編譯原理復(fù)習題答案

1、二、概念題1、設(shè)有文法：PQ P+Q|QCH Q*R|RRH (P)|i(1)證明Q*R+Q+O它的一個句型。(3分)(2)給出Q*R+Q+Q所有短語，直接短語和句柄。(4分)(3)給出句子i + i * i的最右推導。(4分)(4)給出句子i + i * i的最左推導。(4分)2、設(shè)有文法： E+T|T T -T*F|F F -(E)|i(1)證明E+T*F是它的一個句型。(3分)答案 ： E E T E T* F( 2)給出E+T*F 的所有短語，直接短語和句柄。 (4 分)短語 : E+T*F, T*F,直接短語 : T*F句柄 : T*F(3)給出句子i + i * i的最右推導。(4

2、分)3、寫出表達式a+b*(c-d) 對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式： (abcd-*+)三元式序列：OP ARG1 ARG2(1) -cd(2) *b(1)(3) +a(2)三、詞法分析題給出下面語言的相應(yīng)文法L1=anbnambm|n,m >0答案：S-AB|A|B| E2 aAb|abB aBb|ab給出下面語言的相應(yīng)文法L2=anbnci|n >1,i >0答案：S- AB|B2 a|aAB bBc|bc給出下面語言的相應(yīng)文法L3= anbncm| m,n Ll , n 為奇數(shù),m為偶數(shù)答案：文法G(S):S -ACA-> aaAbb/abCf cc

3、Ccc/cc四、詞法分析題1、構(gòu)造下面正規(guī)式相應(yīng)的DFA(0|1) .1(11) .)*(要求：先將正規(guī)式轉(zhuǎn)化為 NFA再將NFA1定化，最小化)2、構(gòu)造下面正規(guī)式相應(yīng)的DFA1(0|1) *101答案：II0I1XA,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,EB,C,DB,C,E B,CB,C,D,yB,C,D,yB,C,E B,C,D3、構(gòu)造一個DFA它接受=a, b上所有包含ab的字符串(要求：先將正規(guī)式轉(zhuǎn)化為 NFA再將NFA1定化，最小化)答案：(一)相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二)與此正規(guī)式對應(yīng)的NFA為狀態(tài)轉(zhuǎn)換矩陣為:精選

4、IJO.1,2)U.2J口，之，同*當 6(1,2141,2.3L,2，3,5,6111.2,3,5,>1asim,5,旬£1,2,3,5,61叫最小化：0,1, 2 3 , 4, 50, 2 , 1, 3 , 4, 5baaboV b,狀態(tài)集為0,1,3,所以此等價的DFA為：開始狀態(tài)為0 ,終態(tài)集為3輸入字母表是a,b狀態(tài)轉(zhuǎn)換圖如上。4、構(gòu)造與正規(guī)式 b(a|b)*ba 等價的DFA五、語法分析題1、對下面的文法G:Expr ExprExpr(Expr)|Var ExprTailExprTail Expr| &Varid VarTailVarTail (Expr)

5、|(1)構(gòu)造LL(1)分析表。(12分)答案:(1) FIRST(Expr尸_ , ( , id FIRST(ExprTail)=_ , & FIRST(Var尸idFIRST(VarTail)= ( ,£ FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) 步驟 符號棧輸入串所用產(chǎn)生式0# Expr1 # ExprTail Var2 # ExprTail VarTailid3 # ExprTailVarTailid_ _id(id)#idid(id)#ExprVar ExprTailidid(id) #Varid VarTail_ _id(

6、id)#4# ExprTail_id(id)#VarTail 一 eFOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) id()EzcrEq： f VarEizpxTai 1Emrf(Emr)EsprTailExprTail-. E樂r，距rTail-* EEzprT,ailVarVar idVarTailVarTailWar%” 一Vai'Tai 1 一VrTailt(2)給出對句子idid(id)的分析過程。(8分)5# Expr_6# Expr_id(id)#id(id) # ExprTail Expr7# Expr_id(id)#

7、ExprExpr8# Exprid(id) #9# ExprTail Varid(id) ExprVar ExprTail10# ExprTail VarTail idid(id) Varid VarTail11#ExprTailVarTail12#ExprTail )Expr(13#ExprTail )Expr(id) (id) # VarTail (Expr)(id) 14# ExprTail ) )Expr(id) Expr(Expr)15# ExprTail ) )Exprid) 16# ExprTail ) )Var ExprTail17# ExprTail ) )ExprTail

8、Var id) Exp ExprTail VarTail id id) Varid VarTail18# ExprTail ) )ExprTail VarTail ) 19# ExprTail ) )ExprTail ) VarTail 一 e20#ExprTail) )21#ExprTail)22#ExprTail23#)#ExprTail &)#ExprTail &分析成功2、對下面的文G:E'f+E| eTfFT'T'f T| eFPF'F' 7*F'| £F(E)|a|b| A(1)計算這個文法的每個非終結(jié)符的

9、FIRST和F0LL0W(8分)答案：FIRST(E尸(abjFIRST(E)=+, & FIRST"尸(abjFIRST(T')=(,a,b,A,& FIRST(F 尸(ab,FIRST(F)=*, £ FIRST(P 尸(abjFOLLOW(E 尸#,)FOLLOW(E')=#,)FOLLOW"尸+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F)=(,a,b,A+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2)證明這個文法是LL(1)的。(6分)答案

10、：考慮下列產(chǎn)生式：E E|T T|F *F |P (E)1A|a|bFIRST(+E) A FIRST( e)=+ A e = 0FIRST(+E) A FOLLOW(E')=+n #,)= 0FIRST(T) A FIRST(£ )=(,a,b,A n e = 0FIRST(T) A FOLLOW(T')=(,a,b,A A +,),#= 0FIRST(*F') A FIRST( & )=* A e = 0FIRST(*F') A FOLLOW(F')=* A (,a,b,A,+,),#=0FIRST(E) AFIRST(a) A F

11、IRST(b) A FIRST)= ©所以，該文法式LL(1)文法.(3)構(gòu)造它的預(yù)測分析表。(6分)口十不1柞卬副3E/E fTE'EtTZ*£ 一龍,£ ->7ZrE”EtEEr f 1爐Ef T6中T tFT卡TfFTFt 口'TtFF妙T,ppTf 7+T aF fT.FfT,p f 1力pF t PF，pF 一 PF,FfWFt*q戌口Fr T已尸r f斗尸F(xiàn)' -> 日F T心Fr T緊戶TFf -y GF，pPf(E)P f wq產(chǎn)T入PfZ3、已知文法GS為:S->a|(T)T->T,S|S消除文法G

12、S中的左遞歸，得文法G'S 文法G'S是否為LL(1)的？若是，給出它的預(yù)測分析表。4、對下面的文法G:S S a T | a T |a TT a T | a(1)消除該文法的左遞歸和提取左公因子；(2)構(gòu)造各非終結(jié)符的FIRST和FOLLO儲合；(3)構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是 LL(1)的答案：并判斷該文法是否是LL(D的. (提取左公因子2分) St aTS1 v a TSf S t 7 仃 TS' I £ 丁一 。丁' 7，T I £(3)構(gòu)造該文法的IX分析表, 答：(1)(消除在遞歸？分)St aTSf “h

13、TS'S- yaTS' | ET > T > 八口 T | a(4分)FIRST(S)af v；FIRST(S)=, £ FIRST(T)F1RST(T)=a f £ FOLLOWS) =FOLLOWS*)=FOLLOW(T)f 用FOLLOWfT), #)5、文法G(S)及其LR分析表如下，請給出串baba#的分析過程(1) S DbB B a (5) B Bba (6) B eLR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案:步驟狀態(tài)符號輸入用00#baba

14、#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc六、語法分析題 考慮文法 :S AS|b A SA|a（ 1） 列 出這個文法的所有LR（0） 項目。 （ 5 分）答案0. S S 1. S S 2. s as 3. s a s4. S AS 5. S b 6. S b 7. A SA8. a s a 9. a sa 10. a a 11. a a（ 2）給出識別文法所有活前綴的DFA。 （ 5 分）（3）求所有非終結(jié)符的FOLLOW。（5分）（4）文法是SL

15、R文法嗎？若是，構(gòu)造出它的SLR分析表，否則說明理由。 （ 5 分）不是SLR文法狀態(tài) 3， 6， 7 有移進歸約沖突狀態(tài) 3： FOLLOW（S）=# 不包含 a,b狀態(tài)6: FOLLOW（S）=#,a,b包含a,b,;移進歸約沖突無法消解狀態(tài)7: FOLLOW（A尸a,b包含a,b ;移進歸約沖突消解所以不是SLR文法。七、證明題1、證明下面文法是LL(1)的但不是SLR(1)的S AaAb|BbBaAtB- £首先該文法無左遞歸存在，沒有公共左因子。其次:對于 S- AaAb|BbBa FIRST(AaAb尸a FIRST(BbBa尸bFIRST(AaAb)n FIRST(Bb

16、Ba尸所以該文法是LL(1)文法。(2)證明該文法不是 SLR的。文法的LR(0)項目集規(guī)范族為：I0=S' 一.S SfAaAb SfBbBa Af B 一.I1= S '- S. I2= S f A.aAb I3= S f B.bBa I4= S f Aa.Ab Af I5= S 一Bb.Ba Bf I6= S f AaA.b I7= S BbB.a I8= S -AaAb. I9= S f BbBa. 考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A) FOLLOW(B尸a,b 產(chǎn)生規(guī)約-規(guī)約沖突。所以該文法不是SLR(1)文法。2、證明

17、下面文法是SLR(1)但不是LR(0)的S A2 Ab|bBaB aAc|a|aAb解：文法GS:0: SA1:卜Ab2: 2bBa3: B aAc4: Ba5: B aAb構(gòu)造LR(0)項目集規(guī)范族:狀態(tài)項目集轉(zhuǎn)換函數(shù)0S7 AGO0, A = 1K AbGO0, A = 12 bBaGO0, b =21S AACCEPTK AbGO1, b =322 b BaGO2, B=4腔 aAcGO2, a =5B7 aGO2, a =5B aAbGO2, a =53K Ab-R142bB- aGO4, a = 65腔 a AcGO5, A = 7B a R4B a AbGO5, A = 7K Ab

18、GO5, A = 72 bBaGO5, b = 262 bBa-R27腔aAcGO7, c = 8B aA bGO7, b =9K AbGO7, b =98- aAc R39B aAb-R5K Ab-R1狀態(tài)5存在“歸約移進”沖突，狀態(tài) 9存在“歸約歸約”沖突，因此該文法不是LR(0)文法。狀態(tài)5:FOLLOW(男a,因止匕 FOLLOW(B) b:狀態(tài)9:FOLLOW(男a, FOLLOW(A> #, b,c,因止匕 FOLLOW(B) FOLLOW(A) =狀態(tài)5和狀態(tài)9的沖突均可用SLR(1)方法解決，構(gòu)造SLR(1)分析表 如下：狀態(tài)ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1該SLR(1)分析表無重定義，因此該文法是 SLR(1)文法，不是LR(0) 文法。八、語義分析題1、將語句if (A<0)(B>0) then while (C>0) do C:=C-D翻譯成四元式答案：100 (j< , A, 0, 104)101 (j , - , - , 102)102 (j> , B, 0, 104)103 (j , - , - , 109)104 (j> , C