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

《编译原理复习题--有答案版.pdf》由会员分享，可在线阅读，更多相关《编译原理复习题--有答案版.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、给出下面语言的相应文法。L1=anbnci|n1,i0答案：S AB|BA a|aAB bBc|bc2给出下面语言的相应文法L1=anbncmdm|m,n1，n 为奇数，m 为偶数。答案：文法 G(S):SAC AaaAbb/ab CccCcc/cc3、构造一个 DFA，它接受=a，b上所有包含 ab 的字符串。（要求：先将正规式转化为 NFA，再将 NFA确定化，最小化）(一)相应的正规式为(a|b)*ab(a|b)*(二)与此正规式对应的 NFA为答案；在自己写的纸上4、对下面的文法 G:ETEE+E|TFTTT|FPFF*F|P(E)|a|b|（1）证明这个文法是 LL(1)的。考虑

2、下列产生式: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,

3、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-*+)三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)给出下面语言的相应文法L

4、1=anbnambm|n,m0给出下面语言的相应文法答案：SAB|A|B|A aAb|abB aBb|abL2=anbnci|n1,i0给出下面语言的相应文法答案：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(4)B a(2)D d(3)D (6)B (5)B BbaLR

5、 分析表ACTIONb012345678r5GOTO#Ds3aS1BD2r3s4r2r6r4s7accS5r6r4r16S8r5答案：步骤状态符号输入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc七、证明题1、证明下面文法是 LL(1)的但不是 SLR(1)的。SAaAb|BbBaAB首先该文法无左递归存在,没有公共左因子。其次:对于 SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb)FIRST

6、(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=SAaAb.I9=SBbBa.考察 I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)FOLLOW(B)=a,b产生规约-规约冲突。所以该文法不是 SLR(1)文法。2、证明下面文法是 SLR(1)但不是 LR(0)的。SAAAb|bBaBaAc|a|aAb解：文法 GS：0：SA1：AAb2：AbBa3：BaAc4：

7、Ba5：BaAb状态 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(A0)thenwhile(C0)doC:=C-D翻译成四元式答案：100(j，B，0，104)103(j，-，-，109)104

8、(j，C，0，106)105(j，-，-，109)106(-，C，D，T1)107(:=，T1，-，C)108(j，-，-，104)1092、写出下面语句经语法制导翻译后所生成的四元式代码序列。写出下面语句经语法制导翻译后所生成的四元式代码序列。if xc doif xc doc:=c+1 else x:=x+5c:=c+1 else x:=x+5答案：假设初始为 100，则四元式代码序列为100ifxcgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1097、设有文法：EE+T|TTT*F|FF(E)|i（1）证明 E+T

9、*F 是它的一个句型。（3 分)：?*（2）给出 E+T*F 的所有短语，直接短语和句柄。(4 分)短语:E+T*F,T*F,直接短语:T*F句柄:T*F（3）给出句子+*的最右推导。(4 分)没有 答案10、11、构造下面正规式相应的 DFA1(0|1)*101答案：II0I1XA,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,CB,C,D,yB,C,D,yB,C,E B,C,D14、对下面的文法 G:Expr-ExprExpr(Expr)|Var ExprTailExprTail-Expr|Varid VarTailVarT

10、ail(Expr)|（1）构造 LL(1)分析表。（12 分）（2）给出对句子 idid(id)的分析过程。（8 分）答案：（1）FIRST(Expr)=_,(,id FIRST(ExprTail)=_,FIRST(Var)=idFIRST(VarTail)=(,FOLLOW(Expr)=#,)FOLLOW(ExprTail)=#,)FOLLOW(Var)=_,#,)FOLLOW(VarTail)=_,#,)（2）给出对句子 idid(id)的分析过程。（步骤符号栈输入串所用产生式0Exprid_ _id(id)1#ExprTail Varid_ _id(id)ExprVar ExprTail

11、 2#ExprTailVarTail id id_ _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 ExprTail10#ExprTail VarTail id id(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)ExpVarExprTai17#ExprTail)ExprTail VarTail id id)Varid VarTail18#ExprTail)ExprTail VarTail)19#ExprTail)ExprTail)VarTail20#ExprTail)ExprTail21#ExprTail)22#ExprTail#ExprTail23#分析成功