編譯原理習(xí)題解答： 第一次作業(yè)： 2、何謂源程序、目標程序、翻譯程序、匯編程序、編譯程序和解釋程序？它們之間可能有何種關(guān)系？ 答：被翻譯的程序稱為源程序； 翻譯出來的程序稱為目標程序或目標代碼； 將匯編語言和高級語言編寫的程序翻譯成等價的機器語言，實現(xiàn)此功能的程序稱為翻譯程序； 把匯編語言寫的源程序翻譯成機器語言的目標程序稱為匯編程序； 解釋程序不是直接將高級語言的源程序翻譯成目標程序后再執(zhí)行，而是一個個語句讀入源程序，即邊解釋邊執(zhí)行； 編譯程序是將高級語言寫的源程序翻譯成目標語言的程序。 關(guān) 系：匯編程序、解釋程序和編譯程序都是翻譯程序，具體見 3、編譯程序是由哪些部分組成？試述各部分的功能？ 答：編譯程序主要由 8 個部分組成：（ 1）詞法分析程序；（ 2）語法分析程序；（ 3）語義分析程序；（ 4）中間代碼生成；（ 5）代碼優(yōu)化程序；（ 6）目標代碼生成程序；（ 7）錯誤檢查和處理程序；（ 8）信息表管理程序。具體功能見 4、語法分析和語義分析有什么不同？試舉例說明。 答：語法分析是將單詞流分析如何組成句子而句子又如何組成程序，看句子乃至程序是否符合語法規(guī)則， 例如：對變量 x： = y 符合語法規(guī)則就通過。語義分析是對語句意義進行檢查，如賦值語句中 x 與 y 類型要一致，否則語法分析正確，語義分析則錯誤。 5、編譯程序分遍由哪些因素決定？ 答：計算機存儲容量大小；編譯程序功能強弱；源語言繁簡；目標程序優(yōu)化程度；設(shè)計和實現(xiàn)編譯程序時使用工具的先進程度以及參加人員多少和素質(zhì)等等。 補充： 1、為什么要對單詞進行內(nèi)部編碼？其原則是什么？對標識符是如何進行內(nèi)部編碼的？ 答：內(nèi)部編碼從“源字符串”中識別單詞并確定單詞的類型和值；原則：長度統(tǒng)一，即刻畫了單詞本身，也刻畫 了它所具有的屬性，以供其它部分分析使用。對于標識符編碼，先判斷出該單詞是標識符，然后在類別編碼中寫入相關(guān)信息，以表示為標識符，再根據(jù)具體標識符的含義編碼該單詞的值。 補充： 2、賦值語句： A： = 5 * C 的語法和語義指的是什么？ 答：語法分析將檢查該語句是否符合賦值語句規(guī)則，語義是指將 5 * C 的結(jié)果賦值為 A 。 第二次作業(yè)： 1、設(shè) 11， 010， 0， 01， 1001，計算： 011， 0010， 0111， 01010， 100111， 1001010 ， 11， 010， 1111， 11010， 01011， 010010 0， 01， 1001， 00， 001， 01001， 010， 0101 3、令 A 0， 1， 2，寫出集合 A+和 A*的七個最短符號串。 A+： 0， 1， 2， 00， 01， 02， 10（有多種可能） A*： ， 0， 1， 2， 00， 01， 02（有多種可能） 5、試證明： A+ A A* A*A。 證明： A+ A* ） A+ A A* A（ A+ ） A A+ A+ A （ A+ ） A A*A（證畢） 7、設(shè)有文法 GS： S A A B | B C | B+C | +C C D | C*D | *D D X | (A) | 試寫出 T。 S， A， B， C， D +， *， X， (， )， - 8、設(shè)有文法 GS： S B B 試問下列符號串（ 1） 3） 5） 否為該文法的句型或句子。 （ 1） S 句型但不是句子； （ 3） S a b 是句型也是句子； （ 5） S 型也是句子。 10、給定文法： S a B b 該文法所描述的語言是什么？ L(G) 相同個數(shù)的 a 與 b 以任意次序連接而成的非空符號串 。 11、試分別描述下列文法所產(chǎn)生的語言（文法開始符號為 S）： （ 1） S 0S | 01 （ 2） S 3） S: = : = 4） S: =: = : = （ 1） L(G) 0n 1； 解題思路：將文法轉(zhuǎn)換為正規(guī)表達式 （ 2） L(G) n 0； （ 3） L(G) i, j, k 1, i=j+或者 L(G) aj+ j, k 1； （ 4） L(G) m 0, n 1。 12、試分別構(gòu)造產(chǎn)生下列語言的文法： （ 1） n=0， 1， 2， 3 （ 2） n=1， 2， 3， 4 （ 3） n 1 （ 4） n, m 1 （ 5） n， m， p 0 （ 6） m， p 0 （ 1） G P， S， S， A ， a， b， P： S 或 S B a （ 2） G P， S， S， a， b， P： S （ 3） G P， S， S， A ， a， b， P： S 或 S a （ 4） G P， S， S， A ， a， b， P： S a （ 5） G P， S， S， A ， B， C ， a， b， c， P： S B C （ 6） G P， S， S， A ， a， b， c， P： S A 第三次作業(yè)： 5. 設(shè)文法 G 規(guī)則為： S： =： =a|： =Aa|下列句型給出推導(dǎo)語法樹，并求出其句型短語，簡單短語和句柄。 （ 2） (3) 2） S A B A a S b b B A B a b B a a 句型 短語 a, 單短語 a，句柄 a S （ 3） A B b B S b A B 短語 單短語 句柄 40 18. 分別對 i+i*i 和 i+i+而證明下述文法 G是二義的。 ： =i|()| ： =+|-|*|/ 1 i+i*i i + i * i * i i + i 由于句子 i+i*i 可構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。 2. i+i+i i + i + i + i i + i 由于句子 i+i+i 可構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。 9. 證明下述文法是二義的 1) S:=iS|i 2) S:=a E:=b 存在句子 者 兩顆不同的語法樹 3) S:=A|B A:=a B:=a C:= (最簡單的就是 a 為句 型 ) 1) 對于句子 構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。 S i S e S i S i S i i S i S i S e S i i S i 3） 對于句子 構(gòu)造兩棵不同的語法樹，所以證明該文法是二義的。 S A a C b A b a a S B B C C a b a b a 1. 令文法 N： =D|： =0|1|2|3|4|5|6|7|8|9 給出句子 0127， 34， 568 最左推導(dǎo)和最右推導(dǎo)。 解： 0127 的最左推導(dǎo) N=001012D=0127 0127 的最右推導(dǎo) N=0127 34 的最左推導(dǎo) N=3D=34 34 的最右推導(dǎo) N=34 568 的最左推導(dǎo) N=556D=568 568 的最右推導(dǎo) N=568 3. 設(shè)有文法如下： :=1:=12:=2+V3| =)( 試分析句子 (, )(*, i(, (+(, (+(i(, (+)(i(*i(。 解 = ( = )(* = i( = 3=3=(+(+( = 3i(= i(= i(=(+(i( = 3 3 (+(+)V1*(+) (+) (+) (+) (+) (+) (+) (i(*(+) (i(*(+) (i(*i( 4. 下面文法那些是短語結(jié)構(gòu)文法，上下文有關(guān)文法，上下文無關(guān)文法，及正 規(guī)文法？ = B:= B:=b C:=c =B:= C:=c C:= = B:=b A:=a =B = B:=b =A:=a B:= B:=b C:=c 6. S:=A:=a B:= C:=c C:= 7. S:=S:= A:=A:=A:=a B:=b 8. S:=S:= A:= A:=a 正規(guī)文法 1 2 7 或者 1 上下文無關(guān)文法 5 6 8 或者 2 5 6 7 8 上下文有關(guān)文法 3 短語結(jié)構(gòu)文法 4 6. 給出產(chǎn)生下列語言 L（ G） =W|W 0， 1+且 W 不含相鄰 1的正規(guī)文法。 G=(S, A, B, 0, 1, P, S) P: S:=0|1|0S|1A A:=0|0S 解題思路一：寫出滿足要求的符號串，例如 0， 1， 00， 01， 10， 000， 101， 010， 001等，根據(jù)符號串從左至右的次序畫出狀態(tài)轉(zhuǎn)換圖，然后根據(jù)狀態(tài)轉(zhuǎn)換圖來推導(dǎo)出文法。這將會得到 S:=0|1|0S|1A|0Z|1Z A:=0|0S|0Z 經(jīng)過分析其中 Z 為多余狀態(tài)可刪去。 解題思路二：寫出其正規(guī)表達式 (0|10)*(10|0|1)【如果僅有 (0|10)*的話推導(dǎo)不出 1，因為是連接關(guān)系，后面缺了 10 的話就會以 1 結(jié)尾，同樣的道理還要推導(dǎo)出 0，所以得到此正規(guī)式】，畫出轉(zhuǎn)換系統(tǒng) ，然后根據(jù)轉(zhuǎn)換系統(tǒng)來推導(dǎo)出文法。也可以根據(jù)正規(guī)表達式直接寫文法，例如正規(guī)表達式 (0|10)*(10|0|1)可以看成是 a*b，推導(dǎo)出 A:= (0|10)A|10|0|1，S Z 1 0 0 1 0 0 A 即 A:= 0A|1B|10|0|1，其中 B:=0A，但是 10 此項不符合正規(guī)文法的選項，可以進行改寫從而得到 A:= 0A|1B|0|1 B:=0A|0。 7. 給出一個產(chǎn)生下列語 言 L（ G） W|W a,b*且 W 中含 a 的個數(shù)是 b 個數(shù)兩倍的前后文無關(guān)文法。 文法 G=(S, A, B, a, b, P, S) P: S:= A:=:=者 S:= 或者 S:= B:=41 28. 給出一個產(chǎn)生下列語言 L(G)=w | w a, b, c+且 w 由相同個數(shù)的 a， b， c 組成的前后文有關(guān)文法。 文法 G=(S, A, B, a, b, c, P, S) P: S:= := a B:= b C:= c =C:=C:=42 29. 用擴充的 示以下文法規(guī)則 ： 1 Z:=C|A 2 A:= S:= A:= 解 : 1 Z:=A（ B|C|） :=AB|C 2 A:=|D） |X（ Z|Y） := |X（ Z|Y） 3 A:=a()b) := aABb 4 A:=:=第四次作業(yè)： . 什么叫超前搜索？掃描緩沖區(qū)的作用是什么？ 詞法分析程序在識別單詞的時候，為進一步判明情況，確定下一步要做什么，一般采用超前讀字符的方法，稱超前搜索，掃描緩沖區(qū)的作用是為了識別單詞符號。 . 畫出下列文法的狀態(tài)圖： Z： = B： = A： =e| 并使用該狀態(tài)圖檢查下列句子是否該文法的合法句子： f, 由狀態(tài)圖可知只有 該文法的合法句子。 . 設(shè)右線性文法 G=(S, A, B, a, b, S, P)，其中 P 組成如下： S： = A： = A： = A： =b B： =a 畫出該文法的狀態(tài)轉(zhuǎn)換圖。 第五次作業(yè)： . 構(gòu)造下述文法 GZ的自動機，該自動機是確定的嗎？它相應(yīng)的語言是什么？ Z： = A： =1|0 解 1：將左線性文法轉(zhuǎn)換為右線性文法，由于在規(guī)則中出現(xiàn)了識別符號出現(xiàn)在規(guī)則右部的情形，因此不能直接使用書上的左右線性文法對應(yīng)規(guī)則，可以引入非終結(jié)符號 B，將左線性文法變?yōu)?Z： = A： =1|0 B： =體為： A := A := A := Z := B := 將所得的新左線性文法轉(zhuǎn)換成右線性文法： 此時利用書上規(guī)則，其對應(yīng)的右線性文法為： A： =0A|0B|0 Z： =0A B： =1A 解 2：先畫出該文法狀態(tài)轉(zhuǎn)換圖： S， A， Z， 0， 1， M， S， Z） 其中 M： M（ S， 0） =A M（ S， 1） = M（ A， 0） =A， Z M（ A， 1） = M（ Z， 0） = M（ Z， 1） =A 顯然該文法的自動機是非確定的；它相應(yīng)的語言為： 0， 1上所有滿足以 00 開頭以 0結(jié)尾且每個 1 必有 0 直接跟在其后的字符串的集合；也可以通過求解正規(guī)表達式得到A=0(0|01)*， Z=0(0|01)*0 那么如何構(gòu)造其相應(yīng)的有窮自 動機呢？ 先構(gòu)造其轉(zhuǎn)換系統(tǒng)： 根據(jù)其轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示： (其中 S可以忽略，結(jié)果是一樣的 ) I 1 S 0 1 S, S A 0 1 A A, Z, Z 1 2 A, Z, Z A, Z, Z A 2 2 1 則其相應(yīng)的 ： . 構(gòu)造一個 接受 0， 1上所有滿足下述條件的字符串，其條件是：字符串 中每個 1 都有 0 直接跟在右邊，然后，再構(gòu)造該語言的正規(guī)文法?！酒渌夥蓞⒖?解 (一 )：其狀態(tài)轉(zhuǎn)換圖為 (狀態(tài) S 表示空串開始，狀態(tài) A 表明串的末尾是 1，狀態(tài) Z 表示串的末尾是 0) S， A， Z， 0， 1， M， S， Z） 其中 M： M（ S， 0） =Z M（ S， 1） = A M（ A， 0） =Z S Z 0 0 1 A 0 Z S 1 2 0 1 0 0 0 S 0 1 1 A 0 Z 0 M（ Z， 0） =Z M（ Z， 1） =A 該語言的正規(guī) 文法 GZ為： 右線性文法： /S： =0|1A|0Z 左線性文法： A： =0|0Z A： =1|： =0|1A|0Z Z： =0|0 若終止狀態(tài)只引入不引出則適合構(gòu)造右線性文法，若開始狀態(tài)只引出不引入則適合構(gòu)造左線性文法，若終態(tài)和初態(tài)均既有引入又有引出，則構(gòu)造文法要注意。 解 (二 )：可以先寫出該文法的正規(guī)表達式為 (0 | 10)*，根據(jù)該正規(guī)式構(gòu)造轉(zhuǎn)換系統(tǒng) 對于該轉(zhuǎn)換系統(tǒng)可以采用子集法將其轉(zhuǎn)變?yōu)?根據(jù) 出其正規(guī)文法；但是注意觀察后，發(fā)現(xiàn)開始狀態(tài) S 通過 到達 A 狀態(tài)，可以直接刪去 S 狀態(tài)，由 A 狀態(tài)作為新的開始狀態(tài)，同理，只有 A 狀態(tài)通過 才能到達終止狀態(tài) Z，因此可以刪去 Z 狀態(tài)，由 A 狀態(tài)作為終止狀態(tài)。這樣， A 狀態(tài)就既為開始狀態(tài)又為終止狀態(tài)。可畫出化簡后的轉(zhuǎn)換圖?？蓪懗鲇揖€性文法為： A： =0|0A|1B B： =0|0S . 設(shè) (M = ( A, B, a, b, M, A, B )，其中 M 定義如下： M (A, a) = A, B M (A, b) = B M (B, a) = M (B, b) = A, B 請構(gòu)造相應(yīng)確定有窮自動機 (M。 解：構(gòu)造一個如下的自動機 (M， (M=K, a, b, M, S, Z K的元素是 A B A, B 由于 M（ A, a） =A, B，故有 M（ A, a） =A, B 同樣 M（ A， b） =B M（ B， a） = M（ B， b） =A， B 由于 M（ A， B， a） = M（ A， a） U M（ B， a） = A， BU = A， B 故 M（ A， B， a） = A， B 由于 M（ A， B， b） = M（ A， b） U M（ B， b） =BU A， B = A， B 故 M（ A， B， b） = A， B S=A，終態(tài)集 Z=A， B， B 重新定義：令 0=A 1=B 2=A, B，則 下所示： S Z A 0 1 B 0 A 0 1 B 0 . 設(shè)有窮自動機 M = (S, A, E, a, b, c, M, S, E)，其中 M 定義為 M (S, c) = A M (A, b) = A M (A, a) = E 請構(gòu)造一個左線性文法。 解：先求右線性文法 S A A a | A 際上是多余的規(guī)則，應(yīng)該去掉 其左線性文法 G=（ P, S） A, S a, b, c 根據(jù)書上左右線性文法的轉(zhuǎn)換規(guī)則，得到 P: A c A S E 際上是多余的規(guī)則，應(yīng)該去掉 畫出狀態(tài)轉(zhuǎn)換圖之后就非常清晰。 0. 已知正規(guī)文法 G = (S, B, C, a, b, c, P, S)，其中 P 內(nèi)包含如下產(chǎn)生式： S:= B:= C:= c 請構(gòu)造一個等價的有窮自動機。 解： M=(S, B, C, T, a, b, c, M, S, T) M (S, a)=S M (S, a)=B M (S, b)= M (S, c)= M (B, a)= M (B, b)=B M (B, b)=C M (B, c)= M (C, a)= M (C, b)= M (C, c)=T M (C, c)=C 第六次作業(yè)： 1. 構(gòu)造下列正規(guī)式相應(yīng)的 （ 1） 1(0|1)*101 【老課本】 解：先構(gòu)造該正規(guī)式的轉(zhuǎn)換系統(tǒng)： 由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集 K=S, 1, 2, 3, 4, 5, Z，狀態(tài)子集轉(zhuǎn)換矩陣如下表所示： I 1 K 0 1 S 1, 2, 3 0 1 1, 2, 3 2, 3 2, 3, 4 1 2 3 S Z 1(0|1)*101 S 1 5 3 4 Z 1 1 0 1 (0|1)* S 1 5 3 4 Z 1 1 0 1 2 0 1 2, 3 2, 3 2, 3, 4 2 2 3 2, 3, 4 2, 3, 5 2, 3, 4 3 4 3 2, 3, 5 2, 3 2, 3, 4, Z 4 2 5 2, 3, 4, Z 2, 3, 5 2, 3, 4 5 4 3 其對應(yīng)的 態(tài)轉(zhuǎn)換圖為： 現(xiàn)在對該 行化簡，最終得到下列化簡后的狀態(tài)轉(zhuǎn)換圖（先將其分成兩組 終態(tài)組5和非終態(tài)組 0, 1, 2, 3, 4，再根據(jù)是否可繼續(xù)劃分來確定最后的組數(shù)）： （ 1） (0 | 11*0)* 【新課本】 解：先構(gòu)造該正規(guī)式的轉(zhuǎn)換系統(tǒng)： 由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換 集 K=S, 1, 2, 3, 4, Z，狀態(tài)子集轉(zhuǎn)換矩陣如下表所示： I 1 K 0 1 S, 1, Z 1, Z 2, 3, 4 0 1 2 1, Z 1, Z 2, 3, 4 1 1 2 2, 3, 4 1, Z 3, 4 2 1 3 3, 4 1, Z 3, 4 3 1 3 0 5 1 1 2 3 1 0 0 1 1 4 0 0 1 1 0 0 5 1 1, 2 3 4 0 1 1 1 1 0 0 0 S Z (0 | 11*0)* S Z 1 0 11*0 S Z 1 0 2 1 3 1 0 4 2. 將圖 確定有窮自動機 定化和最少化。 解：設(shè) ( = K, M, S, Z，其中， K=0, 0, 1, 1， a, b， M： M (1, a) =0 M (1, b) = M (0, 1, a) =0, 1 M (0, 1, b) =1 M (0, a) =0, 1 M (0, b) =1 S=1， Z=0, 0, 1 令 0, 1=2，則其相應(yīng)的狀態(tài)轉(zhuǎn)換圖為： 現(xiàn)在對該 行化簡， 先把狀態(tài)分為兩組： 終態(tài)組 0, 2 和非終態(tài)組 1，易于發(fā)現(xiàn) 0, 2 不可以繼續(xù)劃分，因此化簡后的狀態(tài)轉(zhuǎn)換圖如下： 3. 構(gòu)造下列正規(guī)式的 （ 1） b(a|b)*題的與 11 題基本一樣，見上； 1 0 a a, b a 圖 態(tài)轉(zhuǎn)換圖 1 0 a b a a 2 b 1 0, 2 a b a 由狀態(tài)子集轉(zhuǎn)換矩陣可知，狀態(tài) 0 和 1 是等價的，而狀態(tài) 2和 3 是等價的，因此，合并等價狀態(tài)之后只剩下 2 個狀態(tài)，也即是最少狀態(tài)的 1 0 0 1 0 1 1 1 3 0 0 00 1 0 1 1 2 5. 用兩種方法將 (M = (X, Y, Z, 0, 1, M, X, Z)，構(gòu)造相應(yīng)的 中： M (X, 0) = Z M (X, 1) = X M (Y, 0) = X, Y M (Y, 1) = M (Z, 0) = X, Z M (Z, 1) = Y 第一種方法：先畫出其狀態(tài)轉(zhuǎn)換圖，利用非子集法： 假設(shè) (M=(K, M, S, Z)，其中 K=X, Y, Z, X,Y, X, Z, Y, Z, X, Y, Z，0, 1， M的規(guī)則如下表： I 1 K 0 1 X Z X 0 2 0 Y X, Y 1 3 Z X, Z Y 2 4 1 X, Y X, Y, Z X 3 6 0 X, Z X, Z X, Y 4 4 3 Y, Z X, Y, Z Y 5 6 1 X, Y, Z X, Y, Z X, Y 6 6 3 其中 Y, Z為不可到達狀態(tài)，應(yīng)該刪去，所以 S=X， Z=Z, X, Z, X, Y, Z，再進行化簡，發(fā)現(xiàn) 4 和 6 兩狀態(tài)等價，最后其 下所示： 第二種方法：先構(gòu)造其對應(yīng)的轉(zhuǎn)換系統(tǒng)： X Z 1 0 1 0 0 0 Y 0 X Z 1 0 1 0 0 0 Y 0 Z S 0 1 1 0 0 0 1 3 0 1 1 2 4, 6 0 由上述轉(zhuǎn)換系統(tǒng)可得狀態(tài)轉(zhuǎn)換集、狀態(tài)子集轉(zhuǎn)換矩陣如下表所示： I 1 K 0 1 S, X Z, Z X 0 1 2 Z, Z X, Z, Z Y 1 3 4 X Z, Z X 2 1 2 X, Z, Z X, Z, Z X, Y 3 3 5 Y X, Y 4 5 X, Y X, Y, Z, Z X 5 6 2 X, Y, Z, Z X, Y, Z, Z X, Y 6 6 5 先化簡，分為非終態(tài)集 2, 4, 5, 0 和終態(tài)集 6, 1, 3，易于發(fā)現(xiàn)可劃分為 0, 2， 1， 3, 6，4， 5，其 下所示： 6. 已知 (a|b)*， a*b*)*，試證明 證明： L(L(a|b)*)= (L (a|b)*= (L (a) L(b)*=a, b*； L( L(a*b*)*)= (L (a*b*)*=(L(a*)L(b*)*=a*b*=a, b*； 因此 證） 8. 根據(jù)下面正規(guī)文法構(gòu)造等價的正規(guī)表達式： S:= a A:= B:= c C:= a 解：由 式可得 B= c B=a*c 由 式可得 A= A= c*aa*c 由 式可得 S= a 由 式可得 C= a C= c*( a) C= c*( ac*aa*c + ba*c + a) S= ac*aa*c + ba*c + a) + a = cc* ac*aa*c + ba*c + a) + a = (cc*a)*( ac*aa*c + ba*c + a) + a) = (cc*a)*( ac*aa*c | ba*c | a) | a) 另一種答案是 S= c( c)*( ac*aa*c | ba*c | a) | a 9. a, b，寫出下列正規(guī)集： （ 1） (a | b)*( a | b)* 解： L(a | b)*( a | b)*) = L(a | b)*) L( L(a | b)*) =(L (a | b)* (L (a | b)* = a, b*a, b* 0. 證明下列關(guān)系式成立，其 中 A、 B 是任意正規(guī)表達式。 1 4 1 0 5 0 0 0 1 0 1 3, 6 1 0, 2 （ 1） A | A = A （ 3） A* = | （ 4） (A = A( （ 1）解： L(A | A) = L(A) L(A) = L(A)，所以 A | A = A； （ 3） 解 ： L(A*) = (L(A)*， L(| = L(A)L(A*) = (L(A)*， 所以 A* = | （ 4）解： (A = ( ( ( )A = A = A( ( ( ) = A(。 第七次作業(yè)： . 試分別消除下列文法的直接左遞歸（采用兩種方法 重復(fù)法和改寫法） （ 1） GE: E:=T | T:=F | F:=(E) | i A:=+ | - M:=* | / 解：先采用“重復(fù)法”： 再采用“改寫法”： E:=T E:=T:=F E:= | F:=(E) | i T:=A:=+ | - T:=| M:=* | / F:=(E) | i A:=+ | - M:=* | / （ 4） GZ: Z:= = = 3 =)| ( 解：先采用“重復(fù)法”： 再采用“改寫法”： Z:= Z:=1:= =1 =+ :=i 1 | =)| ( =2 :=+2 | =)| ( . 試分別消除下列文法的間接左遞歸 （ 2） GZ: Z:= b A:=Z A | a 解 (一 )：將式代入式可得， Z:= b 消除左遞歸后得到： Z:=( b)Z Z:=| A:= a 解 (二 )：將式代入式可得， A:= a 消除左遞歸后得到： Z:= b A:=| A:=| . 試分別用兩種方法（框圖法和類 言或類 C 語言）寫一個識別下面文法句子的遞歸子程序 文法 GA: A:=B B:=X | X:= a | b 解：消除該文法的左遞歸和回溯，得到文法如下： A:=B B:=XB B:=| X:=| X:= | | 用類 言寫出其遞歸子程序： P(A): F (B) (B): (X) IF (B) (B): F # P(A) P(B) (X): F a P(X) F b P(X) (X): F F a P(X) F b P(X) 框圖法來表述：（此處僅給出 P(A)和 P(X)的框圖形式，其余相似從略） 當消除左遞歸和回溯之后，可能某些非終結(jié)符號例如 U 的右部會出現(xiàn) 的情況，書上的處理方法是 將自動獲得匹配，并無對此類規(guī)則的具體處理方法，實際上應(yīng)該求出)，對于 )中的每個終結(jié)符號進行判定，例如此例中的 P(X)，否則將無法判定出 a P(A): P(X): 第八次作業(yè)： . 對下面的文法 GE: E:= E:=+E | T:=T:=T | F:=F:=*F | P (E) |a |b | （ 1）計算這個文法的每個非終 結(jié)符號的 （ 2）證明這個文法是 1）文法； （ 3）構(gòu)造它的 1）分析表并分析符號串 a*b+b; 解 :（ 1）構(gòu)造 ： )=+, )=*, )=)=)=) = (