编译原理复习题2

ET*F二、观点题1、设有文法：P→P+Q|QQ→Q*R|RR→(P)|i1）证明Q*R+Q+Q是它的一个句型。（3分)2）给出Q*R+Q+Q的全部短语，直接短语和句柄。(4分)3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)4）给出句子ｉ+ｉ*ｉ的最左推导。(4分)2、设有文法：E→E+T|TT→T*F|FF→(E)|i（1）证明E+T*F是它的一个句型。（3分)答案：EET（2）给出E+T*F的全部短语，直接短语和句柄。(4分)短语:E+T*F,T*F,直接短语:T*F句柄:T*F（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)3、写出表达式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|ab给出下边语言的相应文法L2={anbnci|n≥1,i≥0}答案：S→AB|BA→a|aAB→bBc|bc给出下边语言的相应文法L3={anbncm|m,n≥1，n为奇数，m为偶数}。答案：文法G(S):S→ACA→aaAbb/abC→ccCcc/cc四、词法剖析题1、结构下边正规式相应的DFA((0|1)*|(11)*)*（要求：先将正规式转变为NFA，再将NFA确立化，最小化）2、结构下边正规式相应的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}3、结构一个DFA，它接受={a，b}上全部包括ab的字符串。（要求：先将正规式转变为NFA，再将NFA确立化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*(二)①与此正规式对应的NFA为②状态变换矩阵为：③最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}baaab013b④所以此等价的DFA为：开始状态为0，终态集为{3}，状态集为{0,1,3}，输入字母表是{a,b}状态变换图如上。4、结构与正规式b(a|b)*ba等价的DFA五、语法剖析题1、对下边的文法G:Expr→-ExprExpr→(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε1）结构LL(1)剖析表。（12分）答案：（1）FIRST(Expr)={_,(,id}FIRST(ExprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(ε,}FOLLOW(Expr)={#,)}FOLLOW(ExprTail)={#,)}FOLLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}（2）给出对句子id—id((id))的剖析过程。（8分）步骤符号栈输入串所用产生式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→VarExprTail17#ExprTail))ExprTailVarTailidid))＃Var→idVarTail18#ExprTail))ExprTailVarTail))＃19#ExprTail))ExprTail))＃VarTail→ε20#ExprTail))))＃ExprTail→ε21#ExprTail))＃22#ExprTail#ExprTail→ε23##剖析成功2、对下边的文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧（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,^,+,),#}（2）证明这个文法是LL(1)的。（6分）答案：考虑以下产生式:EE|TT|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)文法.（3）结构它的展望剖析表。（6分）3、已知文法G[S]为：S->a|(T)T->T,S|S①除去文法G[S]中的左递归，得文法G′[S]。②文法G′[S]能否为LL(1)的假如，给出它的展望剖析表。4、对下边的文法G:SSaT|aT|aTTaT|a除去该文法的左递归和提取左公因子；结构各非终结符的FIRST和FOLLOW会合；结构该文法的LL(1)剖析表，并判断该文法是不是LL(1)的。答案：5、文法G(S)及其LR剖析表以下，请给出串baba#的剖析过程。(1)S→DbB(2)D→d(3)D→ε(4)B→a(5)B→Bba(6)B→εLR剖析表ACTIONGOTObDa#SBD0r3s3121accs4r24r6S5r665r4r46s7r17S88r5r5答案：步骤状态符号输入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc六、语法剖析题考虑文法:S→AS|bA→SA|a1）列出这个文法的全部LR(0)项目。（5分）答案0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb

7.ASA8.ASA9.ASA10.Aa11.Aa2）给出辨别文法全部活前缀的DFA。（5分）3）求全部非终结符的FOLLOW集。（5分）4）文法是SLR文法吗假如，结构出它的SLR剖析表,不然说明原因。5分）不是SLR文法状态3，6，7有移进归约矛盾状态3：FOLLOW(S’)={#}不包括a,b状态6：FOLLOW(S)={#,a,b}包括a,b,；移进归约矛盾没法消解状态7：FOLLOW(A)={a,b}包括a,b；移进归约矛盾消解所以不是SLR文法。七、证明题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→}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结构LR(0)项目集规范族：状态项目集变换函数0S→·AGO[0，A]＝1A→·AbGO[0，A]＝1A→·bBaGO[0，b]＝21S→A·ACCEPTA→A·bGO[1，b]＝32A→b·BaGO[2，B]＝4B→·aAcGO[2，a]＝5B→·aGO[2，a]＝5B→·aAbGO[2，a]＝53A→Ab·R14A→bB·aGO[4，a]＝65→a·Ac，A]＝7BGO[5B→a·R4B→a·AbGO[5，A]＝7A→·AbGO[5，A]＝7A→·bBaGO[5，b]＝26A→bBa·R27B→aA·cGO[7，c]＝8B→aA·bGO[7，b]＝9A→A·bGO[7，b]＝98B→aAc·R39→·R5BaAbA→Ab·R1状态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)剖析表如下：ACTIONGOTO状态abc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)剖析表无重定义，所以该文法是SLR(1)文法，不是LR(0)文法。八、语义剖析题1、将语句if((A<0)(B>0))thenwhile(C>0)doC:=C-D翻译成四元式答案：100(j<，A，0，104)101(j，-，-，102)102(j>，B，0，104)103(j，-，-，109)104(j>，C