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

1、给出下面语言的相应文法。L1={anbnci|n≥1,i≥0}答案：S→AB|BA→a|aAB→bBc|bc2．给出下面语言的相应文法L1={anbncmdm|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-*+)三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)给出下面语言的相应文法L1={anbnambm|n,m≥0}给出下面语言的相应文法答案：S→AB|A|B|∑A→aAb|abB→aBb|abL2={anbnci|n≥1,i≥0}给出下面语言的相应文法答案：S→AB|BA→a|aAB→bBc|bc17、对下面的文法G:SSaT|aT|aTTaT|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分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案：步骤状态符号输入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc七、证明题1、证明下面文法是LL(1)的但不是SLR(1)的。S→AaAb|BbBaA→εB→ε首先该文法无左递归存在,没有公共左因子。其次:对于S→AaAb|BbBaFIRST(AaAb)={a}FIRST(BbBa)={b}FIRST(AaAb)∩FIRST(BbBa)=Φ所以该文法是LL(1)文法。(2)证明该文法不是SLR的。文法的LR(0)项目集规范族为:I0={S’→.SS→.AaAbS→.BbBaA→.B→.}I1={S’→S.}I2={S→A.aAb}I3={S→B.bBa}I4={S→Aa.AbA→.}I5={S→Bb.BaB→.}I6={S→AaA.b}I7={S→BbB.a}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((A0)(B0))thenwhile(C0)doC:=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、写出下面语句经语法制导翻译后所生成的四元式代码序列。ifxythenwhileecdoc:=c+1elsex:=x+5答案：假设初始为100，则四元式代码序列为100ifxygoto102101goto107102ifecgoto104103goto109104M:=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）给出句子ｉ+ｉ*ｉ的最右推导。(4分)没有答案10、11、构造下面正规式相应的DFA1(0|1)*101答案：II0I1{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)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(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＃Exprid__id((id))＃1#ExprTailVarid__id((id))＃Expr→VarExprTail2#ExprTailVarTailidid__id((id))＃Var→idVarTail3#ExprTailVarTail__id((id))＃4#ExprTail__id((id))＃VarTail→ε5#Expr___id((id))＃ExprTail→_Expr6#Expr_id((id))＃7#Expr__id((id))＃Expr→_Expr8#Exprid((id))＃9#ExprTailVarid((id))＃Expr→VarExprTail10#ExprTailVarTailidid((id))＃Var→idVarTail11#ExprTailVarTail((id))＃12#ExprTail)Expr(((id))＃VarTail→(Expr)13#ExprTail)Expr(id))＃14#ExprTail))Expr((id))＃Expr→(Expr)15#ExprTail))Exprid))＃16#ExprTail))ExprTailVarid))＃Exp→VarExprTai17#ExprTail))ExprTailVarTailidid))＃Var→idVarTail18#ExprTail))ExprTailVarTail))＃19#ExprTail))ExprTail))＃VarTail→ε20#ExprTail))))＃ExprTail→ε21#ExprTail))＃22#ExprTail#ExprTail→ε23##分析成功