[政史地]第2節(jié)課第二章ppt課件

1、編譯程序編譯程序的構(gòu)成的構(gòu)成 編譯程序主要由八個(gè)部分構(gòu)成：編譯程序主要由八個(gè)部分構(gòu)成：1.1.程序程序掃描器掃描器 scannerscanner2.2.程序程序分析器分析器 parserparser3.3.程序程序4.4.程序程序5.5.程序程序6.6.程序程序7.7.程序程序8.8.程序程序1.2 1.2 的的詞詞法法分分析析程程序序語語法法分分析析程程序序語語義義分分析析程程序序中中間間代代碼碼生生成成代代碼碼優(yōu)優(yōu)化化程程序序目目標(biāo)標(biāo)代代碼碼生生成成信信 息息 表表 管管 理理 程程 序序錯(cuò)錯(cuò) 誤誤 檢檢 查查 和和 處處 理理 程程 序序源源程程序序目目標(biāo)標(biāo)代代碼碼1.3 需要注意的是，

2、前面所說的各部分之間的關(guān)系，需要注意的是，前面所說的各部分之間的關(guān)系，是指它們之間的是指它們之間的邏輯關(guān)系邏輯關(guān)系，而不一定是執(zhí)行時(shí)，而不一定是執(zhí)行時(shí)間上的先后順序。間上的先后順序。 事實(shí)上，可按不同的執(zhí)行流程來組織上述各部事實(shí)上，可按不同的執(zhí)行流程來組織上述各部分的工作，這在很大程度上依賴于編譯過程中分的工作，這在很大程度上依賴于編譯過程中對(duì)源程序掃描的遍數(shù)對(duì)源程序掃描的遍數(shù)，以及如何劃分各遍掃描，以及如何劃分各遍掃描所進(jìn)展的工作。所進(jìn)展的工作。 此處所說的此處所說的“遍遍,是指對(duì)源程序或其內(nèi)部表示是指對(duì)源程序或其內(nèi)部表示從頭到尾掃視一次從頭到尾掃視一次,并進(jìn)展有關(guān)的加工處理工作。并進(jìn)展有關(guān)

3、的加工處理工作。 例如，對(duì)于要求經(jīng)例如，對(duì)于要求經(jīng)一遍掃描一遍掃描就能完成從源程就能完成從源程序到目的代碼翻譯的編譯程序，我們可序到目的代碼翻譯的編譯程序，我們可以語以語法分析程序?yàn)橹行姆ǚ治龀绦驗(yàn)橹行膩斫M織它的工作流程。來組織它的工作流程。 語法分析語法分析程序程序語義分析及語義分析及代碼生成程序代碼生成程序詞法分析詞法分析程序程序整理目標(biāo)程序整理目標(biāo)程序源程序源程序目標(biāo)程序目標(biāo)程序停機(jī)停機(jī)開始開始圖圖1-3 以語法分析程序?yàn)橹行牡木幾g程序邏輯構(gòu)造以語法分析程序?yàn)橹行牡木幾g程序邏輯構(gòu)造 顯然，由于整個(gè)編譯程序只對(duì)源程序進(jìn)展一顯然，由于整個(gè)編譯程序只對(duì)源程序進(jìn)展一次掃描，故次掃描，故不必產(chǎn)生中

4、間代碼不必產(chǎn)生中間代碼。 對(duì)于某些程序語言，例如對(duì)于某些程序語言，例如PASCAL和和C，用一，用一遍掃描的編譯程序去實(shí)現(xiàn)比較困難，宜于采遍掃描的編譯程序去實(shí)現(xiàn)比較困難，宜于采用用多遍掃描多遍掃描的編譯程序構(gòu)造。的編譯程序構(gòu)造。 本章內(nèi)容完畢本章內(nèi)容完畢第第2章章 在在20世紀(jì)世紀(jì)50年代，年代，N.Chomsky首先對(duì)語言的描首先對(duì)語言的描繪問題進(jìn)展了討論。他提出了一種用來描繪語繪問題進(jìn)展了討論。他提出了一種用來描繪語言的數(shù)學(xué)系統(tǒng)，并以此定義了四類性質(zhì)不同的言的數(shù)學(xué)系統(tǒng)，并以此定義了四類性質(zhì)不同的語言，稱為語言，稱為語言文法的語言文法的Chomsky分類分類。 人們把用一組數(shù)學(xué)符號(hào)和規(guī)那么來

5、描繪語言的人們把用一組數(shù)學(xué)符號(hào)和規(guī)那么來描繪語言的方式稱為方式稱為形式描繪形式描繪，把所用的數(shù)學(xué)符號(hào)和規(guī)那，把所用的數(shù)學(xué)符號(hào)和規(guī)那么稱為么稱為形式語言形式語言。 目前，目前，形式語言與自動(dòng)機(jī)理論形式語言與自動(dòng)機(jī)理論已成為計(jì)算機(jī)科已成為計(jì)算機(jī)科學(xué)中的一個(gè)重要分支。學(xué)中的一個(gè)重要分支。2.1 文法及語言的表示文法及語言的表示 首先，我們確定一個(gè)概念：什么是語言？據(jù)首先，我們確定一個(gè)概念：什么是語言？據(jù)統(tǒng)計(jì)，目前在世界各地，人們所使用的語言統(tǒng)計(jì)，目前在世界各地，人們所使用的語言達(dá)達(dá)2700多種。多種。 Webster的定義：的定義：“為相當(dāng)大地區(qū)的公眾所懂為相當(dāng)大地區(qū)的公眾所懂得并使用的得并使用的話

6、話，以及組成這些，以及組成這些話話的的方法的統(tǒng)一體方法的統(tǒng)一體。 上述定義對(duì)于建立語言的數(shù)學(xué)理論而言不夠上述定義對(duì)于建立語言的數(shù)學(xué)理論而言不夠準(zhǔn)確。準(zhǔn)確。 所以，有人又將語言定義為：所以，有人又將語言定義為：“某一字母表某一字母表上符號(hào)串句子的集合上符號(hào)串句子的集合 此定義仍需準(zhǔn)確化。因?yàn)椋捍硕x仍需準(zhǔn)確化。因?yàn)椋?還應(yīng)為所定義的句子還應(yīng)為所定義的句子提供一種構(gòu)造性的描繪提供一種構(gòu)造性的描繪語法規(guī)那么語法規(guī)那么；2最好能再提供一種手段，以便最好能再提供一種手段，以便能準(zhǔn)確地判別能準(zhǔn)確地判別什么是該語言中的正確句子什么是該語言中的正確句子即識(shí)別方法、即識(shí)別方法、分析方法等分析方法等。 遺憾的是，

7、對(duì)于自然語言來說，目前尚無可遺憾的是，對(duì)于自然語言來說，目前尚無可以完全刻劃一語言全部句子的構(gòu)造的方法。以完全刻劃一語言全部句子的構(gòu)造的方法。 然而，對(duì)大多數(shù)程序設(shè)計(jì)語言來說，此問題然而，對(duì)大多數(shù)程序設(shè)計(jì)語言來說，此問題已被解決。已被解決。1960年，年，P.Naur & J.Backus首先首先用用BNFBackus-Naur-Formal范式對(duì)范式對(duì)ALGOL語言進(jìn)展了描繪。語言進(jìn)展了描繪。 應(yīng)指出，應(yīng)指出，BNF成功地解決了程序設(shè)計(jì)語言的成功地解決了程序設(shè)計(jì)語言的語法描繪問題，但描繪其語義，還必須借助語法描繪問題，但描繪其語義，還必須借助自然語言。自然語言。 通常，可用如下方式表

8、示或定義一種語言：通常，可用如下方式表示或定義一種語言：1假設(shè)語言的句子有限時(shí)，可用假設(shè)語言的句子有限時(shí)，可用枚舉法枚舉法。 例如，只含兩個(gè)句子的語言：例如，只含兩個(gè)句子的語言： “I am a teacher, “You are students ;2制定制定，用于產(chǎn)生所要描繪的，用于產(chǎn)生所要描繪的語言的全部句子語言的全部句子可無限多可無限多，這些規(guī)那么，這些規(guī)那么構(gòu)成了該語言的構(gòu)成了該語言的文法文法。 例如，文法例如，文法G1標(biāo)識(shí)符標(biāo)識(shí)符 ： 標(biāo)識(shí)符標(biāo)識(shí)符字母字母|標(biāo)識(shí)符標(biāo)識(shí)符字母字母 |標(biāo)識(shí)符標(biāo)識(shí)符數(shù)字?jǐn)?shù)字 字母字母 a | b | c | | z 數(shù)字?jǐn)?shù)字 0 | 1 | 2 | |

9、93建立一種建立一種，它以某字它以某字母表上的符號(hào)串為輸入，判別該符號(hào)串是否母表上的符號(hào)串為輸入，判別該符號(hào)串是否為所描繪語言的句子。此裝置稱為為所描繪語言的句子。此裝置稱為自動(dòng)機(jī)。自動(dòng)機(jī)。cabbcaaSAB2.2 文法和語言的定義文法和語言的定義2.2.1 根本概念和術(shù)語根本概念和術(shù)語1、字母表符號(hào)表、符號(hào)集字母表符號(hào)表、符號(hào)集 由假設(shè)干元素由假設(shè)干元素符符 號(hào)、字母所組成的有限非空集合。號(hào)、字母所組成的有限非空集合。2、符號(hào)串符號(hào)串 用字母表中的符號(hào)所組成的任何有限用字母表中的符號(hào)所組成的任何有限 序列。序列。 符號(hào)串的長度符號(hào)串的長度 = 符號(hào)串中所含符號(hào)的個(gè)數(shù)。符號(hào)串中所含符號(hào)的個(gè)數(shù)

10、。 例：例：aba的長度為的長度為3。記為：。記為：|aba|=3 空串空串 不含任何符號(hào)的符號(hào)串，記為不含任何符號(hào)的符號(hào)串，記為 。 顯然，顯然，| |= 0。 本課約定本課約定 用用A、B、C、 等表示字母表或等表示字母表或符號(hào)串集；符號(hào)串集； 用用a,b,c,S,T,U 等表示符號(hào)；等表示符號(hào)； 用用s,t,u,x,y,z, , , 等表示符號(hào)串。等表示符號(hào)串。3、符號(hào)串的前后綴及子串符號(hào)串的前后綴及子串 設(shè)設(shè) ， ， ，x 是符號(hào)串，是符號(hào)串， 假設(shè)假設(shè) x = ，那么稱，那么稱 是是 x 的的子串子串； 特別地，特別地， 當(dāng)當(dāng) = = 時(shí)，稱時(shí)，稱 是是 x 的的前前后后綴綴。4、符

11、號(hào)串的連接和方冪符號(hào)串的連接和方冪連接連接 設(shè)設(shè)x , y是符號(hào)串，將是符號(hào)串，將y直接拼接到直接拼接到x之后所之后所得的新符號(hào)串稱為得的新符號(hào)串稱為x與與y的連接，記為的連接，記為xy 。 注意，一般說來，注意，一般說來，xy 不等于不等于 yx；但但 x = x = x 方冪方冪 符號(hào)串符號(hào)串x與其自身的與其自身的 n-1次連接稱為次連接稱為 x 的的 n 次方冪，記為：次方冪，記為：nx 011:,.3,2xnxxxxxnn我我們們約約定定這這里里即即5、符號(hào)串集合的和與積符號(hào)串集合的和與積 設(shè)設(shè)A，B為兩個(gè)符號(hào)串集合，定義：為兩個(gè)符號(hào)串集合，定義：和：和：A+B或或AB=w | w A

12、，或，或 w B 例如，假設(shè)例如，假設(shè)A=a,b,c，B=00,11，那么，那么 A+B=a,b,c,00,11。 積：積：AB或或 AB= xy | x A, 且且y B 例如，假設(shè)例如，假設(shè)A=a,b,c，B=00,11，那么，那么 AB=a00,a11,b00,b11,c00,c11顯然，顯然， A+ = +A = A ； A = A = ； A = A = A6、符號(hào)串集合的方冪符號(hào)串集合的方冪)0(:,110 nAAAAAAAAnnn 的的方方冪冪定定義義是是符符號(hào)號(hào)串串集集合合設(shè)設(shè)例如，假設(shè)例如，假設(shè)A=a,b，那么，那么,3210bbbbbababbaaabbabaaabaaaA

13、bbbaabaaAbaAA 7。符號(hào)串集合的閉包符號(hào)串集合的閉包根據(jù)符號(hào)串集合的和運(yùn)算，我們又可分別定義符根據(jù)符號(hào)串集合的和運(yùn)算，我們又可分別定義符號(hào)串集合號(hào)串集合A的的 正閉包正閉包A+ 及及 自反傳遞閉包自反傳遞閉包A* 如下：如下： niiAAAAAA21:)(閉閉包包正正的的傳傳遞遞 AAAAAii:0* 的的自自反反傳傳遞遞閉閉包包例如，假設(shè)例如，假設(shè)A=a,b，那么，那么,bbbbbababbaaabbabaaabaaabbbaabaabaA ,*bbbbbababbaaabbabaaabaaabbbaabaabaA niiAAAAA21 AAAAii0* 例例A=a,b,c,1c

14、baA ,2cccbcabcbbbaacabaaA ,*abaacbaA 合合上上所所有有符符號(hào)號(hào)串串構(gòu)構(gòu)成成的的集集實(shí)實(shí)際際上上就就是是AA*2.2 我們從我們從“產(chǎn)生語言的角度出發(fā)，討論文法產(chǎn)生語言的角度出發(fā)，討論文法和語言的形式定義。和語言的形式定義。產(chǎn)生語言產(chǎn)生語言指制定出有限條規(guī)那么，借助指制定出有限條規(guī)那么，借助它們就能產(chǎn)生出某些語言的句子。它們就能產(chǎn)生出某些語言的句子。 我們以幾個(gè)英語句子構(gòu)成的語言為例進(jìn)展討我們以幾個(gè)英語句子構(gòu)成的語言為例進(jìn)展討論。并設(shè)每個(gè)句子都是論。并設(shè)每個(gè)句子都是“主主-謂謂-賓構(gòu)造。賓構(gòu)造。 其中，每個(gè)用其中，每個(gè)用 “ 括起來的部分是所要定括起來的部分是

15、所要定義語言中的一個(gè)語法實(shí)體稱為語法單位、語義語言中的一個(gè)語法實(shí)體稱為語法單位、語法構(gòu)造、法構(gòu)造、語法范疇語法范疇、語法變量等。、語法變量等。 “:= 是用于定義語法構(gòu)造的符號(hào)，其含義是用于定義語法構(gòu)造的符號(hào)，其含義并讀作并讀作“定義為定義為。 語法規(guī)那么也稱為語法規(guī)那么也稱為產(chǎn)生式產(chǎn)生式Production。:= := the := := the :=:=:=monkey :=banana:=eat :=has:= the := a 如今討論如何用上述規(guī)那么如今討論如何用上述規(guī)那么推導(dǎo)推導(dǎo)出相應(yīng)語言的出相應(yīng)語言的全部全部句子句子。推導(dǎo)推導(dǎo) 從語言最大的一個(gè)從語言最大的一個(gè)語法范疇語法范疇本例

16、中是本例中是 開場，反復(fù)用語法規(guī)那么中開場，反復(fù)用語法規(guī)那么中“:= 右側(cè)的符號(hào)串取代其左側(cè)符號(hào)，直到所得的符右側(cè)的符號(hào)串取代其左側(cè)符號(hào)，直到所得的符號(hào)串中不再含有可被交換的號(hào)串中不再含有可被交換的語法范疇語法范疇。 每次交換稱為一步每次交換稱為一步直接直接推導(dǎo)推導(dǎo)，并用符號(hào)，并用符號(hào)“表示。例如，表示。例如， 首先用規(guī)那么進(jìn)展第一步推導(dǎo)首先用規(guī)那么進(jìn)展第一步推導(dǎo)derivation，就可得到，就可得到，記為：記為： 所得的符號(hào)串含有兩個(gè)所得的符號(hào)串含有兩個(gè)語法范疇語法范疇，可對(duì)其中任，可對(duì)其中任一個(gè)一個(gè)如對(duì)如對(duì)進(jìn)展新的進(jìn)展新的推導(dǎo)推導(dǎo)交交換：換： 重復(fù)上述過程，可得到一個(gè)推導(dǎo)序列：重復(fù)上述過

17、程，可得到一個(gè)推導(dǎo)序列：推導(dǎo)推導(dǎo) 所用所用 所得的符號(hào)串所得的符號(hào)串步驟步驟 規(guī)那么規(guī)那么 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 the monkey eat a banana 從前面的推導(dǎo)看，從從前面的推導(dǎo)看，從出發(fā)，經(jīng)出發(fā)，經(jīng)8步推導(dǎo)步推導(dǎo)得到了一個(gè)英語句子。故前面的推導(dǎo)稱為得到了一個(gè)英語句子。故前面的推導(dǎo)稱為長度長度為為8的推導(dǎo)的推導(dǎo)。 假設(shè)不關(guān)心推導(dǎo)的中間過程，可將從一符號(hào)串假設(shè)不關(guān)心推導(dǎo)的中間過程，可將從一符號(hào)串到到 另一符號(hào)串的推導(dǎo)用記號(hào)另一符號(hào)串的推導(dǎo)用記號(hào) 表示，例如，表示，例如，

18、上例中經(jīng)過上例中經(jīng)過 5 步的推導(dǎo)記為：步的推導(dǎo)記為： 名名詞詞冠冠詞詞動(dòng)動(dòng)詞詞句句子子monkeythe規(guī)那么的簡化表示規(guī)那么的簡化表示 在前面的語法規(guī)那么定義中在前面的語法規(guī)那么定義中,有些語法范疇有些語法范疇如如、有假設(shè)干條不同的規(guī)那么來有假設(shè)干條不同的規(guī)那么來定義它。定義它。 為簡明起見，我們可以將它們寫在同一個(gè)左部為簡明起見，我們可以將它們寫在同一個(gè)左部語法范疇下，將其定義值用符號(hào)語法范疇下，將其定義值用符號(hào)“| 讀作讀作或或 隔開。如隔開。如、的定義規(guī)那么可簡記為：的定義規(guī)那么可簡記為： := monkey | banana := eat | has := the | a語法規(guī)那么

19、及其產(chǎn)生的語言語法規(guī)那么及其產(chǎn)生的語言 前面的語法規(guī)那么可以產(chǎn)生前面的語法規(guī)那么可以產(chǎn)生16個(gè)不同的句子，個(gè)不同的句子，。 應(yīng)指出，所產(chǎn)生的句子中，有些句子的含義是應(yīng)指出，所產(chǎn)生的句子中，有些句子的含義是荒唐荒唐的如的如 the banana eat a monkey 和和 the banana eat the banana 等。等。 然而，假設(shè)不考慮然而，假設(shè)不考慮語義語義，那么我們就必須成認(rèn)，那么我們就必須成認(rèn)它們是語法上它們是語法上合法合法的句子。的句子。 為得到文法的嚴(yán)格定義，對(duì)前面的規(guī)那么為得到文法的嚴(yán)格定義，對(duì)前面的規(guī)那么進(jìn)進(jìn)行如下的概括：行如下的概括： 含有一系列需要定義的語法范

20、疇，通常我們把含有一系列需要定義的語法范疇，通常我們把它們的名字稱為它們的名字稱為非終結(jié)符號(hào)非終結(jié)符號(hào)。 由這些非終結(jié)符號(hào)組成的集合稱為由這些非終結(jié)符號(hào)組成的集合稱為非終結(jié)符號(hào)非終結(jié)符號(hào)集集，用，用 VN 記之。對(duì)于上例，我們有：記之。對(duì)于上例，我們有： VN = 句子句子,主語短語主語短語,動(dòng)詞短語動(dòng)詞短語, 賓語短語賓語短語,名詞名詞,動(dòng)詞動(dòng)詞,冠詞冠詞 含有假設(shè)干個(gè)根本符號(hào)，由于這些根本符號(hào)含有假設(shè)干個(gè)根本符號(hào)，由于這些根本符號(hào)不需要進(jìn)一步定義，故通常將它們稱為不需要進(jìn)一步定義，故通常將它們稱為終結(jié)終結(jié)符號(hào)符號(hào)。 由終結(jié)符號(hào)組成的集合稱為由終結(jié)符號(hào)組成的集合稱為終結(jié)符號(hào)集終結(jié)符號(hào)集，以，

21、以VT 記之。對(duì)于上例有：記之。對(duì)于上例有： VT = monkey, banana, eat, has, the, a TNTNNTNTNVVVVVVSPVVSPVVSGSG且且詞詞匯匯表表字字匯匯表表稱稱為為法法的的開開始始符符號(hào)號(hào)。為為文文產(chǎn)產(chǎn)生生式式集集終終結(jié)結(jié)符符集集分分別別稱稱為為非非終終結(jié)結(jié)符符集集空空有有限限集集為為非非。其其中中是是一一四四元元組組一一文文法法定定義義),(;,12注注：為使用上的方便，我們用為使用上的方便，我們用代替產(chǎn)生式中的代替產(chǎn)生式中的 :=。另外，在不強(qiáng)調(diào)開場符號(hào)。另外，在不強(qiáng)調(diào)開場符號(hào) S 時(shí)，可將文法時(shí)，可將文法 GS 簡記為簡記為 G 。 GGT

22、NUPUVUVSPVVS 或或的的直直接接推推導(dǎo)導(dǎo)記記為為是是我我們們把把通通常常。且且其其中中和和可可分分別別寫寫成成當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)，直直接接產(chǎn)產(chǎn)生生或或的的直直接接推推導(dǎo)導(dǎo)是是稱稱是是一一文文法法設(shè)設(shè)定定義義,)(,22*當(dāng)然，上述定義中的當(dāng)然，上述定義中的 、 、 都可以是空串都可以是空串 。另外，。另外，推導(dǎo)符號(hào)推導(dǎo)符號(hào)下面的下面的G表示推導(dǎo)是以文法表示推導(dǎo)是以文法G的規(guī)那么的規(guī)那么進(jìn)展的，假設(shè)進(jìn)展的，假設(shè)G無須指明，那么可簡寫為無須指明，那么可簡寫為例如，由前面的文法例如，由前面的文法G，可得推導(dǎo)：可得推導(dǎo)： 其中，其中， = , = , = := := the :=)()1(0,

23、),2(;0),1(1,)2(,)1(),(,3 . 20*01010nnnnnnnnVVG 的的推推導(dǎo)導(dǎo)記記為為長長度度通通常常的的推推導(dǎo)導(dǎo)。則則稱稱為為長長度度為為對(duì)對(duì)于于步步推推導(dǎo)導(dǎo)稱稱為為對(duì)對(duì)于于情情況況使使上上的的符符號(hào)號(hào)串串序序列列存存在在或或如如果果產(chǎn)產(chǎn)生生的的推推導(dǎo)導(dǎo)是是符符號(hào)號(hào)串串，稱稱上上的的兩兩個(gè)個(gè)是是為為一一文文法法設(shè)設(shè)定定義義。產(chǎn)產(chǎn)生生的的句句子子是是則則稱稱特特別別地地，當(dāng)當(dāng)句句型型的的一一個(gè)個(gè)句句型型。是是則則稱稱若若是是文文法法設(shè)設(shè)定定義義),(,4 .2*GVGSVSGTG 例例2.1：GA: A Bb B a 該文法僅有該文法僅有3個(gè)句型個(gè)句型 A, Bb,

24、 ab， 僅有僅有1個(gè)句子個(gè)句子ab。產(chǎn)產(chǎn)生生的的句句子子是是則則稱稱特特別別地地，當(dāng)當(dāng)句句型型的的一一個(gè)個(gè)句句型型。是是則則稱稱若若是是文文法法設(shè)設(shè)定定義義),(,4 .2*GVGSVSGTG 例例2.2：GS: S aB | Bb B a | b 該文法僅有該文法僅有6個(gè)句型個(gè)句型S, aB, Bb, aa, ab, bb， 僅有僅有3個(gè)句子個(gè)句子aa, ab, bb 。上上的的。是是定定義義于于字字母母表表故故由由于于產(chǎn)產(chǎn)生生的的語語言言。稱稱為為則則是是文文法法設(shè)設(shè)定定義義TTTGVGLVGLGVwwSwGLSG)(,)(,|)(,5 . 2* 例例2.1：GA: A Bb B a 例

25、例2.2：GS: S aB | Bb B a | b )(abAGL ,)(bbabaaSGL 我們看到，我們看到，LGA和和LGS是由有是由有限的句子組成的。當(dāng)語言是無限集時(shí)，能否用有限的句子組成的。當(dāng)語言是無限集時(shí)，能否用有限的規(guī)那么來描繪呢？答復(fù)是肯定的限的規(guī)那么來描繪呢？答復(fù)是肯定的, 只需使用只需使用文法的文法的遞歸定義遞歸定義即可。即可。例例2.1：GA: ABb Ba 例例2.2：GS: SaB|Bb Ba|b )(abAGL ,)(bbabaaSGL 例例2.3：GS: S 0S1 | 01 S,01,0S1,0011,00S11,000111,000S111,是句是句 型，其中型，其中01，0011，000111,是句子，故是句子，故 例例2.4： 設(shè)設(shè) =a,b, 那么那么 + 字符串集的字符串集的BNF表表示示 如下：如下： GA: A a | b | Aa | Ab 110)( nSGLnn所謂所謂遞歸定義遞歸定義，是指在定義一個(gè)語法成分時(shí)，是指在定義一個(gè)語法成分時(shí)，直接