当前位置:文档之家› 编译原理复习题--有答案版

编译原理复习题--有答案版

1、给出下面语言的相应文法。

L1={a n b n c i|n≥1,i≥0}答案: S→ AB|BA→ a|aAB→ bBc|bc2.给出下面语言的相应文法L1={a n b n c m d m| m,n≥1,n为奇数,m为偶数}。

答案:文法G(S):S→ACA→aaAbb/abC→ccCcc/cc3、构造一个DFA,它接受={a,b}上所有包含ab的字符串。

(要求:先将正规式转化为NFA,再将NFA确定化,最小化)(一)相应的正规式为(a|b)*ab(a|b)*(二)①与此正规式对应的NFA为答案;在自己写的纸上4、对下面的文法G:E→TE’ E’→+E|ε T→FT’ T’→T|εF→PF’ F’→*F’|ε P→(E)|a|b|∧(1)证明这个文法是LL(1)的。

考虑下列产生式: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)文法.计算这个文法的每个非终结符的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,^,+,),#}(3)构造它的预测分析表。

(6分)答案;在手机上写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。

答案:逆波兰式:(abcd-*+)三元式序列:OP ARG1 ARG2(1) - c d(2) * b (1)(3) + a (2)给出下面语言的相应文法L1={a n b n a m b m|n,m≥0}给出下面语言的相应文法答案: S→AB|A|B|∑A→ aAb|abB→ aBb|abL2={a n b n c i|n≥1,i≥0}给出下面语言的相应文法答案: S→ AB|BA→ a|aAB→ bBc|bc17、对下面的文法G:S S a T | a T | a TT a T | a(1) 消除该文法的左递归和提取左公因子;(2) 构造各非终结符的FIRST和FOLLOW集合;(3) 构造该文法的LL(1)分析表,并判断该文法是否是LL(1)的。

18、文法G(S)及其LR分析表如下,请给出串baba#的分析过程。

(1) S → DbB(2) D → d(3) D → ε(4) B → a(5) B → Bba(6) B → εLR分析表ACTION GOTOb D a#S B D0r3s312答案:步骤状态符号输入串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)的。

S→AaAb|BbBaA→εB→ε首先该文法无左递归存在,没有公共左因子。

其次:对于S→AaAb|BbBa FIRST(AaAb)={a} FIRST(BbBa)={b} FIRST(AaAb)∩FIRST(BbBa)=Φ所以该文法是LL(1)文法。

(2)证明该文法不是SLR的。

文法的LR(0)项目集规范族为:I0={S’→.S S→.AaAb S→.BbBa A→. B→.}I1={ S’→ S. }I2={ S→ }I3={ S→ }I4={ S→ A→. }I5={ S→ B→. }I6={ S→ }I7={ S→ }I8={ S→AaAb. }I9={ S→BbBa. }考察I0:FOLLOW(A)={a,b} FOLLOW(B)={a,b} FOLLOW(A)∩FOLLOW(B)= {a,b} 产生规约-规约冲突。

所以该文法不是SLR(1)文法。

2、证明下面文法是SLR(1)但不是LR(0)的。

S→AA→Ab|bBaB→aAc|a|aAb解:文法G[S]:0:S→A1:A→Ab2:A→bBa3:B→aAc4:B→a5:B→aAb状态5存在“归约-移进”冲突,状态9存在“归约-归约”冲突,因此该文法不是LR(0)文法。

状态5: FOLLOW(B)={a},因此,FOLLOW(B)∩{b}=Φ状态9: FOLLOW(B)={a},FOLLOW(A)={#,b,c},因此FOLLOW(B)∩FOLLOW(A)=Φ状态5和状态9的冲突均可用SLR(1)方法解决,构造SLR(1)分析表该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)105 (j, -, -, 109)106 (-, C, D, T1)107 (:=, T1, -, C)108 (j, -, -, 104)1092、写出下面语句经语法制导翻译后所生成的四元式代码序列。

if x<y then while e>c do c:=c+1 else x:=x+5答案:假设初始为100,则四元式代码序列为100if x<y goto102101goto107102if e>c goto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1097、设有文法:E→E+T|TT→T*F|FF→(E)|i(1)证明E+T*F是它的一个句型。

(3分):*(2)给出E+T*F的所有短语,直接短语和句柄。

(4分)短语: E+T*F, T*F,直接短语: T*F句柄: T*F(3)给出句子i+i*i的最右推导。

(4分)没有答案10、11、构造下面正规式相应的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,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,D}14、对下面的文法G:Expr→- ExprExpr→(Expr)|Var ExprTailExprTail→- Expr|εVar→id VarTailVarTail→(Expr) |ε(1)构造LL(1)分析表。

(12分)(2)给出对句子id—id((id))的分析过程。

(8分)答案:(1)FIRST(Expr)={_ , ( , id } FIRST(ExprTail)={_ , ε }FIRST(Var)={id} FIRST(VarTail)={ ( , ε}FOLLOW(Expr)={# , ) } FOLLOW(ExprTail) ={# , ) } FOLLOW(Var) ={_ , # , ) } FOLLOW(VarTail) ={_ , # , ) }(2)给出对句子id—id((id))的分析过程。

(步骤符号栈输入串所用产生式0 #Expr id_ _id((id))#1 # ExprTail Var id_ _id((id))# Expr→Var ExprTail2 # ExprTail VarTail id id_ _id((id))# Var→id VarTail3 # ExprTail VarTail _ _id((id))#4 # ExprTail _ _id((id))# VarTail→ε5 # Expr_ _ _id((id))# ExprTail→_ Expr6 # Expr _id((id))#7 # Expr_ _id((id))# 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 # ExprTail ) ) ExprTail VarTail id id))# Var→id VarTail18 # ExprTail ) ) ExprTail VarTail ))#19 # ExprTail ) ) ExprTail ))# VarTail→ε20 # ExprTail ) ) ))# ExprTail→ε21 # ExprTail ) )#22 # ExprTail # ExprTail→ε23 # # 分析成功。

相关主题