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

1、1、 給出下面語(yǔ)言的相應(yīng)文法 。 L1=a nbnci |n 1,i 0答案： S AB|BA a|aAB bBc|bc2給出下面語(yǔ)言的相應(yīng)文法L1= anbncmdm| m,n 1，n 為奇數(shù)， m為偶數(shù) 。答案：文法 G(S):S ACA aaAbb/abC ccCcc/cc3、構(gòu)造一個(gè) DFA，它接受 =a ，b上所有包含 ab 的字符串。(要求：先將正規(guī)式轉(zhuǎn)化為 NFA，再將 NFA確定化，最小化) ( 一 ) 相應(yīng)的正規(guī)式為 (a|b)*ab(a|b)*( 二 ) 與此正規(guī)式對(duì)應(yīng)的 NFA為答案；在自己寫(xiě)的紙上4、對(duì)下面的文法 G:ETE E +E| T FT T T| FPF F

2、*F| P (E)|a|b| (1) 證明這個(gè)文法是 LL(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) 文法.計(jì)算這個(gè)文法的每個(gè)非

3、終結(jié)符的 FIRST和 FOLLO。W(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,+,),#(3)構(gòu)造它的預(yù)測(cè)分析表。 (6 分)答案；在手機(jī)上寫(xiě)出表達(dá)式 a+b*(c-d) 對(duì)應(yīng)的逆波蘭式和三

4、元式序列。答案：逆波蘭式： (abcd-*+)三元式序列 :OPARG1ARG2(1) -cd(2) *b(1)(3) +a(2)給出下面語(yǔ)言的相應(yīng)文法L1=a nbnambm|n,m 0給出下面語(yǔ)言的相應(yīng)文法答案： S AB|A|B| A aAb|abB aBb|abL2=a nbnci |n 1,i 0給出下面語(yǔ)言的相應(yīng)文法答案： S AB|BA a|aAB bBc|bc17、對(duì)下面的文法 G:SS a T | a T |a TTa T |a(1) 消除該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的 FIRST和 FOLLOW集合；(3) 構(gòu)造該文法的 LL(1) 分析表，并判斷該

5、文法是否是 LL(1) 的18、文法 G(S)及其 LR 分析表如下，請(qǐng)給出串 baba#的分析過(guò)程。 (1) S DbB (2) D d(3) D (4) B a(5) B Bba(6) B LR 分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案： 步驟 狀態(tài) 符號(hào) 輸入串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

6、 # acc七、證明題1、證明下面文法是 LL(1) 的但不是 SLR(1)的。SAaAb|BbBaAB首先該文法無(wú)左遞歸存在 , 沒(méi)有公共左因子。其次:對(duì)于 SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb)FIRST(BbBa)=所以該文法是 LL(1) 文法。(2) 證明該文法不是 SLR的。文法的 LR(0) 項(xiàng)目集規(guī)范族為 :I0=S .S S .AaAb S.BbBa A. B .I1= S S. I2= S A.aAb I3= S B.bBa I4= S Aa.Ab A. I5= S Bb.Ba B. I6= S AaA.b I7=

7、 S BbB.a I8= S AaAb. I9= S BbBa. 考察 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狀態(tài) 5存在“歸約移進(jìn)”沖突，狀態(tài) 9存在“歸約歸約”沖突，因此該文法不是 LR(0) 文法。狀態(tài) 5： FOLLOW(B) a，因此， FOLLOW(B) b狀態(tài) 9： FOLLO

8、W(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)分析表該 SLR（1） 分析表無(wú)重定義，因此該文法是 SLR（1）文法，不是 LR（0） 文法。八、語(yǔ)義分析題1、將語(yǔ)句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， -

9、， C）108 （j ， - ， - ， 104）1092、 寫(xiě)出下面語(yǔ)句經(jīng)語(yǔ)法制導(dǎo)翻譯后所生成的四元式代碼序列。 if xc do c:=c+1 else x:=x+5答案： 假設(shè)初始為 100，則四元式代碼序列為100ifxcgoto103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1097、設(shè)有文法：EE+T|TTT*F|FF(E)|i1041021）證明 E+T*F是它的一個(gè)句型。（3 分）： ?*2）給出 E+T*F的所有短語(yǔ)，直接短語(yǔ)和句柄。 （4 分） 短語(yǔ): E+T*F, T*F, 直接短語(yǔ) : T*F句柄: T*F3）給出

10、句子 +* 的最右推導(dǎo)。 （4 分 ）沒(méi)有 答案10、11、構(gòu)造下面正規(guī)式相應(yīng)的 DFA1(0|1) * 101答案： II0 I1X A,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,E B,C,DB,C,E B,C B,C,D,yB,C,D,y B,C,E B,C,D14、對(duì)下面的文法 G:Expr - ExprExpr (Expr)|Var ExprTailExprTail - Expr| Var id VarTailVarTail (Expr) | (1)構(gòu)造 LL(1) 分析表。(12 分)(2)給出對(duì)句子 id id(id) 的分析過(guò)程。(8 分

11、)答 案 ： ( 1 ) FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) (2) 給出對(duì)句子 id id(id) 的分析過(guò)程。(步驟 符號(hào)棧 輸入串 所用產(chǎn)生式0 Exprid_ _id(id) 1 # ExprTail Var id_ _id(id) ExprTail VarTail id id_ _id

12、(id) Expr Var ExprTail 2 # Var id VarTail3 # ExprTail VarTail _ _id(id)4 # ExprTail _ _id(id) VarTail 5 # Expr_ _ _id(id)6 # Expr _id(id)7 # Expr_ _id(id) ExprTail _ Expr Expr _Expr8 # Expr id(id) 9 # ExprTail Var id(id) Expr Var ExprTail10 # ExprTail VarTail id id(id) Var id VarTail11 # 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) Exp VarExprTai17 # ExprTa