編譯原理習題與答案

第二章2.2設有文法G[N]:N->D|ND D->0|1|…|9(1)G[N]定義的語言是什么？(2)請給出句子0123的最左推導和最右推導。NNDNDDNDDDDDDD0DDD01DD012D0123NNDN3ND3N23ND23N123D12301232021/3/1112.5證明下面的文法是二義性的。 S→iSeS|iS|i答：對句子iiiei對應兩棵不同的語法樹第二章SiSSeiSiiSiSSeiSii2021/3/1122.9設有文法G[T]:T→T*F|F F→F?P|P P→(T)|i分析句型T*P?(T*F)的短語、直接短語和句柄答：句型T*P?(T*F)的語法樹：TTF*()T五棵子樹對應五個短語T*P?(T*F),P?(T*F),P,(T*F),T*F兩層子樹(簡單子樹)的末端結點構成直接短語兩棵兩層子樹對應兩個直接短語：

P,T*F位于最左邊的兩層子樹的末端結點構成句柄： P第二章PF?PTF*2021/3/113第三章3.1構造正規(guī)式1(0|1)*101相應的NFAX1B1C10D

YA(0|1)*X1B1C10D

YAεEε0|1X1B1C10D

YAεEε0,12021/3/114第三章3.1構造正規(guī)式1(0|1)*101相應的NFAX11B10C

YA(0|1)*0,1X11B10C

YAX1B1C10D

YAεEε0,12021/3/115第三章3.5給出下述文法所對應的正規(guī)式。 G：S→aAA→bA|aB|bB→aA解：先由產生式得: B=aA將B代入A中得: A=bA|aaA|b=(b|aa)A|b利用規(guī)則（A->xA|y）得: A=(b|aa)*b將A代入S中得:S=a(b|aa)*b

即為所求正規(guī)式2021/3/1163.4給出文法G[S]，構造相應最小的DFA。 G：S→aS|bA|bA→aS解：由文法到NFA的轉換有兩種方法：①由文法到正規(guī)式，再由正規(guī)式到NFA先由產生式得: A=aS將A代入S中得: S=aS|bA|b=aS|baS|b =(a|ba)S|b利用規(guī)則（A->xA|y）得: S=(a|ba)*b

文法G對應的正規(guī)式為(a|ba)*b，其對應的NFA的狀態(tài)轉換圖為：2021/3/117第三章3.4給出文法G[S]，構造相應最小的DFA。G：S→aS|bA|bA→aS解：②由文法直接到NFA文法對應的有自動M=({S,A,T},{a,b},f,S,{T})其對應的狀態(tài)轉換圖為：產生式轉換函數S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S2021/3/118第三章正規(guī)式：(a|ba)*bTbSAaba產生式轉換函數S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S2021/3/119第三章將NFA確定化為DFA如右圖所示最小化：此狀態(tài)圖已經為最簡了。TbSAaba{S}{S}{A,T}{A,T}{S}IbIaI0101001aba--2021/3/1110第三章1.指出與正規(guī)式匹配的串。a)(ab|b)*c與后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a|b)c與后面的那些串匹配？acacacbbcabbcacabcaccc)(a|b)aa*(ba)*與后面的那些串匹配?babbabaaaaababa2021/3/1111第三章2.為下邊所描述的串寫正規(guī)式，字母表是{0,1}.a)以01結尾的所有串b)只包含一個0的所有串c)包含偶數個1但不含0的所有串d)包含偶數個1且含任意數目0的所有串e)包含01子串的所有串f)不包含01子串的所有串(0|1)*011*01*(11)*(0*10*10*)*(0|1)*01(0|1)*1*0*2021/3/1112第三章3.請描述下面正規(guī)式定義的串.字母表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的串

2021/3/1113第三章4.指出哪些串是自動機可接受的 xyxyxxyyyyxxyyxyxyxxy2021/3/1114第三章 5.將下圖所示的非確定有限自動機(NFA)變換成等價的確定有限自動機(DFA)。2021/3/1115第三章解:用子集法將NFA確定化，如下圖所示。

IIaIb{X}{1}{3}{2,3,Y}{3,Y}{1}－{3,4}{3}{2,3,4,Y}{2,3,Y}{2,3,Y}{2,3,Y}{3,4}{3,Y}{3,4,Y}{3,4}{3,4}{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}{3,4,Y}{3,4,Y}ba01213425－336435557666767重新命名2021/3/1116上圖所對應的DFA如下所示。

第三章ba01213425－3364355576667672021/3/1117對上圖的DFA進行最小化。首先將狀態(tài)分為非終態(tài)集和終態(tài)集兩部分：{0,1,2,5}和{3,4,6,7}。由終態(tài)集可知，對于狀態(tài)3、6、7，無論輸入字符是a還是b的下一狀態(tài)均為終態(tài)集，而狀態(tài)4在輸入字符b的下一狀態(tài)落入非終態(tài)集，故將其化為分{0,1,2,5},{4},{3,6,7}第三章ba01213425－3364355576667672021/3/1118第三章對于非終態(tài)集，在輸入字符a、b后按其下一狀態(tài)落入的狀態(tài)集不同而最終劃分為{0},{1},{2},{5},{4},{3,6,7}按順序重新命名為0、1、2、3、4、5，得到最簡DFA如下圖所示。{0,1,2,5},{4},{3,6,7}ba01213425－3364355576667672021/3/11192021/3/11206.設有L(G)={a2n+1b2ma2p+1|

n≥0,p≥0,m≥1}。(1)給出描述該語言的正規(guī)表達式；(2)構造識別該語言的確定有限自動機(可直接用狀態(tài)圖形式給出)。解：(1)該語言對應的正規(guī)式為a(aa)*bb(bb)*a(aa)*。(2)a(aa)*bb(bb)*a(aa)*正規(guī)表達式對應的NFA如下圖所示。第三章2021/3/1121第三章正規(guī)表達式：a(aa)*bb(bb)*a(aa)*2021/3/1122IIaIb用子集法將上圖確定化，如圖所示。{X}{1}{2}{1}{1}{2}{3}{4}{5}{6}－{Y}－{Y}－{3}－{4}{5}{4}－重命名X1234Y5612－－3－1Y6－Y45－4－ab{Y}{6}－2021/3/1123 重新命名后的狀態(tài)轉換矩陣可化簡為(可由最小化方法得到) {X,2}{1}{3,5}{4}{6}{Y}

按順序重新命名為0、1、2、3、4、5后得到最簡的DFA，如下圖所示。

X1234Y5612－－3－1Y6－Y45－4－ab2021/3/1124第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa2021/3/1125 7.有一臺自動售貨機，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機器中投放≥3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢)。 (1)寫出售貨機售糖的正規(guī)表達式； (2)構造識別上述正規(guī)式的最簡DFA。

解：(1)設a=1，b=2，則售貨機售糖的正規(guī)表達式為 a(b|a(a|b))|b(a|b)。 (2)畫出與正規(guī)表達式a(b|a(a|b))|b(a|b)對應的NFA，如圖所示。第三章2021/3/1126第三章正規(guī)表達式：a(b|a(a|b))|b(a|b)2021/3/1127IIaIb第三章用子集法將NFA確定化。

重新命名{Y}－－{3}{Y}{Y}{2}{Y}{Y}{1}{3}{Y}{X}{1}{2}4－－344244134012ab2021/3/1128由轉換矩陣可看出，非終態(tài)2和非終態(tài)3面對輸入符號a或b的下一狀態(tài)相同，故合并為一個狀態(tài)即最簡狀態(tài){0}、{1}、{2，3}、{4}。按順序重新命名為0、1、2、3，則得到最簡DFA，如下圖所示。第三章4－－344244134012ab2021/3/11290312abbbaa－－3233123012ab第三章2021/3/1130第四章作業(yè)4.3設有文法G[S]: S→A A→B|AiB B→C|B+CC→)A*|(

1）將文法G[S]改寫為LL(1)文法。2）求經改寫后的文法的每個非終結符的FIRST集和FOLLOW集。3）構造相應的預測分析表。2021/3/1131第四章1）將文法G[S]改寫為LL(1)文法。文法G[S]為左遞歸文法，削去文法左遞歸后的文法為：S→A A→BA’A’→iBA’|εB→CB’B’→+CB’|εC→)A*|(

S→A A→B|AiBB→C|B+CC→)A*|(

2021/3/1132第四章1）將文法G[S]改寫為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,$,*}S→A A→BA’A’→iBA’|εB→CB’B’→+CB’|εC→)A*|(

2021/3/1133第四章SELECT(S→A)=FIRST(A)=((,))SELECT(A→BA’)=((,)) SELECT(A’→iBA’)={i}SELECT(A’→ε)=FOLLOW(A’)={$,*}SELECT(B→CB’)=((,))SELECT(B’→+CB’)={+} SELECT(B’→ε)={i,$,*}SELECT(C→)A*)={)} SELECT(C→()={(}因為同一非終結符的不同產生式的Select集交集為空，所以改寫后的文法是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,$,*}2021/3/11343）構造相應的預測分析表。B'→εB'→εC→)A*B’→+CB’B'→εC→(B’B→CB’B→CB’BA'→εA'→εA’→iBA’A’A→BA’A→BA’AS$*)+i(終極符號語法變量S→AS→ASELECT(S→A)=((,)) SELECT(A→BA’)=((,)) SELECT(A’→iBA’)={i} SELECT(A’→ε)={$,*}

SELECT(B→CB’)=((,)) SELECT(B’→+CB’)={+}SELECT(B’→ε)={i,$,*}

SELECT(C→)A*)={)}SELECT(C→()={(}C2021/3/1135第四章作業(yè)4.5設有表格結構文法G[S]:S→a|∧|(T)T→T,S|S

1）計算文法的FIRSTVT集和LASTVT集。2）構造其優(yōu)先關系表，并判斷其是否為算符優(yōu)先文法。3）計算其優(yōu)先函數。2021/3/1136第四章1）計算文法的FIRSTVT集和LASTVT集。FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)}2）構造其優(yōu)先關系表，并判斷其是否為算符優(yōu)先文法。S→a|∧|(T)T→T,S|S∧=><<<$a(a,>>>>>>>><<<)>>>=<<<<($,)∧2021/3/1137第四章3）計算其優(yōu)先函數。用逐次加1法構造優(yōu)先函數∧=><<<$a(a,>>>>>>>><<<)>>>=<<<<($,)∧1111111111迭代函數函數a∧,()fg0(初值)fg122213233313331344241fg2<,<<<2021/3/1138第四章例文法G[S]S→EE→aA|bBA→cA|dB→cB|d

1）構造識別文法活前綴的DFA2）構造其LR(0)分析表3）輸入串aabab是否為文法G定義的句子2021/3/11390:S→·EE→·aAE→·bB4:A→c·AA→·cAA→·dc5:B→c·BB→·cBB→·dc3:E→b·BB→·cBB→·db1:S→E·E2:E→a·AA→·cAA→·da11:B→d·d8:A→cA·Accd10:A→d·dd9:B→cB·B6:E→aA·A7:E→bB·B2021/3/1140LR(0)分析表為:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6狀態(tài)ACTIONGOTOabcd#EAB01234567891011S→E E→aA|bBA→cA|dB→cB|d2021/3/1141(0)S→E (1)E→aА (2)E→bB (3)A→cА(4)A→d (5)B→cB (6)B→d輸入串bccd$的分析過程步驟狀態(tài)棧符號棧輸入串ACTIONGOTO1

2

3

4

56789

0$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$$$$$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E12021/3/1142第四章8086/8088匯編語言對操作數域的檢查可以用LR分析表實現。設m代表存儲器，r代表寄存器，i代表立即數；并且為了簡單起見，省去了關于m、r和i的產生式，暫且認為m、r、i為終結符，則操作數域P的文法G[P]為 G[P]:P→m,r∣m,i∣r,r∣r,i∣r,m試構造能夠正確識別操作數域的LR分析表。2021/3/1143(1)將文法G[S]拓廣為文法G'[S']：(0)S'→P(1)P→m,r(2)P→m,i(3)P→r,r(4)P→r,i(5)P→r,m第四章G[P]:P→m,r∣m,i∣r,r∣r,i∣r,m2021/3/1144文法G'[S']的DFA0:S→·PP→·m,rP→·m,iP→·r,rP→·r,iP→·r,m(0)S'→P (1)P→m,r (2)P→m,i(3)P→r,r (4)P→r,i (5)P→r,m1:S→P·P2:P→m·,rP→m·,i3:P→r·,rP→r·,iP→r·,m5:P→m,·rP→m,·i4:P→r,·rP→r,·iP→r,·m,mr,r6:P→m,r·i7:P→m,i·r8:P→r,r·i9:P→r,i·m10:P→r,m·2021/3/1145LR(0)分析表狀態(tài)ACTIONGOTOmri，$P0s2s3

1

1

acc

2

s5

3

s4

4s10s8s9

5

s6s7

6r1r1r1r1r1

7r2r2r2r2r2

8r3r3r3r3r3

9r4r4r4r4r4

10r5r5r5r5r5r12021/3/1146(0)S'→P (1)P→m,r (2)P→m,i(3)P→r,r (4)P→r,i (5)P→r,m輸入串m,i$的分析過程步驟狀態(tài)棧符號棧輸入串ACTIONGOTO1

2

3

4

5

0$m,i$S202$m,i$S5025$m,i$S70257$m,i$r20$$acc1P12021/3/1147例：請指出下圖中的LR分析表(a)、(b)、(c)分屬LR(0)、SLR(1)和LR(1)中的哪一種，并說明理由。2021/3/1148我們知道，LR(0)、SLR(1)和LR(1)分析表構造的主要差別是構造算法。其區(qū)別如下： (1)對LR(0)分析表來說，若項目A→α·屬于Ik(狀態(tài))，則對任何終結符a(包括$)，置ACTION[k,a]為“用產生式A→α進行歸約(A→α為第j個產生式)”，簡記為“rj”。表現在ACTION子表中，則是每個歸約狀態(tài)所在的行全部填滿“rj”；并且，同一行的“rj”其下標j相同，而不同行的“rj”其下標j是不一樣的。

2021/3/1149(2)對SLR(1)分析表來說，若項目A→α·屬于Ik，則對任何輸入符號a，僅當a∈FOLLOW(A)時置ACTION[k,a]為“用產生式A→α進行歸約(A→α為第j個產生式)”，簡記為“rj”。表現在ACTION子表中，則存在某個歸約狀態(tài)所在的行并不全部填滿rj，并且不同行的“rj”其下標j不同。第四章2021/3/1150(3)對LR(1)來說，若項目[A→α·,a]屬于Ik(狀態(tài))，則置ACTION[k,a]為“用產生式A→α進行歸約”，簡記為“rj”。LR(1)是在SLR(1)狀態(tài)(項目集)的基礎上，通過狀態(tài)分裂的辦法(即分裂成更多的項目集)，使得LR分析器的每個狀態(tài)能夠確切地指出當α后跟哪些終結符時才容許把α歸約為A。例如，假定[A→α·,a]屬于Ik(狀態(tài))，則置ACTION[k,a]欄目為rj(A→α為第j個產生式)；而[A→α·,b]屬于Im(狀態(tài))，則同樣置ACTION[m,b]欄目為rj。表現在ACTION子表中，則在不同的行(即不同的狀態(tài))里有相同的rj存在。2021/3/1151因此，圖3-12(a)的分析表為LR(1)分析表(在不同行有相同的r2存在)；圖3-12(b)為LR(0)分析表(有rj的行是每行都填滿了rj且同一行rj的j相同，不同行rj的j不同)；而圖3-12(c)為LR(0)分析表(存在并不全部填滿rj的行，且不同行rj的j不同)。第四章2021/3/1152第五章1、表達式(┐A∨B)∧(C∨D)的逆波蘭表示為

。

2、有一語法制導翻譯如下所示：

S→bAb{print″1″} A→(B{print″2″} A→a{print″3″