編譯原理習題與答案

第二章2.2設有文法設有文法GN:N-D|NDD-0|1|9(1)GN定義的語言是什么？定義的語言是什么？(2)請給出句子請給出句子0123的最左推導和最右推導。的最左推導和最右推導。N ND NDD NDDDDDDD 0DDD01DD012D0123N ND N3ND3 N23ND23N123D12301232.5證明下面的文法是二義性的。證明下面的文法是二義性的。SiSeS|iS|i答：對句子答：對句子iiiei對應兩棵不同的語法樹對應兩棵不同的語法樹第二章SiSSeiSiiSiSSeiSii2.9設有文法設有文法GT:TT*F|F FFP|PP(T)|i分析句型分析句型T*P(T*F)的短語、直接短語和句柄的短語、直接短語和句柄答：句型答：句型T*P(T*F)的語法樹：的語法樹：TTF*()T五棵子樹對應五個短語五棵子樹對應五個短語T*P(T*F),P(T*F),P,(T*F),T*F兩層子樹兩層子樹(簡單子樹簡單子樹)的末端結(jié)點構(gòu)成直接短語的末端結(jié)點構(gòu)成直接短語 兩棵兩層子樹對應兩個直接短語：兩棵兩層子樹對應兩個直接短語：P,T*F位于最左邊的兩層子樹的末端結(jié)點構(gòu)成句柄：位于最左邊的兩層子樹的末端結(jié)點構(gòu)成句柄：P第二章PFPTF*第三章3.1構(gòu)造正規(guī)式構(gòu)造正規(guī)式1(0|1)*101相應的相應的NFAX1B1C10DYA(0|1)*X1B1C10DYAE0|1X1B1C10DYAE0,1第三章3.1構(gòu)造正規(guī)式構(gòu)造正規(guī)式1(0|1)*101相應的相應的NFAX11B10CYA(0|1)*0,1X11B10CYAX1B1C10DYAE0,1第三章3.5給出下述文法所對應的正規(guī)式。給出下述文法所對應的正規(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)造相應最小的，構(gòu)造相應最小的DFA。G：SaS|bA|bAaS解解：由文法到由文法到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對對應應的的正正規(guī)規(guī)式式為為(a|ba)*b，其其對對應應的的NFA的狀態(tài)轉(zhuǎn)換圖為的狀態(tài)轉(zhuǎn)換圖為：第三章3.4給出文法給出文法GS，構(gòu)造相，構(gòu)造相應最小的應最小的DFA。G：SaS|bA|bAaS解解：由文法直接到由文法直接到NFA文法對應的有自動文法對應的有自動M=(S,A,T,a,b,f,S,T)其對應的狀態(tài)轉(zhuǎn)換圖為：其對應的狀態(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)為最簡了。最小化：此狀態(tài)圖已經(jīng)為最簡了。TbSAabaSSA,TA,TSIbIaI0101001aba-第三章1.指出與正規(guī)式匹配的串。指出與正規(guī)式匹配的串。a)(ab|b)*c與后面的那些串匹配？與后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a|b)c與后面的那些串匹配？與后面的那些串匹配？acacacbbcabbcacabcaccc)(a|b)aa*(ba)*與后面的那些串匹配與后面的那些串匹配?babbabaaaaababa第三章2.為下邊所描述的串寫正規(guī)式，字母表是為下邊所描述的串寫正規(guī)式，字母表是0,1.a)以以01結(jié)尾的所有串結(jié)尾的所有串b)只包含一個只包含一個0的所有串的所有串c)包含偶數(shù)個包含偶數(shù)個1但不含但不含0的所有串的所有串d)包含偶數(shù)個包含偶數(shù)個1且含任意數(shù)目且含任意數(shù)目0的所有串的所有串e)包含包含01子串的所有串子串的所有串f)不包含不包含01子串的所有串子串的所有串(0|1)*011*01*(11)*(0*10*10*)*(0|1)*01(0|1)*1*0*第三章3.請描述下面正規(guī)式定義的串請描述下面正規(guī)式定義的串.字母表字母表S=x,y。a)x(x|y)*x必須以必須以x開頭和開頭和x結(jié)尾的串結(jié)尾的串b)x*(yx+)*x*每個每個y至少有一個至少有一個x跟在后邊的串跟在后邊的串c)(x|y)*(xx|yy)(x|y)*所有含兩個相繼的所有含兩個相繼的x或兩個相繼的或兩個相繼的y的串的串 第三章4.指出哪些串是自動機可接受的指出哪些串是自動機可接受的xyxyxxyyyyxxyyxyxyxxy第三章5.將將下下圖圖所所示示的的非非確確定定有有限限自自動動機機(NFA)變變換換成成等等價價的的確確定定有有限限自動機自動機(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重新命名重新命名 上上圖所對應的圖所對應的DFA如下所示。如下所示。第三章ba01213425336435557666767對對上上圖圖的的DFA進進行行最最小小化化。首首先先將將狀狀態(tài)態(tài)分分為為非非終終態(tài)態(tài)集集和和終終態(tài)態(tài)集集兩兩部部分分：0,1,2,5和和3,4,6,7。由由終終態(tài)態(tài)集集可可知知，對對于于狀狀態(tài)態(tài)3、6、7，無無論論輸輸入入字字符符是是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第三章對對于于非非終終態(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，得到最簡得到最簡DFADFA如下圖所示。如下圖所示。0,1,2,5,4,3,6,7ba012134253364355576667676.設有設有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)給出描述該語言的正規(guī)表達式；給出描述該語言的正規(guī)表達式；(2)構(gòu)構(gòu)造造識識別別該該語語言言的的確確定定有有限限自自動動機機(可可直直接接用用狀狀態(tài)圖形式給出態(tài)圖形式給出)。解：解：(1)該語言對應的正規(guī)式為該語言對應的正規(guī)式為a(aa)*bb(bb)*a(aa)*。(2)a(aa)*bb(bb)*a(aa)*正正規(guī)規(guī)表表達達式式對對應應的的NFA如如下下圖所示。圖所示。第三章第三章正規(guī)表達式：正規(guī)表達式：a(aaa(aa)*bb(bbbb(bb)*a(aaa(aa)*IIaIb用子集法將上圖確定化，如圖所示。用子集法將上圖確定化，如圖所示。X121123456YY3454重命名重命名X1234Y561231Y6Y454abY6重重新新命命名名后后的的狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)換換矩矩陣陣可化簡為可化簡為(可由最小化方法得到可由最小化方法得到)X,213,546Y按順序重新命名為按順序重新命名為0、1、2、3、4、5后得到最簡的后得到最簡的DFA，如，如下圖所示。下圖所示。X1234Y561231Y6Y454ab第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa7.7.有有一一臺臺自自動動售售貨貨機機，接接收收1 1分分和和2 2分分硬硬幣幣，出出售售3 3分分錢錢一一塊塊的的硬硬糖糖。顧顧客客每每次次向向機機器器中中投投放放3 3分分的的硬硬幣幣，便可得到一塊糖便可得到一塊糖(注意：只給一塊并且不找錢注意：只給一塊并且不找錢)。(1)(1)寫出售貨機售糖的正規(guī)表達式；寫出售貨機售糖的正規(guī)表達式；(2)(2)構(gòu)造識別上述正規(guī)式的最簡構(gòu)造識別上述正規(guī)式的最簡DFADFA。解解：(1)(1)設設a=1a=1，b=2b=2，則售貨機售糖的正規(guī)表達式為則售貨機售糖的正規(guī)表達式為a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)。(2)(2)畫畫出出與與正正規(guī)規(guī)表表達達式式a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)對對應應的的NFANFA，如圖所示。如圖所示。第三章第三章正規(guī)表達式：正規(guī)表達式：a(b|a(a|b)|b(a|b)IIaIb第三章用子集法將用子集法將NFA確定化。確定化。重新命名Y3YY2YY13YX124344244134012ab由由轉(zhuǎn)轉(zhuǎn)換換矩矩陣陣可可看看出出，非非終終態(tài)態(tài)2 2和和非非終終態(tài)態(tài)3 3面面對對輸輸入入符符號號a a或或b b的的下下一一狀狀態(tài)態(tài)相相同同，故故合并為一個狀態(tài)合并為一個狀態(tài)即最簡狀態(tài)即最簡狀態(tài)00、11、22，33、44。按按順順序序重重新新命命名名為為0 0、1 1、2 2、3 3，則則得得到到最簡最簡DFADFA，如下圖所示。，如下圖所示。第三章4344244134012ab0312abbbaa3233123012ab第三章第四章作業(yè)作業(yè)4.3設有文法設有文法GS:SAAB|AiBBC|B+CC)A*|(1）將文法）將文法GS改寫為改寫為LL(1)文法。文法。2）求經(jīng)改寫后的文法的每個非終結(jié)符的）求經(jīng)改寫后的文法的每個非終結(jié)符的FIRST集和集和FOLLOW集。集。3）構(gòu)造相應的預測分析表。）構(gòu)造相應的預測分析表。第四章1）將文法）將文法GS改寫為改寫為LL(1)文法。文法。文法文法GS為左遞歸文法，削去文法左遞歸為左遞歸文法，削去文法左遞歸后的文法為：后的文法為：SAABAAiBA|BCBB+CB|C)A*|(SAAB|AiBBC|B+CC)A*|(第四章1）將文法）將文法GS改寫為改寫為LL(1)文法。文法。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,$,*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()=(因為因為同一非終結(jié)符的不同產(chǎn)生式的同一非終結(jié)符的不同產(chǎn)生式的Select集交集為空集交集為空，所以，所以改寫后的文法是改寫后的文法是LL(1)文法。文法。2）求經(jīng)改寫后的文法的每個非終結(jié)符的）求經(jīng)改寫后的文法的每個非終結(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)造相應的預測分析表。）構(gòu)造相應的預測分析表。BBBBC)A*B+CBBBC(BBCBBCBBAAAAAiBAAABAABAAS$*)+i(終極符號終極符號語法語法變量變量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設有表格結(jié)構(gòu)文法設有表格結(jié)構(gòu)文法GS:Sa|(T)TT,S|S 1）計算文法的）計算文法的FIRSTVT集和集和LASTVT集。集。2）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算）構(gòu)造其優(yōu)先關(guān)系表，并判斷其是否為算符優(yōu)先文法。符優(yōu)先文法。3）計算其優(yōu)先函數(shù)。）計算其優(yōu)先函數(shù)。第四章1）計算文法的）計算文法的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)造識別識別文法活前文法活前綴綴的的DFA2）構(gòu)造其）構(gòu)造其LR(0)分析表分析表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)S E(1)Ea(2)EbB(3)Ac(4)Ad(5)BcB(6)Bd輸入串輸入串bccd$的分析過程的分析過程步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧輸入串輸入串 ACTIONGOTO1234567890$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E1第四章8086/8088匯匯編編語語言言對對操操作作數(shù)數(shù)域域的的檢檢查查可可以以用用LR分分析析表表實實現(xiàn)現(xiàn)。設設m代代表表存存儲儲器器，r代代表表寄寄存存器器，i代代表表立立即即數(shù)數(shù)；并并且且為為了了簡簡單單起起見見，省省去去了了關(guān)關(guān)于于m、r和和i的的產(chǎn)產(chǎ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ù)域的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)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$的分析過程的分析過程步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧輸入串輸入串 ACTIONGOTO123450$m,i$S202$m,i$S5025$m,i$S70257$m,i$r20$acc1P1例例：請請指指出出下下圖圖中中的的LRLR分分析析表表(a)(a)、(b)(b)、(c)(c)分分屬屬LR(0)LR(0)、SLR(1)SLR(1)和和LR(1)LR(1)中的哪一種，并說明理由。中的哪一種，并說明理由。我我們們知知道道，LR(0)、SLR(1)和和LR(1)分分析析表表構(gòu)造的主要差別是構(gòu)造算法。其區(qū)別如下：構(gòu)造的主要差別是構(gòu)造算法。其區(qū)別如下：(1)對對LR(0)分析表來說，若項目分析表來說，若項目A屬屬于于Ik(狀態(tài)狀態(tài))，則對，則對任何終結(jié)符任何終結(jié)符a(包括包括$)，置，置ACTIONk,a為為“用產(chǎn)生式用產(chǎn)生式A進行歸約進行歸約(A為第為第j個產(chǎn)生式個產(chǎn)生式)”，簡記為，簡記為“rj”。表現(xiàn)在表現(xiàn)在ACTION子表中，則是每個歸約狀子表中，則是每個歸約狀態(tài)所在的行全部填滿態(tài)所在的行全部填滿“rj”；并且，并且，同一同一行的行的“rj”其下標其下標j相同，而不同行的相同，而不同行的“rj”其下標其下標j是不一樣的。是不一樣的。(2)(2)對對SLR(1)SLR(1)分分析析表表來來說說，若若項項目目A A屬屬于于I Ik k，則則對對任任何何輸輸入入符符號號a a，僅僅當當a aFOLLOW(A)FOLLOW(A)時時置置ACTIONk,aACTIONk,a為為“用用產(chǎn)產(chǎn)生生式式A A進進行行歸歸約約(A(A為為第第j j個個產(chǎn)產(chǎn)生生式式)”，簡簡記記為為“r rj j”。表表現(xiàn)現(xiàn)在在ACTIONACTION子子表表中中，則則存存在在某某個個歸歸約約狀狀態(tài)態(tài)所所在在的的行行并并不不全全部部填填滿滿r rj j，并且不同行的并且不同行的“r rj j”其下標其下標j j不同。不同。第四章(3)(3)對對LR(1)LR(1)來來說說，若若項項目目AA,a,a屬屬于于I Ik k(狀狀態(tài)態(tài))，則則置置ACTIONk,aACTIONk,a為為“用用產(chǎn)產(chǎn)生生式式A A進進行行歸歸約約”，簡簡記記為為“r rj j”。LR(1)LR(1)是是在在SLR(1)SLR(1)狀狀態(tài)態(tài)(項項目目集集)的的基基礎(chǔ)礎(chǔ)上上，通通過過狀狀態(tài)態(tài)分分裂裂的的辦辦法法(即即分分裂裂成成更更多多的的項項目目集集)，使使得得LRLR分分析析器器的的每每個個狀狀態(tài)態(tài)能能夠夠確確切切地地指指出出當當后后跟跟哪哪些些終終結(jié)結(jié)符符時時才才容容許許把把歸歸約約為為A A。例例如如，假假定定AA,a,a屬屬于于I Ik k(狀狀態(tài)態(tài))，則則置置ACTIONk,aACTIONk,a欄欄目目為為r rj j(A(A為為第第j j個個產(chǎn)產(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)的的分分析析表表為為LR(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)為為LR(0)LR(0)分分析析表表(存存在在并并不不全全部部填填滿滿r rj j的行，且不同行的行，且不同行r rj j的的j j不同不同)。第四章第五章1 1、表達式表達式(A AB)B)(C(CD)D)的逆波蘭表示為的逆波蘭表示為 。2 2、有一語法制導翻譯如下所示：、有一語法制導翻譯如下所示：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，且且采采用用自自下下而而上上的分析方法，則輸出序列為的分析方法，則輸出序列為 。34242421ABCD3 3、給出文法、給出文法GS:GS:S SSaA|ASaA|AA AAbB|BAbB|BB BcSd|ecSd|e請證實請證實AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一個句型；的一個句型；請寫出該句型的所有短語、素短語以及句柄；請寫出該句型的所有短語、素短語以及句柄；為為文文法法GSGS的的每每個個產(chǎn)產(chǎn)生生式式寫寫出出相相應應的的翻翻譯譯子子程程序序，使使句句型型AacAbcBaAdbedAacAbcBaAdbed經(jīng)經(jīng)該該翻翻譯譯方方案案歸歸約約后，輸出為后，輸出為131042521430131042521430。第五章第五章(1)(1)根根據(jù)據(jù)文文法法GSGS畫畫出出AacAbcBaAdbedAacAbcBaAdbed對對應應的的語法樹如圖所示。語法樹如圖所示。由由圖圖可可知知AacAbcBaAdbedAacAbcBaAdbed是是文文法法GSGS的一個句型。的一個句型。圖圖AacAbcBaAdbed對應的語法樹對應的語法樹第五章(2)(2)由由圖圖可可知知，句句型型AacAbcBaAdbedAacAbcBaAdbed中的短語為：中的短語為：B,B,BaABaA,cBaAdcBaAd,AbcBaAdAbcBaAd,e,e,AbcBaAdbeAbcBaAdbe,cAbcBaAdbedcAbcBaAdbed,A,A,AacAbcBaAdbedAacAbcBaAdbed第五章從從 圖圖 可可 看看 出出，句句 型型AacAbcBaAdbedAacAbcBaAdbed的的素短語為：素短語為：BaABaA和和e e。句柄句柄(最左直接短語最左直接短語)為：為：A A。(3)(3)采采用用修修剪剪語語法法樹樹的的辦辦法法，按按句句柄柄方方式式自自下下而而上上歸歸約約，每每當當一一個個產(chǎn)產(chǎn)生生式式得得到到匹匹配配時時，則則按按歸歸約約的的先先后后順序與所給的輸出順序與所給的輸出131042521430131042521430順序進行對應。順序進行對應。如如：第第一一個個句句柄柄為為A A，它它所所對對應應的的產(chǎn)產(chǎn)生生式式為為S SA A，所所以以它它的的語語義義動動作作應應為為print(print(1 1)；修修剪剪后后第第二二次次找找到到的的句句柄柄為為B,B,它它所所對對應應的的產(chǎn)產(chǎn)生生式式為為A AB B，此此時時它它對對應應輸輸出出序序列列中中的的“3 3”，即即它它的的語語義義動動作作為為print(print(3 3)，依依此此類類推推，得得到到每每個個產(chǎn)產(chǎn)生生式式相相應應的的語義動作如下：語義動作如下：第五章第五章SSaAprint(0)SAprint(1)AAbBprint(2)ABprint(3)BcSdprint(4)Beprint(5)句型句型AacAbcBaAdbed經(jīng)該翻譯方經(jīng)該翻譯方案歸約后，輸出為案歸約后，輸出為131042521430