編譯原理復(fù)習(xí)題答案(共12頁)

1、PAGE PAGE 13二、概念(ginin)題1、設(shè)有文法(wnf)：PP+Q|QQQ*R|RR(P)|i（1）證明(zhngmng)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、寫出表達(dá)式a+b*(c-d

2、)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 三、詞法分析題給出下面語言的相應(yīng)文法L1=anbnambm|n,m0答案：SAB|A|B|AaAb|abBaBb|ab給出下面語言(yyn)的相應(yīng)文法L2=anbnci|n1,i0答案(d n)：SAB|BAa|aABbBc|bc給出下面(xi mian)語言的相應(yīng)文法L3=anbncm| m,n1，n為奇數(shù)，m為偶數(shù)。答案：文法G(S):SAC AaaAbb/ab CccCcc/cc 四、詞法分析題1、構(gòu)造下面正規(guī)式相應(yīng)

3、的DFA(0|1)*|(11)*)*（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）2、構(gòu)造下面正規(guī)式相應(yīng)的DFA1(0|1)*101答案：I I0 I1X A,B,CA,B,C B,CB,C,DB,C B,CB,C,DB,C,DB,C,E B,C,DB,C,EB,CB,C,D,yB,C,D,yB,C,EB,C,D3、構(gòu)造(guzo)一個DFA，它接受(jishu)=a，b上所有(suyu)包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）答案：(一)相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二) 與此正規(guī)式對應(yīng)的NFA為狀態(tài)轉(zhuǎn)換矩陣為： 最小化：0，1，

4、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五、語法分析題1、對下面的文法G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |構(gòu)造(guzo)LL(1)分析表。（12分）答案(d n)：（1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(V

5、arTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) 給出對句子(j zi)idid(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

6、(id)VarTail5# Expr_ _id(id) ExprTail_ Expr6# Expr_id(id)7# Expr_id(id)Expr_Expr8# Exprid(id)9# ExprTail Varid(id)ExprVar 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

7、) )Exprid)# ExprTail ) )ExprTail Varid)ExpVar ExprTail17# ExprTail ) )ExprTail VarTail idid)Varid VarTail18# ExprTail ) )ExprTail VarTail )19# ExprTail ) )ExprTail)VarTail20# ExprTail ) )ExprTail21# ExprTail )22# ExprTail #ExprTail23# #分析(fnx)成功2、對下面(xi mian)的文法G:ETEE+E|TFTTT|FPFF *F|P(E)|a|b|計算這個(z

8、h ge)文法的每個非終結(jié)符的FIRST和FOLLOW。（8分）答案：FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#證明這個文法是LL(1)的。（6分）答案：考慮下列產(chǎn)生式:FIRST(+E)FIRST()=+

9、=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以(suy),該文法式(fsh)LL(1)文法(wnf).構(gòu)造它的預(yù)測分析表。（6分）3、已知文法GS 為： S-a|(T)T-T,S|S = 1 * GB3 消除文法GS中的左遞歸，得文法GS。 = 2 * GB3 文法GS是否為LL(1)的？若是，給出它的預(yù)測分析表。

10、4、對下面的文法G:S S a T | a T | a TT a T | a(1) 消除該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。答案：5、文法(wnf)G(S)及其LR分析(fnx)表如下，請給出串baba#的分析(fnx)過程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案：步驟狀態(tài)(zhungti)符號輸

11、入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc六、語法分析題考慮(kol)文法:SAS|b ASA|a列出這個文法的所有(suyu)LR(0) 項目。（5分）答案(d n)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有移進(jìn)歸約沖突狀態(tài)3：

12、FOLLOW(S)=#不包含a,b狀態(tài)6：FOLLOW(S)=#,a,b包含a,b,；移進(jìn)歸約沖突無法消解狀態(tài)7：FOLLOW(A)=a,b包含a,b；移進(jìn)歸約沖突消解所以不是SLR文法。七、證明題1、證明下面文法是LL(1)的但不是SLR(1)的。SAaAb|BbBaAB首先該文法無左 HYPERLINK /search?word=%E9%80%92%E5%BD%92&fr=qb_search_exp&ie=utf8 t _blank 遞歸存在,沒有公共左因子。其次:對于SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb)FIRST(BbBa)=

13、所以該文法是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= 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、證明下面(xi mian)文法是SLR(1)但不是LR(0)的。SAAAb|bBaB

14、aAc|a|aAb解：文法(wnf)GS：0：SA1：AAb2：AbBa3：BaAc4：Ba5：BaAb構(gòu)造(guzo)LR(0)項目集規(guī)范族：狀態(tài)項目集轉(zhuǎn)換函數(shù)0SAAAbAbBaGO0，A1GO0，A1GO0，b21SAAAbACCEPTGO1，b32AbBaBaAcBaBaAbGO2，B4GO2，a5GO2，a5GO2，a53AAbR14AbBaGO4，a65BaAcBaBaAbAAbAbBaGO5，A7R4GO5，A7GO5，A7GO5，b26AbBaR27BaAcBaAbAAbGO7，c8GO7，b9GO7，b98BaAcR39BaAbAAbR5R1狀態(tài)(zhungti)5存在“歸約

15、移進(jìn)”沖突，狀態(tài)(zhungti)9存在“歸約歸約”沖突(chngt)，因此該文法不是LR(0)文法。狀態(tài)5：FOLLOW(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 (A0) then while (C0) do C:=C-D翻譯成四元式答案：100 (j， B， 0， 104)103 (j， -， -， 109)104 (j， C， 0， 106)105 (j， -， -， 109)106 (-， C， D， T1)107 (:=， T1， -， C