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

1、1、 給出下面語言的相應(yīng)文法 。 L1=anbnci|n1,i0答案： S AB|B A a|aA B bBc|bc 2給出下面語言的相應(yīng)文法L1=anbncmdm| m,n1，n為奇數(shù)，m為偶數(shù)。答案：文法G(S):SAC AaaAbb/ab CccCcc/cc3、構(gòu)造一個DFA，它接受S=a，b上所有包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）(一) 相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二) 與此正規(guī)式對應(yīng)的NFA為答案；在自己寫的紙上4、對下面的文法G:ETE E+E| TFT TT|FPF F *F| P(E)|a|b|（1） 證明這個文法是LL

2、(1)的?？紤]下列產(chǎn)生式:E -E|T -T|F -*F |P -(E) |a|bFIRST(+E)FIRST()=+= 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()= 所以,該文法式LL(1)文法.計算這個文法的每個非終結(jié)符的FIRST和FOLLOW。（8分）答案：FIRST(E)=(,a,b, FIRST(

3、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,+,),# （3）構(gòu)造它的預(yù)測分析表。（6分）答案；在手機上寫出表達式a+b*(c-d)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (

4、1) - c d (2) * b (1) (3) + a (2) 給出下面語言的相應(yīng)文法L1=anbnambm|n,m0給出下面語言的相應(yīng)文法答案： SAB|A|B| A aAb|ab B aBb|abL2=anbnci|n1,i0給出下面語言的相應(yīng)文法答案： S AB|B A a|aA B bBc|bc 17、對下面的文法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)的。18、文法G(S)及其LR分析表如下，請給出串b

5、aba#的分析過程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案： 步驟 狀態(tài) 符號 輸入串 0 0 # baba# 1 02 #D baba# 2 024 #Db aba# 3 0245 #Dba ba# 4 0246 #DbB ba# 5 02467 #DbBb a# 6 024678 #DbBba # 7 0246 #DbB # 8 01 #S # acc 七、證明題1、證明下面文法是LL(1)的但不是SLR(1

6、)的。SAaAb|BbBaAB首先該文法無左遞歸存在,沒有公共左因子。 其次:對于SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=b FIRST(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= SAaAb. I9= SBbBa. 考察I0: FOLLOW(A)=a,b

7、 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：SA 1：AAb 2：AbBa 3：BaAc 4：Ba 5：BaAb狀態(tài)5存在“歸約移進”沖突，狀態(tài)9存在“歸約歸約”沖突，因此該文法不是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)方

8、法解決，構(gòu)造SLR(1)分析表該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)108 (j， -， -， 104)1092、寫出下面語句經(jīng)語法制導(dǎo)翻譯后所生成的四元式代碼序列。 if xc do c:=c+1 else x:=x+5答案：假設(shè)初始

9、為100，則四元式代碼序列為 100ifxcgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1097、設(shè)有文法：EE+T|TTT*F|FF(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分)沒有 答案10、11、構(gòu)造下面正規(guī)式相應(yīng)的DFA1(0|1)*101答案： I I0 I1 X A,B,C A,B,C B,C B,C,D B,C B,C B,C,

10、D B,C,D B,C,E B,C,D B,C,E B,C B,C,D,y B,C,D,y B,C,E B,C,D14、對下面的文法G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |（1）構(gòu)造LL(1)分析表。（12分）（2）給出對句子idid(id)的分析過程。（8分）答案： （1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(

11、ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) （2） 給出對句子idid(id)的分析過程。（步驟 符號棧 輸入串 所用產(chǎn)生式 0 Expr id_ _id(id) 1 # ExprTail Var id_ _id(id) ExprVar ExprTail 2 # ExprTail VarTail id id_ _id(id) Varid VarTail 3 # ExprTail VarTail _ _id(id) 4 # ExprTail _ _id(id) VarTail5 # Expr_ _ _id(

12、id) ExprTail_ Expr 6 # Expr _id(id) 7 # Expr_ _id(id) Expr_Expr 8 # Expr id(id)9 # ExprTail Var id(id) ExprVar ExprTail 10 # ExprTail VarTail id id(id) Varid VarTail 11 # ExprTail VarTail (id) 12 # ExprTail )Expr( (id) VarTail(Expr) 13 # ExprTail )Expr (id) 14 # ExprTail ) )Expr( (id) Expr(Expr) 15 # ExprTail ) )Expr id) 16 # ExprTail ) ) ExprTail Var id) ExpVarExprTai 17 # ExprTail ) ) E