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

1、二、概念題1、設(shè)有文法：PP+Q|QQQ*R|RR(P)|i（1）證明Q*R+Q+Q是它的一個句型。（3分)（2）給出Q*R+Q+Q的所有短語，直接短語和句柄。(4分)（3）給出句子+*的最右推導(dǎo)。(4分)（4）給出句子+*的最左推導(dǎo)。(4分)2、設(shè)有文法：EE+T|T TT*F|F F(E)|i（1）證明E+T*F是它的一個句型。（3分)答案：（2）給出E+T*F的所有短語，直接短語和句柄。(4分)短語: E+T*F, T*F,直接短語: T*F句柄: T*F（3）給出句子+*的最右推導(dǎo)。(4分)3、寫出表達式a+b*(c-d)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+)

2、三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 三、詞法分析題給出下面語言的相應(yīng)文法L1=anbnambm|n,m0答案：  SAB|A|B| A aAb|ab B aBb|ab給出下面語言的相應(yīng)文法L2=anbnci|n1,i0答案： S AB|B    A a|aA B bBc|bc給出下面語言的相應(yīng)文法L3=anbncm| m,n1，n為奇數(shù)，m為偶數(shù)。答案：文法G(S):SAC

3、AaaAbb/ab CccCcc/cc 四、詞法分析題1、構(gòu)造下面正規(guī)式相應(yīng)的DFA(0|1)*|(11)*)*（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）2、構(gòu)造下面正規(guī)式相應(yīng)的DFA1(0|1)*101答案：I        I0        I1 X         A,B,C  A,B,C    

4、0;B,C      B,C,D  B,C      B,C      B,C,D  B,C,D     B,C,E    B,C,D B,C,E     B,C     B,C,D,y B

5、,C,D,y   B,C,E      B,C,D3、構(gòu)造一個DFA，它接受S=a，b上所有包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）答案：(一)相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二) 與此正規(guī)式對應(yīng)的NFA為狀態(tài)轉(zhuǎn)換矩陣為： 最小化：0，1，2 3，4，50， 2，1， 3，4，5baa01b3ba所以此等價的DFA為：開始狀態(tài)為0 ，終態(tài)集為3 ，狀態(tài)集為0,1,3 ，輸入字母表是a,b 狀態(tài)轉(zhuǎn)換圖如上。4、構(gòu)造與正規(guī)式 b(a|b)*ba 等價的DFA五、

6、語法分析題1、對下面的文法G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |（1） 構(gòu)造LL(1)分析表。（12分）答案：（1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) （2） 給出對句子idi

7、d(id)的分析過程。（8分）步驟 符號棧 輸入串所用產(chǎn)生式0Expr id_ _id(id)1# ExprTail Var id_ _id(id)ExprVar ExprTail2# ExprTail VarTail idid_ _id(id)Varid VarTail3# ExprTail VarTail_ _id(id)4# ExprTail_ _id(id)VarTail5# Expr_ _id(id) ExprTail_ Expr6# Expr_id(id)7# Expr_id(id)Expr_Expr8# Exprid(id)9# ExprTail Varid(id)ExprVar

8、 ExprTail10# ExprTail VarTail idid(id)Varid VarTail11# ExprTail VarTail(id) 12# ExprTail )Expr(id)VarTail(Expr)13# ExprTail )Expr(id)14# ExprTail ) )Expr(id)Expr(Expr)15# ExprTail ) )Exprid)16 # ExprTail ) )ExprTail Varid)ExpVar ExprTail17# ExprTail ) )ExprTail VarTail idid)Varid VarTail18# ExprTail

9、 ) )ExprTail VarTail )19# ExprTail ) )ExprTail)VarTail20# ExprTail ) )ExprTail21# ExprTail )22# ExprTail #ExprTail23# #分析成功2、對下面的文法G:ETEE+E|TFTTT|FPFF *F|P(E)|a|b|（1） 計算這個文法的每個非終結(jié)符的FIRST和FOLLOW。（8分）答案：FIRST(E)=(,a,b,FIRST(E')=+,FIRST(T)=(,a,b,FIRST(T')=(,a,b,FIRST(F)=(,a,b,FIRST(F')=*,FI

10、RST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F')=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#（2） 證明這個文法是LL(1)的。（6分）答案：考慮下列產(chǎn)生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E')=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T')=(,a,b,+,),#=FIRST(*F'

11、;)FIRST()=*=FIRST(*F')FOLLOW(F')=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,該文法式LL(1)文法.（3） 構(gòu)造它的預(yù)測分析表。（6分）3、已知文法GS 為： S->a|(T)T->T,S|S 消除文法GS中的左遞歸，得文法G´S。 文法G´S是否為LL(1)的？若是，給出它的預(yù)測分析表。4、對下面的文法G:S ® S Ú a T | a T | Ú a TT ® Ù a T | Ù a(1) 消除

12、該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。答案：5、文法G(S)及其LR分析表如下，請給出串baba#的分析過程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案：步驟狀態(tài)符號輸入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#

13、6024678#DbBba#70246#DbB#801#S#acc16六、語法分析題考慮文法:SAS|b ASA|a（1） 列出這個文法的所有LR(0) 項目。（5分）答案0.1.2.3.4.5.6.7.8.9.10.11.（2）給出識別文法所有活前綴的DFA。（5分）（3）求所有非終結(jié)符的FOLLOW集。（5分）（4）文法是SLR文法嗎？若是，構(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；移進

14、歸約沖突消解所以不是SLR文法。七、證明題1、證明下面文法是LL(1)的但不是SLR(1)的。SAaAb|BbBaAB首先該文法無左遞歸存在,沒有公共左因子。其次:對于SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb)FIRST(BbBa)=所以該文法是LL(1)文法。(2)證明該文法不是SLR的。文法的LR(0)項目集規(guī)范族為:I0=S.S S.AaAb S.BbBa A. B.I1= S S. I2= SA.aAb I3= SB.bBa I4= SAa.Ab A. I5= SBb.Ba B. I6= SAaA.b I7= SBbB.a I8=

15、 SAaAb. I9= SBbBa. 考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)FOLLOW(B)= a,b產(chǎn)生規(guī)約-規(guī)約沖突。所以該文法不是SLR(1)文法。2、證明下面文法是SLR(1)但不是LR(0)的。SAAAb|bBaBaAc|a|aAb解：文法GS：0：SA1：AAb2：AbBa3：BaAc4：Ba5：BaAb構(gòu)造LR(0)項目集規(guī)范族：狀態(tài)項目集轉(zhuǎn)換函數(shù)0S·AA·AbA·bBaGO0，A1GO0，A1GO0，b21SA·AA·bACCEPTGO1，b32Ab·BaB·

16、aAcB·aB·aAbGO2，B4GO2，a5GO2，a5GO2，a53AAb·R14AbB·aGO4，a65Ba·AcBa·Ba·AbA·AbA·bBaGO5，A7R4GO5，A7GO5，A7GO5，b26AbBa·R27BaA·cBaA·bAA·bGO7，c8GO7，b9GO7，b98BaAc·R39BaAb·AAb·R5R1狀態(tài)5存在“歸約移進”沖突，狀態(tài)9存在“歸約歸約”沖突，因此該文法不是LR(0)文法。狀態(tài)5：FOLLOW(

17、B)a，因此，F(xiàn)OLLOW(B)b狀態(tài)9：FOLLOW(B)a，F(xiàn)OLLOW(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， 0， 106)10