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

《編譯原理習(xí)題與答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理習(xí)題與答案（59頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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 0DDD01DD012D0123N ND N3ND3 N23ND23N123D12301232.5證明下面的文法是二義性的。證明下面的文法是二義性的。SiSeS|iS|i答：對(duì)句子答：對(duì)句子iiiei對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)第二章SiSSeiSiiSiSSeiSii2.9設(shè)有文法設(shè)有文法GT:TT*F|F FFP|PP(T)|i分析句型分析句型T*P(T*F)的

2、短語(yǔ)、直接短語(yǔ)和句柄的短語(yǔ)、直接短語(yǔ)和句柄答：句型答：句型T*P(T*F)的語(yǔ)法樹(shù)：的語(yǔ)法樹(shù)：TTF*()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第二章PFPTF*第三章3.1構(gòu)造正規(guī)式構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的相應(yīng)的NFAX1B1C10DYA(0|1)*X1B1C10DYAE0|1X1B1C10D

3、YAE0,1第三章3.1構(gòu)造正規(guī)式構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的相應(yīng)的NFAX11B10CYA(0|1)*0,1X11B10CYAX1B1C10DYAE0,1第三章3.5給出下述文法所對(duì)應(yīng)的正規(guī)式。給出下述文法所對(duì)應(yīng)的正規(guī)式。G：SaAAbA|aB|bBaA解：先由產(chǎn)生式得解：先由產(chǎn)生式得:B=aA將將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|bAaS解

4、解：由文法到由文法到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利用規(guī)則利用規(guī)則（A-xA|y）得得:S=(a|ba)*b文文法法G對(duì)對(duì)應(yīng)應(yīng)的的正正規(guī)規(guī)式式為為(a|ba)*b，其其對(duì)對(duì)應(yīng)應(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|bAaS解解：由文法直接到由文法直接到NFA文法對(duì)應(yīng)的有自動(dòng)文法對(duì)應(yīng)的有自動(dòng)M=(S,A,T,a,b,f

5、,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)=SSbAf(S,bf(S,b)=A)=ASbf(S,bf(S,b)=T)=TAaSf(A,af(A,a)=S)=S第三章正規(guī)式：正規(guī)式：(a|ba)*bTbSAaba產(chǎn)生式產(chǎn)生式轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)SaSf(S,a)=Sf(S,a)=SSbAf(S,bf(S,b)=A)=ASbf(S,bf(S,b)=T)=TAaSf(A,af(A,a)=S)=S第三章將將NFA確定化為確定化為DFA如右圖所示如右圖所示最小化：此狀態(tài)圖已經(jīng)為最簡(jiǎn)了。最小化：此狀態(tài)圖已經(jīng)為最簡(jiǎn)了。TbSAabaSSA

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

7、但不含0的所有串的所有串d)包含偶數(shù)個(gè)包含偶數(shù)個(gè)1且含任意數(shù)目且含任意數(shù)目0的所有串的所有串e)包含包含01子串的所有串子串的所有串f)不包含不包含01子串的所有串子串的所有串(0|1)*011*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或兩個(gè)相繼的或兩個(gè)相繼的y

8、的串的串 第三章4.指出哪些串是自動(dòng)機(jī)可接受的指出哪些串是自動(dòng)機(jī)可接受的xyxyxxyyyyxxyyxyxyxxy第三章5.將將下下圖圖所所示示的的非非確確定定有有限限自自動(dòng)動(dòng)機(jī)機(jī)(NFA)變變換換成成等等價(jià)價(jià)的的確確定定有有限限自動(dòng)機(jī)自動(dòng)機(jī)(DFA)。第三章解解:用用子子集集法法將將NFA確確定定化化，如如下圖所示。下圖所示。IIaIbX132,3,Y3,Y13,432,3,4,Y2,3,Y2,3,Y2,3,Y3,43,Y3,4,Y3,43,42,3,4,Y2,3,4,Y2,3,4,Y2,3,4,Y3,4,Y3,4,Yba01213425336435557666767重新命名重新命名 上上圖

9、所對(duì)應(yīng)的圖所對(duì)應(yīng)的DFA如下所示。如下所示。第三章ba01213425336435557666767對(duì)對(duì)上上圖圖的的DFA進(jìn)進(jìn)行行最最小小化化。首首先先將將狀狀態(tài)態(tài)分分為為非非終終態(tài)態(tài)集集和和終終態(tài)態(tài)集集兩兩部部分分：0,1,2,5和和3,4,6,7。由由終終態(tài)態(tài)集集可可知知，對(duì)對(duì)于于狀狀態(tài)態(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第三章ba01213425336435557666767第三章對(duì)對(duì)于于非非終

10、終態(tài)態(tài)集集，在在輸輸入入字字符符a a、b b后后按按其其下下一一狀狀態(tài)態(tài)落落入入的的狀狀態(tài)態(tài)集集不同而最終劃分為不同而最終劃分為0,1,2,5,4,3,6,7按按順順序序重重新新命命名名為為0、1、2、3、4、5，得到最簡(jiǎn)得到最簡(jiǎn)DFADFA如下圖所示。如下圖所示。0,1,2,5,4,3,6,7ba012134253364355576667676.設(shè)有設(shè)有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)給出描述該語(yǔ)言的正規(guī)表達(dá)式；給出描述該語(yǔ)言的正規(guī)表達(dá)式；(2)構(gòu)構(gòu)造造識(shí)識(shí)別別該該語(yǔ)語(yǔ)言言的的確確定定有有限限自自動(dòng)動(dòng)機(jī)機(jī)(可可直直接接用用狀狀態(tài)圖形式給出態(tài)圖形式給出)。解：解

11、：(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ī)規(guī)表表達(dá)達(dá)式式對(duì)對(duì)應(yīng)應(yīng)的的NFA如如下下圖所示。圖所示。第三章第三章正規(guī)表達(dá)式：正規(guī)表達(dá)式：a(aaa(aa)*bb(bbbb(bb)*a(aaa(aa)*IIaIb用子集法將上圖確定化，如圖所示。用子集法將上圖確定化，如圖所示。X121123456YY3454重命名重命名X1234Y561231Y6Y454abY6重重新新命命名名后后的的狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)換換矩矩陣陣可化簡(jiǎn)為可化簡(jiǎn)為(可由最小化方法得到可由最小化方法得到)X,213,546Y按順序重新命名為按順

12、序重新命名為0、1、2、3、4、5后得到最簡(jiǎn)的后得到最簡(jiǎn)的DFA，如，如下圖所示。下圖所示。X1234Y561231Y6Y454ab第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa7.7.有有一一臺(tái)臺(tái)自自動(dòng)動(dòng)售售貨貨機(jī)機(jī)，接接收收1 1分分和和2 2分分硬硬幣幣，出出售售3 3分分錢(qián)錢(qián)一一塊塊的的硬硬糖糖。顧顧客客每每次次向向機(jī)機(jī)器器中中投投放放3 3分分的的硬硬幣幣，便可得到一塊糖便可得到一塊糖(注意：只給一塊并且不找錢(qián)注意：只給一塊并且不找錢(qián))。(1)(1)寫(xiě)出售貨機(jī)售糖的正規(guī)表達(dá)式；寫(xiě)出售貨機(jī)售糖的正規(guī)表達(dá)式；(2)(2)構(gòu)造識(shí)

13、別上述正規(guī)式的最簡(jiǎn)構(gòu)造識(shí)別上述正規(guī)式的最簡(jiǎn)DFADFA。解解：(1)(1)設(shè)設(shè)a=1a=1，b=2b=2，則售貨機(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à)畫(huà)出出與與正正規(guī)規(guī)表表達(dá)達(dá)式式a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)對(duì)對(duì)應(yīng)應(yīng)的的NFANFA，如圖所示。如圖所示。第三章第三章正規(guī)表達(dá)式：正規(guī)表達(dá)式：a(b|a(a|b)|b(a|b)IIaIb第三章用子集法將用子集法將NFA確定化。確定化。重新命名Y3YY2YY13YX124344244134012ab由由轉(zhuǎn)轉(zhuǎn)換換矩矩陣陣可

14、可看看出出，非非終終態(tài)態(tài)2 2和和非非終終態(tài)態(tài)3 3面面對(duì)對(duì)輸輸入入符符號(hào)號(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，如下圖所示。，如下圖所示。第三章4344244134012ab0312abbbaa3233123012ab第三章第四章作業(yè)作業(yè)4.3設(shè)有文法設(shè)有文法GS:SAAB|AiBBC|B+CC)A*|(1）將文法）將文法GS改寫(xiě)為改寫(xiě)為L(zhǎng)L(1)文法。文法。2）求經(jīng)改寫(xiě)后的文法的每個(gè)非終結(jié)符的）求經(jīng)改寫(xiě)后

15、的文法的每個(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為左遞歸文法，削去文法左遞歸為左遞歸文法，削去文法左遞歸后的文法為：后的文法為：SAABAAiBA|BCBB+CB|C)A*|(SAAB|AiBBC|B+CC)A*|(第四章1）將文法）將文法GS改寫(xiě)為改寫(xiě)為L(zhǎng)L(1)文法。文法。FIRST(C)=(,)FIRST(B)=+,FIRST(B)=(,)FIRST(A)=i,FIRST(A)=(,)FIRST(S)=(,)FOLLOW(S)=$FOLLOW(A)=$,

16、*FOLLOW(A)=$,*FOLLOW(B)=i,$,*FOLLOW(B)=i,$,*FOLLOW(C)=+,i,$,*SA ABAAiBA|BCBB+CB|C)A*|(第四章SELECT(SA)=FIRST(A)=(,)SELECT(ABA)=(,)SELECT(AiBA)=iSELECT(A)=FOLLOW(A)=$,*SELECT(BCB)=(,)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ě)后的文法是

17、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)=(,)FOLLOW(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è)分析表。BBBBC)A*B+CBBBC(BBCBBCBBAAAAAiBAAABAAB

18、AAS$*)+i(終極符號(hào)終極符號(hào)語(yǔ)法語(yǔ)法變量變量SASASASASELECT(SA)=(,)SELECT(ABA)=(,)SELECT(AiBA)=iSELECT(A)=$,*SELECT(BCB)=(,)SELECT(B+CB)=+SELECT(B)=i,$,*SELECT(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)

19、先函數(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)系表，并判）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算符優(yōu)先文法。斷其是否為算符優(yōu)先文法。Sa|(T)TT,S|S=($,)1111111111迭代函迭代函數(shù)數(shù)函數(shù)函數(shù)a,()fg0(初初值值)fg122213233313331344241fg2,第四章例文法例文法GSS EEaA|bBAcA|dBcB|d 1）構(gòu)造）構(gòu)造識(shí)別識(shí)別文法活前文法活前綴綴的的DFA2）構(gòu)造其）構(gòu)造其LR(0)分析表分

20、析表3）輸輸入串入串a(chǎn)abab是否是否為為文法文法G定定義義的句子的句子0:S EEaAEbB4:AcAAcAAdc5:BcBBcBBdc3:EbBBcBBdb1:S EE2:EaAAcAAda11:Bdd8:AcAAccd10:Addd9:BcBB6:EaAA7:EbBBLR(0)分析表為分析表為:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6狀態(tài)狀態(tài)ACTIONGOTOabcd#EAB01234567891011S EEaA|bBAcA|dBcB|d(0

21、)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)棧輸入串輸入串 ACTIONGOTO1234567890$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E1第四章8086/8088匯匯編編語(yǔ)語(yǔ)言言對(duì)對(duì)操操作作數(shù)數(shù)域域的的檢檢查查可可以以用用LR分分析析表表實(shí)實(shí)現(xiàn)現(xiàn)。設(shè)設(shè)m代代表表存存儲(chǔ)儲(chǔ)器器，r代代表表寄寄存存器器，i代代表表立立即即數(shù)數(shù)；并并且且

22、為為了了簡(jiǎn)簡(jiǎn)單單起起見(jiàn)見(jiàn)，省省去去了了關(guān)關(guān)于于m、r和和i的的產(chǎn)產(chǎn)生生式式，暫暫且且認(rèn)認(rèn)為為m、r、i為為終終結(jié)結(jié)符符，則則操操作作數(shù)數(shù)域域P的文法的文法GP為為GP:Pm,r m,i r,r r,i r,m試試構(gòu)造能構(gòu)造能夠夠正確正確識(shí)別識(shí)別操作數(shù)域的操作數(shù)域的LR分析表。分析表。(1)將文法將文法GS拓廣拓廣為為文法文法GS：(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m第四章GP:Pm,r m,i r,r r,i r,m文法GS的DFA0:S PPm,rPm,iPr,rPr,iPr,m(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5

23、)Pr,m1:S PP2:Pm,rPm,i3:Pr,rPr,iPr,m5:Pm,rPm,i4:Pr,rPr,iPr,m,mr,r6:Pm,ri7:Pm,ir8:Pr,ri9:Pr,im10:Pr,mLR(0)分析表分析表狀態(tài)狀態(tài)ACTIONGOTOmri，$P0s2s311acc2s53s44s10s8s95s6s76r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r4r4r4r4r410r5r5r5r5r5r1(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)棧輸入串輸入串

24、ACTIONGOTO123450$m,i$S202$m,i$S5025$m,i$S70257$m,i$r20$acc1P1例例：請(qǐng)請(qǐng)指指出出下下圖圖中中的的LRLR分分析析表表(a)(a)、(b)(b)、(c)(c)分分屬屬LR(0)LR(0)、SLR(1)SLR(1)和和LR(1)LR(1)中的哪一種，并說(shuō)明理由。中的哪一種，并說(shuō)明理由。我我們們知知道道，LR(0)、SLR(1)和和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é)符

25、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è)歸約狀子表中，則是每個(gè)歸約狀態(tài)所在的行全部填滿態(tài)所在的行全部填滿“rj”；并且，并且，同一同一行的行的“rj”其下標(biāo)其下標(biāo)j相同，而不同行的相同，而不同行的“rj”其下標(biāo)其下標(biāo)j是不一樣的。是不一樣的。(2)(2)對(duì)對(duì)SLR(1)SLR(1)分分析析表表來(lái)來(lái)說(shuō)說(shuō)，若若項(xiàng)項(xiàng)目目A A屬屬于于I Ik k，則則對(duì)對(duì)任任何何輸輸入入符符號(hào)號(hào)a a，僅僅當(dāng)當(dāng)a aFOLLOW(A)FOLLOW(A)時(shí)時(shí)置置ACTIONk,

26、aACTIONk,a為為“用用產(chǎn)產(chǎn)生生式式A A進(jìn)進(jìn)行行歸歸約約(A(A為為第第j j個(gè)個(gè)產(chǎn)產(chǎn)生生式式)”，簡(jiǎn)簡(jiǎn)記記為為“r rj j”。表表現(xiàn)現(xiàn)在在ACTIONACTION子子表表中中，則則存存在在某某個(gè)個(gè)歸歸約約狀狀態(tài)態(tài)所所在在的的行行并并不不全全部部填填滿滿r rj j，并且不同行的并且不同行的“r rj j”其下標(biāo)其下標(biāo)j j不同。不同。第四章(3)(3)對(duì)對(duì)LR(1)LR(1)來(lái)來(lái)說(shuō)說(shuō)，若若項(xiàng)項(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)

27、是是在在SLR(1)SLR(1)狀狀態(tài)態(tài)(項(xiàng)項(xiàng)目目集集)的的基基礎(chǔ)礎(chǔ)上上，通通過(guò)過(guò)狀狀態(tài)態(tài)分分裂裂的的辦辦法法(即即分分裂裂成成更更多多的的項(xiàng)項(xiàng)目目集集)，使使得得LRLR分分析析器器的的每每個(gè)個(gè)狀狀態(tài)態(tài)能能夠夠確確切切地地指指出出當(dāng)當(dāng)后后跟跟哪哪些些終終結(jié)結(jié)符符時(shí)時(shí)才才容容許許把把歸歸約約為為A A。例例如如，假假定定AA,a,a屬屬于于I Ik k(狀狀態(tài)態(tài))，則則置置ACTIONk,aACTIONk,a欄欄目目為為r rj j(A(A為為第第j j個(gè)個(gè)產(chǎn)產(chǎn)生生式式)；而而AA,b,b屬屬于于I Im m(狀狀態(tài)態(tài))，則則同同樣樣置置ACTIONm,bACTIONm,b欄欄目目為為r rj

28、 j。表表現(xiàn)現(xiàn)在在ACTIONACTION子子表表中中，則則在在不同的行不同的行(即不同的狀態(tài)即不同的狀態(tài))里有相同的里有相同的r rj j存在。存在。因因此此，圖圖3-12(a)3-12(a)的的分分析析表表為為L(zhǎng)R(1)LR(1)分分析析表表(在在不不同同行行有有相相同同的的r r2 2存存在在)；圖圖3-12(b)3-12(b)為為L(zhǎng)R(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)分分析析

29、表表(存存在在并并不不全全部部填填滿滿r rj j的行，且不同行的行，且不同行r rj j的的j j不同不同)。第四章第五章1 1、表達(dá)式表達(dá)式(A AB)B)(C(CD)D)的逆波蘭表示為的逆波蘭表示為 。2 2、有一語(yǔ)法制導(dǎo)翻譯如下所示：、有一語(yǔ)法制導(dǎo)翻譯如下所示：S SbAbbAb print print1 1 A A(B print(B print2 2 A Aa a print print3 3 B BAaAa)print)print4 4 若若輸輸入入序序列列為為b(aa)a)a)bb(aa)a)a)b，且且采采用用自自下下而而上上的分析方法，則輸出序列為的分析方法，則輸出序列為

30、。34242421ABCD3 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è)個(gè)產(chǎn)產(chǎn)生生式式寫(xiě)寫(xiě)出出相相應(yīng)應(yīng)的的翻翻譯譯子子程程序序，使使句句型型AacAbcBaAdbedAacAbcBaAdbed經(jīng)經(jīng)該該翻翻譯譯方方案案歸歸約約后，輸出為后，輸出為131042521430131042521430。第五章第五章(1)

31、(1)根根據(jù)據(jù)文文法法GSGS畫(huà)畫(huà)出出AacAbcBaAdbedAacAbcBaAdbed對(duì)對(duì)應(yīng)應(yīng)的的語(yǔ)法樹(shù)如圖所示。語(yǔ)法樹(shù)如圖所示。由由圖圖可可知知AacAbcBaAdbedAacAbcBaAdbed是是文文法法GSGS的一個(gè)句型。的一個(gè)句型。圖圖AacAbcBaAdbed對(duì)應(yīng)的語(yǔ)法樹(shù)對(duì)應(yīng)的語(yǔ)法樹(shù)第五章(2)(2)由由圖圖可可知知，句句型型AacAbcBaAdbedAacAbcBaAdbed中的短語(yǔ)為：中的短語(yǔ)為：B,B,BaABaA,cBaAdcBaAd,AbcBaAdAbcBaAd,e,e,AbcBaAdbeAbcBaAdbe,cAbcBaAdbedcAbcBaAdbed,A,A,Aac

32、AbcBaAdbedAacAbcBaAdbed第五章從從 圖圖 可可 看看 出出，句句 型型AacAbcBaAdbedAacAbcBaAdbed的的素短語(yǔ)為：素短語(yǔ)為：BaABaA和和e e。句柄句柄(最左直接短語(yǔ)最左直接短語(yǔ))為：為：A A。(3)(3)采采用用修修剪剪語(yǔ)語(yǔ)法法樹(shù)樹(shù)的的辦辦法法，按按句句柄柄方方式式自自下下而而上上歸歸約約，每每當(dāng)當(dāng)一一個(gè)個(gè)產(chǎn)產(chǎn)生生式式得得到到匹匹配配時(shí)時(shí)，則則按按歸歸約約的的先先后后順序與所給的輸出順序與所給的輸出131042521430131042521430順序進(jìn)行對(duì)應(yīng)。順序進(jìn)行對(duì)應(yīng)。如如：第第一一個(gè)個(gè)句句柄柄為為A A，它它所所對(duì)對(duì)應(yīng)應(yīng)的的產(chǎn)產(chǎn)生生式式

33、為為S SA A，所所以以它它的的語(yǔ)語(yǔ)義義動(dòng)動(dòng)作作應(yīng)應(yīng)為為print(print(1 1)；修修剪剪后后第第二二次次找找到到的的句句柄柄為為B,B,它它所所對(duì)對(duì)應(yīng)應(yīng)的的產(chǎn)產(chǎn)生生式式為為A AB B，此此時(shí)時(shí)它它對(duì)對(duì)應(yīng)應(yīng)輸輸出出序序列列中中的的“3 3”，即即它它的的語(yǔ)語(yǔ)義義動(dòng)動(dòng)作作為為print(print(3 3)，依依此此類類推推，得得到到每每個(gè)個(gè)產(chǎn)產(chǎn)生生式式相相應(yīng)應(yīng)的的語(yǔ)義動(dòng)作如下：語(yǔ)義動(dòng)作如下：第五章第五章SSaAprint(0)SAprint(1)AAbBprint(2)ABprint(3)BcSdprint(4)Beprint(5)句型句型AacAbcBaAdbed經(jīng)該翻譯方經(jīng)該翻譯方案歸約后，輸出為案歸約后，輸出為131042521430