《編譯原理習題與答案》由會員分享，可在線閱讀，更多相關《編譯原理習題與答案（59頁珍藏版）》請在裝配圖網上搜索。
1、第二章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)的
2、短語、直接短語和句柄的短語、直接短語和句柄答：句型答：句型T*P(T*F)的語法樹：的語法樹：TTF*()T五棵子樹對應五個短語五棵子樹對應五個短語T*P(T*F),P(T*F),P,(T*F),T*F兩層子樹兩層子樹(簡單子樹簡單子樹)的末端結點構成直接短語的末端結點構成直接短語 兩棵兩層子樹對應兩個直接短語：兩棵兩層子樹對應兩個直接短語：P,T*F位于最左邊的兩層子樹的末端結點構成句柄：位于最左邊的兩層子樹的末端結點構成句柄：P第二章PFPTF*第三章3.1構造正規式構造正規式1(0|1)*101相應的相應的NFAX1B1C10DYA(0|1)*X1B1C10DYAE0|1X1B1C10D
3、YAE0,1第三章3.1構造正規式構造正規式1(0|1)*101相應的相應的NFAX11B10CYA(0|1)*0,1X11B10CYAX1B1C10DYAE0,1第三章3.5給出下述文法所對應的正規式。給出下述文法所對應的正規式。G：SaAAbA|aB|bBaA解：先由產生式得解：先由產生式得:B=aA將將B代入代入A中得中得:A=bA|aaA|b=(b|aa)A|b利用規則利用規則（A-xA|y）得得:A=(b|aa)*b將將A代入代入S中得中得:S=a(b|aa)*b即為所求正規式即為所求正規式3.4給出文法給出文法GS，構造相應最小的，構造相應最小的DFA。G：SaS|bA|bAaS解
4、解：由文法到由文法到NFA的轉換有兩種方法：的轉換有兩種方法：由文法到正規式，再由正規式到由文法到正規式，再由正規式到NFA先由產生式得先由產生式得:A=aS將將A代入代入S中得中得:S=aS|bA|b=aS|baS|b=(a|ba)S|b利用規則利用規則（A-xA|y）得得:S=(a|ba)*b文文法法G對對應應的的正正規規式式為為(a|ba)*b，其其對對應應的的NFA的狀態轉換圖為的狀態轉換圖為：第三章3.4給出文法給出文法GS，構造相，構造相應最小的應最小的DFA。G：SaS|bA|bAaS解解：由文法直接到由文法直接到NFA文法對應的有自動文法對應的有自動M=(S,A,T,a,b,f
5、,S,T)其對應的狀態轉換圖為：其對應的狀態轉換圖為：產生式產生式轉換函數轉換函數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第三章正規式：正規式：(a|ba)*bTbSAaba產生式產生式轉換函數轉換函數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如右圖所示如右圖所示最小化：此狀態圖已經為最簡了。最小化：此狀態圖已經為最簡了。TbSAabaSSA
6、,TA,TSIbIaI0101001aba-第三章1.指出與正規式匹配的串。指出與正規式匹配的串。a)(ab|b)*c與后面的那些串匹配？與后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a|b)c與后面的那些串匹配？與后面的那些串匹配？acacacbbcabbcacabcaccc)(a|b)aa*(ba)*與后面的那些串匹配與后面的那些串匹配?babbabaaaaababa第三章2.為下邊所描述的串寫正規式，字母表是為下邊所描述的串寫正規式，字母表是0,1.a)以以01結尾的所有串結尾的所有串b)只包含一個只包含一個0的所有串的所有串c)包含偶數個包含偶數個1但不含
7、但不含0的所有串的所有串d)包含偶數個包含偶數個1且含任意數目且含任意數目0的所有串的所有串e)包含包含01子串的所有串子串的所有串f)不包含不包含01子串的所有串子串的所有串(0|1)*011*01*(11)*(0*10*10*)*(0|1)*01(0|1)*1*0*第三章3.請描述下面正規式定義的串請描述下面正規式定義的串.字母表字母表S=x,y。a)x(x|y)*x必須以必須以x開頭和開頭和x結尾的串結尾的串b)x*(yx+)*x*每個每個y至少有一個至少有一個x跟在后邊的串跟在后邊的串c)(x|y)*(xx|yy)(x|y)*所有含兩個相繼的所有含兩個相繼的x或兩個相繼的或兩個相繼的y
8、的串的串 第三章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重新命名重新命名 上上圖
9、所對應的圖所對應的DFA如下所示。如下所示。第三章ba01213425336435557666767對對上上圖圖的的DFA進進行行最最小小化化。首首先先將將狀狀態態分分為為非非終終態態集集和和終終態態集集兩兩部部分分：0,1,2,5和和3,4,6,7。由由終終態態集集可可知知，對對于于狀狀態態3、6、7，無無論論輸輸入入字字符符是是a還還是是b的的下下一一狀狀態態均均為為終終態態集集，而而狀狀態態4在在輸輸入入字字符符b的的下下一一狀狀態態落落入入非非終終態態集集，故故將將其其化為分化為分0,1,2,5,4,3,6,7第三章ba01213425336435557666767第三章對對于于非非終
10、終態態集集，在在輸輸入入字字符符a a、b b后后按按其其下下一一狀狀態態落落入入的的狀狀態態集集不同而最終劃分為不同而最終劃分為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)給出描述該語言的正規表達式；給出描述該語言的正規表達式；(2)構構造造識識別別該該語語言言的的確確定定有有限限自自動動機機(可可直直接接用用狀狀態圖形式給出態圖形式給出)。解：解
11、：(1)該語言對應的正規式為該語言對應的正規式為a(aa)*bb(bb)*a(aa)*。(2)a(aa)*bb(bb)*a(aa)*正正規規表表達達式式對對應應的的NFA如如下下圖所示。圖所示。第三章第三章正規表達式：正規表達式：a(aaa(aa)*bb(bbbb(bb)*a(aaa(aa)*IIaIb用子集法將上圖確定化，如圖所示。用子集法將上圖確定化，如圖所示。X121123456YY3454重命名重命名X1234Y561231Y6Y454abY6重重新新命命名名后后的的狀狀態態轉轉換換矩矩陣陣可化簡為可化簡為(可由最小化方法得到可由最小化方法得到)X,213,546Y按順序重新命名為按順
12、序重新命名為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)寫出售貨機售糖的正規表達式；寫出售貨機售糖的正規表達式；(2)(2)構造識
13、別上述正規式的最簡構造識別上述正規式的最簡DFADFA。解解：(1)(1)設設a=1a=1，b=2b=2，則售貨機售糖的正規表達式為則售貨機售糖的正規表達式為a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)。(2)(2)畫畫出出與與正正規規表表達達式式a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)對對應應的的NFANFA，如圖所示。如圖所示。第三章第三章正規表達式：正規表達式：a(b|a(a|b)|b(a|b)IIaIb第三章用子集法將用子集法將NFA確定化。確定化。重新命名Y3YY2YY13YX124344244134012ab由由轉轉換換矩矩陣陣可
14、可看看出出，非非終終態態2 2和和非非終終態態3 3面面對對輸輸入入符符號號a a或或b b的的下下一一狀狀態態相相同同，故故合并為一個狀態合并為一個狀態即最簡狀態即最簡狀態00、11、22，33、44。按按順順序序重重新新命命名名為為0 0、1 1、2 2、3 3，則則得得到到最簡最簡DFADFA，如下圖所示。，如下圖所示。第三章4344244134012ab0312abbbaa3233123012ab第三章第四章作業作業4.3設有文法設有文法GS:SAAB|AiBBC|B+CC)A*|(1）將文法）將文法GS改寫為改寫為LL(1)文法。文法。2）求經改寫后的文法的每個非終結符的）求經改寫后
15、的文法的每個非終結符的FIRST集和集和FOLLOW集。集。3）構造相應的預測分析表。）構造相應的預測分析表。第四章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)=$,
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()=(因為因為同一非終結符的不同產生式的同一非終結符的不同產生式的Select集交集為空集交集為空，所以，所以改寫后的文法是改寫后的文法是
17、LL(1)文法。文法。2）求經改寫后的文法的每個非終結符的）求經改寫后的文法的每個非終結符的FIRST集和集和FOLLOW集。集。在上步中已經求出。在上步中已經求出。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）構造相應的預測分析表。）構造相應的預測分析表。BBBBC)A*B+CBBBC(BBCBBCBBAAAAAiBAAABAAB
18、AAS$*)+i(終極符號終極符號語法語法變量變量SASASASASELECT(SA)=(,)SELECT(ABA)=(,)SELECT(AiBA)=iSELECT(A)=$,*SELECT(BCB)=(,)SELECT(B+CB)=+SELECT(B)=i,$,*SELECT(C)A*)=)SELECT(C()=(C第四章作業作業4.5設有表格結構文法設有表格結構文法GS:Sa|(T)TT,S|S 1）計算文法的）計算文法的FIRSTVT集和集和LASTVT集。集。2）構造其優先關系表，并判斷其是否為算）構造其優先關系表，并判斷其是否為算符優先文法。符優先文法。3）計算其優先函數。）計算其優
19、先函數。第四章1）計算文法的）計算文法的FIRSTVT集和集和LASTVT集。集。FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)2）構造其優先關系表，并判）構造其優先關系表，并判斷其是否為算符優先文法。斷其是否為算符優先文法。Sa|(T)TT,S|S=($,)1111111111迭代函迭代函數數函數函數a,()fg0(初初值值)fg122213233313331344241fg2,第四章例文法例文法GSS EEaA|bBAcA|dBcB|d 1）構造）構造識別識別文法活前文法活前綴綴的的DFA2）構造其）構造其LR(0)分析表分
20、析表3）輸輸入串入串aabab是否是否為為文法文法G定定義義的句子的句子0:S EEaAEbB4:AcAAcAAdc5:BcBBcBBdc3:EbBBcBBdb1:S EE2:EaAAcAAda11:Bdd8:AcAAccd10:Addd9:BcBB6:EaAA7:EbBBLR(0)分析表為分析表為:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6狀態狀態ACTIONGOTOabcd#EAB01234567891011S EEaA|bBAcA|dBcB|d(0
21、)S E(1)Ea(2)EbB(3)Ac(4)Ad(5)BcB(6)Bd輸入串輸入串bccd$的分析過程的分析過程步驟步驟狀態棧狀態棧符號棧符號棧輸入串輸入串 ACTIONGOTO1234567890$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E1第四章8086/8088匯匯編編語語言言對對操操作作數數域域的的檢檢查查可可以以用用LR分分析析表表實實現現。設設m代代表表存存儲儲器器，r代代表表寄寄存存器器，i代代表表立立即即數數；并并且且
22、為為了了簡簡單單起起見見，省省去去了了關關于于m、r和和i的的產產生生式式，暫暫且且認認為為m、r、i為為終終結結符符，則則操操作作數數域域P的文法的文法GP為為GP:Pm,r m,i r,r r,i r,m試試構造能構造能夠夠正確正確識別識別操作數域的操作數域的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)分析表分析表狀態狀態ACTIONGOTOmri，$P0s2s311acc2s53s44s10s8s95s6s76r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r4r4r4r4r410r5r5r5r5r5r1(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m輸入串輸入串m,i$的分析過程的分析過程步驟步驟狀態棧狀態棧符號棧符號棧輸入串輸入串
24、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)分分析析表表構造的主要差別是構造算法。其區別如下：構造的主要差別是構造算法。其區別如下：(1)對對LR(0)分析表來說，若項目分析表來說，若項目A屬屬于于Ik(狀態狀態)，則對，則對任何終結符任何終結符
25、a(包括包括$)，置，置ACTIONk,a為為“用產生式用產生式A進行歸約進行歸約(A為第為第j個產生式個產生式)”，簡記為，簡記為“rj”。表現在表現在ACTION子表中，則是每個歸約狀子表中，則是每個歸約狀態所在的行全部填滿態所在的行全部填滿“rj”；并且，并且，同一同一行的行的“rj”其下標其下標j相同，而不同行的相同，而不同行的“rj”其下標其下標j是不一樣的。是不一樣的。(2)(2)對對SLR(1)SLR(1)分分析析表表來來說說，若若項項目目A A屬屬于于I Ik k，則則對對任任何何輸輸入入符符號號a a，僅僅當當a aFOLLOW(A)FOLLOW(A)時時置置ACTIONk,
26、aACTIONk,a為為“用用產產生生式式A A進進行行歸歸約約(A(A為為第第j j個個產產生生式式)”，簡簡記記為為“r rj j”。表表現現在在ACTIONACTION子子表表中中，則則存存在在某某個個歸歸約約狀狀態態所所在在的的行行并并不不全全部部填填滿滿r rj j，并且不同行的并且不同行的“r rj j”其下標其下標j j不同。不同。第四章(3)(3)對對LR(1)LR(1)來來說說，若若項項目目AA,a,a屬屬于于I Ik k(狀狀態態)，則則置置ACTIONk,aACTIONk,a為為“用用產產生生式式A A進進行行歸歸約約”，簡簡記記為為“r rj j”。LR(1)LR(1)
27、是是在在SLR(1)SLR(1)狀狀態態(項項目目集集)的的基基礎礎上上，通通過過狀狀態態分分裂裂的的辦辦法法(即即分分裂裂成成更更多多的的項項目目集集)，使使得得LRLR分分析析器器的的每每個個狀狀態態能能夠夠確確切切地地指指出出當當后后跟跟哪哪些些終終結結符符時時才才容容許許把把歸歸約約為為A A。例例如如，假假定定AA,a,a屬屬于于I Ik k(狀狀態態)，則則置置ACTIONk,aACTIONk,a欄欄目目為為r rj j(A(A為為第第j j個個產產生生式式)；而而AA,b,b屬屬于于I Im m(狀狀態態)，則則同同樣樣置置ACTIONm,bACTIONm,b欄欄目目為為r rj
28、 j。表表現現在在ACTIONACTION子子表表中中，則則在在不同的行不同的行(即不同的狀態即不同的狀態)里有相同的里有相同的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)分分析析
29、表表(存存在在并并不不全全部部填填滿滿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，且且采采用用自自下下而而上上的分析方法，則輸出序列為的分析方法，則輸出序列為
30、。34242421ABCD3 3、給出文法、給出文法GS:GS:S SSaA|ASaA|AA AAbB|BAbB|BB BcSd|ecSd|e請證實請證實AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一個句型；的一個句型；請寫出該句型的所有短語、素短語以及句柄；請寫出該句型的所有短語、素短語以及句柄；為為文文法法GSGS的的每每個個產產生生式式寫寫出出相相應應的的翻翻譯譯子子程程序序，使使句句型型AacAbcBaAdbedAacAbcBaAdbed經經該該翻翻譯譯方方案案歸歸約約后，輸出為后，輸出為131042521430131042521430。第五章第五章(1)
31、(1)根根據據文文法法GSGS畫畫出出AacAbcBaAdbedAacAbcBaAdbed對對應應的的語法樹如圖所示。語法樹如圖所示。由由圖圖可可知知AacAbcBaAdbedAacAbcBaAdbed是是文文法法GSGS的一個句型。的一個句型。圖圖AacAbcBaAdbed對應的語法樹對應的語法樹第五章(2)(2)由由圖圖可可知知，句句型型AacAbcBaAdbedAacAbcBaAdbed中的短語為：中的短語為：B,B,BaABaA,cBaAdcBaAd,AbcBaAdAbcBaAd,e,e,AbcBaAdbeAbcBaAdbe,cAbcBaAdbedcAbcBaAdbed,A,A,Aac
32、AbcBaAdbedAacAbcBaAdbed第五章從從 圖圖 可可 看看 出出，句句 型型AacAbcBaAdbedAacAbcBaAdbed的的素短語為：素短語為：BaABaA和和e e。句柄句柄(最左直接短語最左直接短語)為：為：A A。(3)(3)采采用用修修剪剪語語法法樹樹的的辦辦法法，按按句句柄柄方方式式自自下下而而上上歸歸約約，每每當當一一個個產產生生式式得得到到匹匹配配時時，則則按按歸歸約約的的先先后后順序與所給的輸出順序與所給的輸出131042521430131042521430順序進行對應。順序進行對應。如如：第第一一個個句句柄柄為為A A，它它所所對對應應的的產產生生式式
33、為為S SA A，所所以以它它的的語語義義動動作作應應為為print(print(1 1)；修修剪剪后后第第二二次次找找到到的的句句柄柄為為B,B,它它所所對對應應的的產產生生式式為為A AB B，此此時時它它對對應應輸輸出出序序列列中中的的“3 3”，即即它它的的語語義義動動作作為為print(print(3 3)，依依此此類類推推，得得到到每每個個產產生生式式相相應應的的語義動作如下：語義動作如下：第五章第五章SSaAprint(0)SAprint(1)AAbBprint(2)ABprint(3)BcSdprint(4)Beprint(5)句型句型AacAbcBaAdbed經該翻譯方經該翻譯方案歸約后，輸出為案歸約后，輸出為131042521430
編譯原理習題與答案
