編譯原理習(xí)題與答案

1、第二章 2.2 設(shè)有文法設(shè)有文法GN: N-D | NDD-0|1|9 (1) GN定義的語(yǔ)言是什么？定義的語(yǔ)言是什么？ (2) 請(qǐng)給出句子請(qǐng)給出句子0123的最左推導(dǎo)和最右推導(dǎo)。的最左推導(dǎo)和最右推導(dǎo)。 N ND NDD NDDDDDDD 0DDD 01DD 012D 0123 N ND N3ND3 N23 ND23 N123 D123 0123 2.5 證明下面的文法是二義性的。證明下面的文法是二義性的。 SiSeS | iS | i 答：對(duì)句子答：對(duì)句子iiiei對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù) 第二章 S iS SeiS ii S iS SeiS i i 2.9 設(shè)有文法設(shè)有文法

2、GT: TT*F|F F FP|PP(T)|i 分析句型分析句型T*P (T*F)的短語(yǔ)、直接短語(yǔ)和句柄的短語(yǔ)、直接短語(yǔ)和句柄 答：句型答：句型T*P (T*F)的語(yǔ)法樹(shù)：的語(yǔ)法樹(shù)：T TF * ()T 五棵子樹(shù)對(duì)應(yīng)五個(gè)短語(yǔ)五棵子樹(shù)對(duì)應(yīng)五個(gè)短語(yǔ)T*P (T*F), P (T*F), P, (T*F), T*F 兩層子樹(shù)兩層子樹(shù)( (簡(jiǎn)單子樹(shù)簡(jiǎn)單子樹(shù)) )的末端結(jié)點(diǎn)構(gòu)成直接短語(yǔ)的末端結(jié)點(diǎn)構(gòu)成直接短語(yǔ) 兩棵兩層子樹(shù)對(duì)應(yīng)兩個(gè)直接短語(yǔ)：兩棵兩層子樹(shù)對(duì)應(yīng)兩個(gè)直接短語(yǔ)： P , T*F 位于最左邊的兩層子樹(shù)的末端結(jié)點(diǎn)構(gòu)成句柄：位于最左邊的兩層子樹(shù)的末端結(jié)點(diǎn)構(gòu)成句柄： P 第二章 PF P TF * 第三章

3、 3.1 構(gòu)造正規(guī)式構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的相應(yīng)的NFA X 1 B 1 C 10 D Y A (0|1)* X 1 B 1 C 10 D Y A E 0|1 X 1 B 1 C 10 D Y A E 0,1 第三章 3.1 構(gòu)造正規(guī)式構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的相應(yīng)的NFA X 11 B 10 C Y A (0|1)* 0,1 X 11 B 10 C Y A X 1 B 1 C 10 D Y A E 0,1 第三章 3.5 給出下述文法所對(duì)應(yīng)的正規(guī)式。給出下述文法所對(duì)應(yīng)的正規(guī)式。 G：SaA AbA | aB | b B aA 解：先由產(chǎn)生式得解：先由產(chǎn)生式得: B=aA

4、 將將B代入代入A中得中得:A=bA|aaA|b =(b|aa)A|b 利用規(guī)則利用規(guī)則（A-xA|y）得得: A= (b|aa) * b 將將A代入代入S中得中得:S=a (b|aa) * b 即為所求正規(guī)式即為所求正規(guī)式 3.4 給出文法給出文法GS，構(gòu)造相應(yīng)最小的，構(gòu)造相應(yīng)最小的DFA。 G：SaS | bA | b AaS 解解：由文法到由文法到NFA的轉(zhuǎn)換有兩種方法：的轉(zhuǎn)換有兩種方法： 由文法到正規(guī)式，再由正規(guī)式到由文法到正規(guī)式，再由正規(guī)式到NFA 先由產(chǎn)生式得先由產(chǎn)生式得:A = aS 將將A代入代入S中得中得:S = aS|bA|b = aS|baS|b = (a|ba)S|b

5、利用規(guī)則利用規(guī)則（A-xA|y）得得: S= (a|ba)*b 文法文法G對(duì)應(yīng)的正規(guī)式為對(duì)應(yīng)的正規(guī)式為(a|ba)*b ，其對(duì)應(yīng)的，其對(duì)應(yīng)的NFA的的 狀態(tài)轉(zhuǎn)換圖為狀態(tài)轉(zhuǎn)換圖為： 第三章 3.4 給出文法給出文法GS，構(gòu)造相，構(gòu)造相 應(yīng)最小的應(yīng)最小的DFA。 G：SaS | bA | b AaS 解解： 由文法直接到由文法直接到NFA 文法對(duì)應(yīng)的有自動(dòng)文法對(duì)應(yīng)的有自動(dòng) M=(S,A, T, a,b, f, S, T) 其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖為：其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖為： 產(chǎn)生式產(chǎn)生式轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) SaSf(S,a)=Sf(S,a)=S SbAf(S,b)=Af(S,b)=A Sbf(S,b)=Tf

6、(S,b)=T AaSf(A,a)=Sf(A,a)=S 第三章 正規(guī)式：正規(guī)式：(a|ba)*b T b SA a b a 產(chǎn)生式產(chǎn)生式轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) SaSf(S,a)=Sf(S,a)=S SbAf(S,b)=Af(S,b)=A Sbf(S,b)=Tf(S,b)=T AaSf(A,a)=Sf(A,a)=S 第三章 將將NFA確定化為確定化為DFA 如右圖所示如右圖所示 最小化：此狀態(tài)圖已經(jīng)為最簡(jiǎn)了。最小化：此狀態(tài)圖已經(jīng)為最簡(jiǎn)了。 T b SA a b a S SA,T A,TS IbIaI 0 1 01 0 01 a b a - 第三章 1.指出與正規(guī)式匹配的串。指出與正規(guī)式匹配的串。 a

7、) (ab|b)*c 與后面的那些串匹配？與后面的那些串匹配？ ababbcababcbabcaaabc b) ab*c*(a|b)c 與后面的那些串匹配？與后面的那些串匹配？ acacacbbcabbcacabcacc c) (a|b)aa*(ba)* 與后面的那些串匹配與后面的那些串匹配? ? ba bba baaaaababa 第三章 2. 為下邊所描述的串寫(xiě)正規(guī)式，字母表是為下邊所描述的串寫(xiě)正規(guī)式，字母表是 0, 1. a) 以以01 結(jié)尾的所有串結(jié)尾的所有串 b) 只包含一個(gè)只包含一個(gè)0的所有串的所有串 c) 包含偶數(shù)個(gè)包含偶數(shù)個(gè)1但不含但不含0的所有串的所有串 d) 包含偶數(shù)個(gè)包含

8、偶數(shù)個(gè)1且含任意數(shù)目且含任意數(shù)目0的所有串的所有串 e) 包含包含01子串的所有串子串的所有串 f) 不包含不包含01子串的所有串子串的所有串 (0|1)*01 1*01* (11)* (0*10*10*)* (0|1)*01(0|1)* 1*0* 第三章 3. 請(qǐng)描述下面正規(guī)式定義的串請(qǐng)描述下面正規(guī)式定義的串. 字母表字母表S = x, y。 a) x(x|y)*x 必須以必須以 x 開(kāi)頭和開(kāi)頭和x結(jié)尾的串結(jié)尾的串 b) x*(yx+)*x* 每個(gè)每個(gè) y 至少有一個(gè)至少有一個(gè) x 跟在后邊的串跟在后邊的串 c) (x|y)*(xx|yy) (x|y)* 所有含兩個(gè)相繼的所有含兩個(gè)相繼的x或

9、兩個(gè)相繼的或兩個(gè)相繼的y的串的串 第三章 4.指出哪些串是自動(dòng)機(jī)可接受的指出哪些串是自動(dòng)機(jī)可接受的 xy xyxxy yyyx xyyxyxyxxy 第三章 5.將下圖所示的將下圖所示的 非 確 定 有 限 自非 確 定 有 限 自 動(dòng)機(jī)動(dòng)機(jī)(NFA)變換變換 成 等 價(jià) 的 確 定成 等 價(jià) 的 確 定 有 限 自 動(dòng) 機(jī)有 限 自 動(dòng) 機(jī) (DFA)。 X Y 1 34 2 a b a a b b a b a b 第三章 解解: :用子集法將用子集法將NFA確定化，確定化， 如下圖所示。如下圖所示。 IIaIb X13 2,3,Y3,Y1 3,43 2,3,4,Y2,3,Y2,3,Y 2,

10、3,Y3,43,Y 3,4,Y3,43,4 2,3,4,Y 2,3,4,Y2,3,4,Y 2,3,4,Y3,4,Y3,4,Y ba 012 134 25 336 435 557 666 767 重新命名重新命名 X Y 1 34 2 a b a a b b a b a b 上上圖所對(duì)應(yīng)的圖所對(duì)應(yīng)的DFA如下所示。如下所示。 3 4 5 a a b b a 2 b b 0 1 a 7 b b 6 b a b a a 第三章 ba 012 134 25 336 435 557 666 767 對(duì)上圖的對(duì)上圖的DFA進(jìn)行最小化。首先將進(jìn)行最小化。首先將 狀態(tài)分為非終態(tài)集和終態(tài)集兩部分：狀態(tài)分為非終態(tài)

11、集和終態(tài)集兩部分： 0,1,2,5和和3,4,6,7。 由終態(tài)集可知，對(duì)于狀態(tài)由終態(tài)集可知，對(duì)于狀態(tài)3、6、7， 無(wú)論輸入字符是無(wú)論輸入字符是a還是還是b的下一狀態(tài)的下一狀態(tài) 均為終態(tài)集，而狀態(tài)均為終態(tài)集，而狀態(tài)4在輸入字符在輸入字符b 的下一狀態(tài)落入非終態(tài)集，故將其的下一狀態(tài)落入非終態(tài)集，故將其 化為分化為分0,1,2,5, 4, 3,6,7 第三章 ba 012 134 25 336 435 557 666 767 第三章 對(duì)于非終態(tài)集，在輸入字符對(duì)于非終態(tài)集，在輸入字符a a、 b b后按其下一狀態(tài)落入的狀態(tài)集后按其下一狀態(tài)落入的狀態(tài)集 不同而最終劃分為不同而最終劃分為 0, 1, 2,

12、 5, 4, 3,6,7 按順序重新命名為按順序重新命名為0、1、2、3、 4、5，得到最簡(jiǎn)得到最簡(jiǎn)DFADFA如下圖所示。如下圖所示。 0,1,2,5, 4, 3,6,7 ba 012 134 25 336 435 557 666 767 0 1 2 a b 4 3 5 a a b b b b b a a 3 4 5 a a b b a 2 b b 0 1 a 7 b b 6 b a b a a 6.設(shè)有設(shè)有L(G)=a2n+1b2ma2p+1| n0,p0,m1。 (1) 給出描述該語(yǔ)言的正規(guī)表達(dá)式；給出描述該語(yǔ)言的正規(guī)表達(dá)式； (2) 構(gòu)造識(shí)別該語(yǔ)言的確定有限自動(dòng)機(jī)構(gòu)造識(shí)別該語(yǔ)言的確定有

13、限自動(dòng)機(jī)(可直接用狀可直接用狀 態(tài)圖形式給出態(tài)圖形式給出)。 解：解： (1) 該語(yǔ)言對(duì)應(yīng)的正規(guī)式為該語(yǔ)言對(duì)應(yīng)的正規(guī)式為a(aa)*bb(bb)*a(aa)*。 (2) a(aa)*bb(bb)*a(aa)*正規(guī)表達(dá)式對(duì)應(yīng)的正規(guī)表達(dá)式對(duì)應(yīng)的NFA如如下下 圖所示。圖所示。 第三章 第三章 正規(guī)表達(dá)式：正規(guī)表達(dá)式：a(aa)a(aa)* *bb(bb)bb(bb)* *a(aa)a(aa)* * Y1X ba 34 5 bb ab 6 aa 2 aa II a I b 用子集法將上圖確定化，如圖所示。用子集法將上圖確定化，如圖所示。 X1 2 1 1 2 3 4 5 6 Y Y 3 4 5 4

14、重命名重命名 X 1 2 3 4 Y 5 6 1 2 3 1 Y 6 Y 4 5 4 ab Y6 Y1X ba 34 5 bb ab 6 aa 2 aa 重新命名后的狀態(tài)轉(zhuǎn)換矩陣重新命名后的狀態(tài)轉(zhuǎn)換矩陣 可化簡(jiǎn)為可化簡(jiǎn)為( (可由最小化方法得到可由最小化方法得到) ) X,2 1 3,5 46 Y 按順序重新命名為按順序重新命名為0、1、2、 3、4、5后得到最簡(jiǎn)的后得到最簡(jiǎn)的DFA，如，如 下圖所示。下圖所示。 X 1 2 3 4 Y 5 6 1 2 3 1 Y 6 Y 4 5 4 ab Y1X ba 34 5 bb ab 6 aa 2 aa 第三章 a(aa)*bb(bb)*a(aa)*

15、Y1X ba 34 5 bb ab 6 aa 2 aa 510 ba 23 ab ab 4 aa 7.7.有一臺(tái)自動(dòng)售貨機(jī)，接收有一臺(tái)自動(dòng)售貨機(jī)，接收1 1分和分和2 2分硬幣，出售分硬幣，出售3 3分分 錢一塊的硬糖。顧客每次向機(jī)器中投放錢一塊的硬糖。顧客每次向機(jī)器中投放3 3分的硬幣，分的硬幣， 便可得到一塊糖便可得到一塊糖( (注意：只給一塊并且不找錢注意：只給一塊并且不找錢) )。 (1) (1) 寫(xiě)出售貨機(jī)售糖的正規(guī)表達(dá)式；寫(xiě)出售貨機(jī)售糖的正規(guī)表達(dá)式； (2) (2) 構(gòu)造識(shí)別上述正規(guī)式的最簡(jiǎn)構(gòu)造識(shí)別上述正規(guī)式的最簡(jiǎn)DFADFA。 解解：(1) (1) 設(shè)設(shè)a=1a=1，b=2b=2

16、，則售貨機(jī)售糖的正規(guī)表達(dá)式為，則售貨機(jī)售糖的正規(guī)表達(dá)式為 a (b|a(a|b)|b(a|b)a (b|a(a|b)|b(a|b)。 (2) (2) 畫(huà)出與正規(guī)表達(dá)式畫(huà)出與正規(guī)表達(dá)式a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)對(duì)應(yīng)的對(duì)應(yīng)的 NFANFA，如圖所示。，如圖所示。 第三章 X Y 1 2 3 a b a b b a b a 第三章 正規(guī)表達(dá)式：正規(guī)表達(dá)式：a(b|a(a|b)|b(a|b) II a I b 第三章 用子集法將用子集法將NFA確定化。確定化。 重新命名 Y 3YY 2YY 13Y X12 X Y 1 2 3 a b a b b a b a 4

17、 344 244 134 012 ab 由轉(zhuǎn)換矩陣可看出，非終態(tài)由轉(zhuǎn)換矩陣可看出，非終態(tài)2 2和非終態(tài)和非終態(tài)3 3 面對(duì)輸入符號(hào)面對(duì)輸入符號(hào)a a或或b b的下一狀態(tài)相同，故的下一狀態(tài)相同，故 合并為一個(gè)狀態(tài)合并為一個(gè)狀態(tài) 即最簡(jiǎn)狀態(tài)即最簡(jiǎn)狀態(tài)00、11、22，33、44。 按順序重新命名為按順序重新命名為0 0、1 1、2 2、3 3，則得到，則得到 最簡(jiǎn)最簡(jiǎn)DFADFA，如下圖所示。，如下圖所示。 第三章 4 344 244 134 012 ab 0 3 1 2 a b b b a a 3 233 123 012 ab 第三章 第四章 作業(yè)作業(yè)4.3 設(shè)有文法設(shè)有文法GS: SA AB|

18、AiB BC|B+C C)A*|( 1）將文法）將文法GS改寫(xiě)為改寫(xiě)為L(zhǎng)L(1)文法。文法。 2）求經(jīng)改寫(xiě)后的文法的每個(gè)非終結(jié)符的）求經(jīng)改寫(xiě)后的文法的每個(gè)非終結(jié)符的 FIRST集和集和FOLLOW集。集。 3）構(gòu)造相應(yīng)的預(yù)測(cè)分析表。）構(gòu)造相應(yīng)的預(yù)測(cè)分析表。 第四章 1）將文法）將文法GS改寫(xiě)為改寫(xiě)為L(zhǎng)L(1)文法。文法。 文法文法GS為左遞歸文法，削去文法左遞歸為左遞歸文法，削去文法左遞歸 后的文法為：后的文法為： SA ABA A iBA| BCB B +CB| C)A*|( SA AB|AiB BC|B+C C)A*|( 第四章 1）將文法）將文法GS改寫(xiě)為改寫(xiě)為L(zhǎng)L(1)文法。文法。 F

19、IRST(C)=(,) FIRST(B)=+, FIRST(B)=(,) FIRST(A)=i, FIRST(A)=(,) FIRST(S)=(,) FOLLOW(S)=$ FOLLOW(A)=$,* FOLLOW(A)=$,* FOLLOW(B)=i,$,* FOLLOW(B)=i,$,* FOLLOW(C)=+,i,$,* SA ABA A iBA| BCB B +CB| C)A*|( 第四章 SELECT(SA) =FIRST(A)=(,) SELECT(ABA)=(,) SELECT(AiBA) =i SELECT(A)= FOLLOW(A)= $,* SELECT(BCB)=(,)

20、SELECT(B +CB) =+ SELECT(B)= i, $,* SELECT(C)A*)=) SELECT(C( )= ( 因?yàn)橐驗(yàn)橥环墙K結(jié)符的不同產(chǎn)生式的同一非終結(jié)符的不同產(chǎn)生式的Select集交集為空集交集為空，所以，所以 改寫(xiě)后的文法是改寫(xiě)后的文法是LL(1)文法。文法。 2）求經(jīng)改寫(xiě)后的文法的每個(gè)非終結(jié)符的）求經(jīng)改寫(xiě)后的文法的每個(gè)非終結(jié)符的FIRST集和集和 FOLLOW集。集。 在上步中已經(jīng)求出。在上步中已經(jīng)求出。 FIRST(C)=(,) FIRST(B)=+, FIRST(B)=(,) FIRST(A)=i, FIRST(A)=(,) FIRST(S)=(,) FOLLO

21、W(S)=$ FOLLOW(A)=$,* FOLLOW(A)=$,* FOLLOW(B)=i,$,* FOLLOW(B)=i,$,* FOLLOW(C)=+,i,$,* 3）構(gòu)造相應(yīng)的預(yù)測(cè)分析表。）構(gòu)造相應(yīng)的預(yù)測(cè)分析表。 C)A* B +CB C( B BCBBCBB AiBAA ABAABAA S $*)+i ( 終極符號(hào)終極符號(hào) 語(yǔ)法語(yǔ)法 變量變量 SELECT(SA) = (,) SELECT(ABA)=(,) SELECT(AiBA) =i SELECT(A)= $,* SELECT(BCB)=(,) SELECT(B +CB) =+ SELECT(B)= i, $,* SELECT(

22、C)A*)=) SELECT(C( )= ( C 第四章 作業(yè)作業(yè)4.5 設(shè)有表格結(jié)構(gòu)文法設(shè)有表格結(jié)構(gòu)文法GS: Sa|(T) TT,S|S 1）計(jì)算文法的）計(jì)算文法的FIRSTVT集和集和LASTVT集。集。 2）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算 符優(yōu)先文法。符優(yōu)先文法。 3）計(jì)算其優(yōu)先函數(shù)。）計(jì)算其優(yōu)先函數(shù)。 第四章 1）計(jì)算文法的）計(jì)算文法的FIRSTVT集和集和 LASTVT集。集。 FIRSTVT(S)=a, , ( FIRSTVT(T)=, a, , ( LASTVT(S)=a, , ) LASTVT(T)=, a, ,) 2）構(gòu)造其優(yōu)先關(guān)系表

23、，并判）構(gòu)造其優(yōu)先關(guān)系表，并判 斷其是否為算符優(yōu)先文法。斷其是否為算符優(yōu)先文法。 Sa|(T) TT,S|S = = =( $,) 11111 11111 迭代函迭代函 數(shù)數(shù) 函數(shù)函數(shù)a,() f g 0(初初 值值) f g 1 22213 23331 33313 44241 f g 2 , 第四章 例文法例文法GS S E EaA|bB AcA|d BcB|d 1）構(gòu)造識(shí)別文法活前綴的）構(gòu)造識(shí)別文法活前綴的DFA 2）構(gòu)造其）構(gòu)造其LR(0)分析表分析表 3）輸入串）輸入串a(chǎn)abab是否為文法是否為文法G定義的句子定義的句子 0: S E EaA EbB 4: AcA AcA Ad c 5

24、: BcB BcB Bd c 3: EbB BcB Bd b 1: S E E 2: EaA AcA Ad a 11: Bd d 8: AcA A c c d 10: Ad d d 9: BcB B 6: EaA A 7: EbB B LR(0)分析表為分析表為: s2s31 acc s4s106 s5s117 s4s108 s5s11 r1r1r1r1r1 9 r2r2r2r2r2 r3r3r3r3r3 r5r5r5r5r5 r4r4r4r4r4 r6r6r6r6r6 狀態(tài)狀態(tài) ACTIONGOTO abcd#EAB 0 1 2 3 4 5 6 7 8 9 10 11 S E EaA|bB

25、AcA|d BcB|d (0) S E(1) Ea(2) EbB(3) Ac (4) Ad(5) BcB(6) Bd 輸入串輸入串bccd$的分析過(guò)程的分析過(guò)程 步驟步驟狀態(tài)棧狀態(tài)棧符號(hào)棧符號(hào)棧輸入串輸入串 ACTIONGOTO 1 2 3 4 5 6 7 8 9 0$bccd$S3 03$b ccd$S8 038$bccd$ S8 0388$bccd$ S9 03889$bccd$ $ $ $ $ r611 0388$bccr511 038$bcr57 03 $br21 0$acc B(11) B (11) B 7 E1 第四章 8086/8088匯編語(yǔ)言對(duì)操作數(shù)域的檢查可匯編語(yǔ)言對(duì)操作數(shù)域

26、的檢查可 以用以用LR分析表實(shí)現(xiàn)。設(shè)分析表實(shí)現(xiàn)。設(shè)m代表存儲(chǔ)器，代表存儲(chǔ)器，r 代表寄存器，代表寄存器，i代表立即數(shù)；并且為了簡(jiǎn)代表立即數(shù)；并且為了簡(jiǎn) 單起見(jiàn)，省去了關(guān)于單起見(jiàn)，省去了關(guān)于m、r和和i的產(chǎn)生式，的產(chǎn)生式， 暫且認(rèn)為暫且認(rèn)為m、r、i為終結(jié)符，則操作數(shù)域?yàn)榻K結(jié)符，則操作數(shù)域 P的文法的文法GP為為 GP: Pm,r m,i r,r r,i r,m 試構(gòu)造能夠正確識(shí)別操作數(shù)域的試構(gòu)造能夠正確識(shí)別操作數(shù)域的LR分析表。分析表。 (1) 將文法將文法GS拓廣為文法拓廣為文法GS： (0) SP (1) Pm,r (2) Pm,i (3) Pr,r (4) Pr,i (5) Pr,m 第

27、四章 GP: Pm,r m,i r,r r,i r,m 文法GS的DFA 0: S P Pm,r Pm,i Pr,r Pr,i Pr,m (0) SP (1) Pm,r(2) Pm,i (3) Pr,r (4) Pr,i(5) Pr,m 1: S P P 2: Pm,r Pm,i 3: Pr,r Pr,i Pr,m 5: Pm, r Pm, i 4: Pr, r Pr, i Pr, m , m r , r 6: Pm, r i 7: Pm, i r 8: Pr, r i 9: Pr, i m 10: Pr, m LR(0)分析表分析表 狀態(tài)狀態(tài) ACTIONGOTO mri，$P 0 s2s3

28、 1 1 acc 2 s5 3 s4 4 s10s8s9 5 s6s7 6 r1r1r1r1r1 7 r2r2r2r2r2 8 r3r3r3r3r3 9 r4r4r4r4r4 10 r5r5r5r5r5 r1 (0) SP (1) Pm,r(2) Pm,i (3) Pr,r (4) Pr,i(5) Pr,m 輸入串輸入串m,i$的分析過(guò)程的分析過(guò)程 步驟步驟狀態(tài)棧狀態(tài)棧符號(hào)棧符號(hào)棧輸入串輸入串 ACTIONGOTO 1 2 3 4 5 0$m,i$S2 02$m,i$ S5 025$m, i$ S7 0257$m,i$ r2 0$acc 1P1 例：請(qǐng)指出下圖中的例：請(qǐng)指出下圖中的LRLR分析

29、表分析表(a)(a)、(b)(b)、(c)(c)分屬分屬 LR(0)LR(0)、SLR(1)SLR(1)和和LR(1)LR(1)中的哪一種，并說(shuō)明理由。中的哪一種，并說(shuō)明理由。 (a)(b )(c) 5r 1 4r 2 3r 2 2s 4 5 1acc 0s 3 12 狀態(tài) ACTION GOTO b#SB 4r 1 r 1 r 1 3r 2 r 2 r 2 2s 2 s 3 0s 3 s 2 1 1accg 狀態(tài) ACTIONGOTO ab#T 4r 1 3r 2 2acc 1s 1 s 3 0s 1 2s 3 狀態(tài) ACTIONGOTO ik#P 我們知道，我們知道，LR(0)、SLR(1

30、)和和LR(1)分析表分析表 構(gòu)造的主要差別是構(gòu)造算法。其區(qū)別如下：構(gòu)造的主要差別是構(gòu)造算法。其區(qū)別如下： (1) 對(duì)對(duì)LR(0)分析表來(lái)說(shuō)，若項(xiàng)目分析表來(lái)說(shuō)，若項(xiàng)目A屬屬 于于Ik(狀態(tài)狀態(tài))，則對(duì)，則對(duì)任何終結(jié)符任何終結(jié)符a(包括包括$)，置，置 ACTIONk,a為為“用產(chǎn)生式用產(chǎn)生式A進(jìn)行歸約進(jìn)行歸約 (A為第為第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式)”，簡(jiǎn)記為，簡(jiǎn)記為“rj”。表。表 現(xiàn)在現(xiàn)在ACTION子表中，則是每個(gè)歸約狀態(tài)子表中，則是每個(gè)歸約狀態(tài) 所在的行全部填滿所在的行全部填滿“rj”；并且，；并且，同一行的同一行的 “rj”其下標(biāo)其下標(biāo)j相同，而不同行的相同，而不同行的“rj”其下其下 標(biāo)標(biāo)

31、j是不一樣的。是不一樣的。 (2) (2) 對(duì)對(duì)SLR(1)SLR(1)分析表來(lái)說(shuō)，若項(xiàng)目分析表來(lái)說(shuō)，若項(xiàng)目A A屬于屬于I Ik k， 則對(duì)任何輸入符號(hào)則對(duì)任何輸入符號(hào)a a，僅當(dāng)，僅當(dāng)a aFOLLOW(A)FOLLOW(A)時(shí)置時(shí)置 ACTIONk,aACTIONk,a為為“用產(chǎn)生式用產(chǎn)生式A A進(jìn)行歸約進(jìn)行歸約(A(A 為第為第j j個(gè)產(chǎn)生式個(gè)產(chǎn)生式) )”，簡(jiǎn)記為，簡(jiǎn)記為“r r j j ”。表現(xiàn)在。表現(xiàn)在 ACTIONACTION子表中，則存在某個(gè)歸約狀態(tài)所在的行并子表中，則存在某個(gè)歸約狀態(tài)所在的行并 不全部填滿不全部填滿r rj j，并且不同行的，并且不同行的“r rj j”其下

32、標(biāo)其下標(biāo)j j不同。不同。 第四章 (3) (3) 對(duì)對(duì)LR(1)LR(1)來(lái)說(shuō)，若項(xiàng)目來(lái)說(shuō)，若項(xiàng)目AA,a,a屬于屬于I Ik k( (狀態(tài)狀態(tài)) )， 則置則置ACTIONk,aACTIONk,a為為“用產(chǎn)生式用產(chǎn)生式A A進(jìn)行歸約進(jìn)行歸約”， 簡(jiǎn)記為簡(jiǎn)記為“r rj j”。LR(1)LR(1)是在是在SLR(1)SLR(1)狀態(tài)狀態(tài)( (項(xiàng)目集項(xiàng)目集) )的基的基 礎(chǔ)上，通過(guò)狀態(tài)分裂的辦法礎(chǔ)上，通過(guò)狀態(tài)分裂的辦法( (即分裂成更多的項(xiàng)目即分裂成更多的項(xiàng)目 集集) )，使得，使得LRLR分析器的每個(gè)狀態(tài)能夠確切地指出當(dāng)分析器的每個(gè)狀態(tài)能夠確切地指出當(dāng) 后跟哪些終結(jié)符時(shí)才容許把后跟哪些終結(jié)符

33、時(shí)才容許把歸約為歸約為A A。例如，假定。例如，假定 AA,a,a屬于屬于I Ik k( (狀態(tài)狀態(tài)) )，則置，則置ACTIONk,aACTIONk,a欄目欄目 為為r rj j(A(A為第為第j j個(gè)產(chǎn)生式個(gè)產(chǎn)生式) )；而；而AA,b,b屬于屬于 I Im m( (狀態(tài)狀態(tài)) )，則同樣置，則同樣置ACTIONm,bACTIONm,b欄目為欄目為r rj j。表現(xiàn)在。表現(xiàn)在 ACTIONACTION子表中，則在不同的行子表中，則在不同的行( (即不同的狀態(tài)即不同的狀態(tài)) )里有里有 相同的相同的r rj j存在。存在。 因此，圖因此，圖3-12(a)3-12(a)的分析表為的分析表為L(zhǎng)R

34、(1)LR(1)分析表分析表 ( (在不同行有相同的在不同行有相同的r r2 2存在存在) )；圖；圖3-12(b)3-12(b)為為 LR(0)LR(0)分析表分析表( (有有r rj j的行是每行都填滿了的行是每行都填滿了r rj j 且同一行且同一行r rj j的的j j相同，不同行相同，不同行r rj j的的j j不同不同) )； 而圖而圖3-12(c)3-12(c)為為L(zhǎng)R(0)LR(0)分析表分析表( (存在并不全存在并不全 部填滿部填滿r rj j的行，且不同行的行，且不同行r rj j的的j j不同不同) )。 第四章 第五章 1 1、表達(dá)式表達(dá)式( (A AB)B)(C(CD

35、)D)的逆波蘭表示為的逆波蘭表示為 。 2 2、有一語(yǔ)法制導(dǎo)翻譯如下所示：、有一語(yǔ)法制導(dǎo)翻譯如下所示： S SbAb printbAb print1 1 A A(B print(B print2 2 A Aa printa print3 3 B BAa) printAa) print4 4 若輸入序列為若輸入序列為b(aa)a)a)bb(aa)a)a)b，且采用自下而上，且采用自下而上 的分析方法，則輸出序列為的分析方法，則輸出序列為 。34242421 ABCD 3 3、給出文法、給出文法GS: GS: S SSaA|ASaA|AA AAbB|BAbB|BB BcSd|ecSd|e 請(qǐng)證實(shí)請(qǐng)證實(shí)AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一個(gè)句型；的一個(gè)句型； 請(qǐng)寫(xiě)出該句型的所有短語(yǔ)、素短語(yǔ)以及句柄；請(qǐng)寫(xiě)出該句型的所有短語(yǔ)、素短語(yǔ)以及句柄； 為文法為文法GSGS的每個(gè)產(chǎn)生式寫(xiě)出相應(yīng)的翻譯子程的每個(gè)產(chǎn)生式寫(xiě)出相應(yīng)的翻譯子程 序，使句型序，使句型AacAbcBaAdbedAacAbcBaAdbed經(jīng)該翻譯方案經(jīng)該翻譯方案歸約歸約 后，輸出為后，輸出為131042521430131042521430。 第五章 第五章