您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 编译原理第4章习题解答
第4章习题解答:1,2,3,4解答略!5.解答:(1)×(2)√(3)×(4)√(5)√(6)√(7)×(8)×6.解答:(1)A:④B:③C:③D:④E:②(2)A:④B:④C:③D:③E:②7.解答:(1)消除给定文法中的左递归,并提取公因子:bexpr→bterm{orbterm}bterm→bfactor{andbfactor}bfactor→notbfactor|(bexpr)|true|false(2)用类C语言写出其递归分析程序:voidbexpr();{bterm();WHILE(lookahead=='or'){match('or');bterm();}}voidbterm();{bfactor();WHILE(lookahead=='and'){match('and');bfactor();}}voidbfactor();{if(llokahead=='not')then{match('not');bfactor();}elseif(lookahead=='(')then{match(‘(');bexpr();match(')');}elseif(lookahead=='true')thenmatch('true)elseif(lookahead=='false')thenmatch('false');elseerror;}8.解答:消除所给文法的左递归,得G':S→(L)|aL→SL'L'→,SL'|实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制,下面构造预测分析表:根据文法G'有:First(S)={(,a)Follow(S)={),,,#}First(L)={(,a)Follow(L)={)}First(L')={,}Follow(L')={)}按以上结果,构造预测分析表M如下:文法G'是LL(1)的,因为它的LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a))做出的分析动作如下:步骤栈剩余输入串输出1#S(a,(a,a))##2#)L(a,(a,a))#S→(L)3#)La,(a,a))#4#)L'Sa,(a,a))#L→SL'5#)L'aa,(a,a))#S→a6#)L',(a,a))#7#)L'S,,(a,a))#L'→,SL'8#)L'S(a,a))#9#)L')L((a,a))#S→(L)10#)L')La,a))#11#)L')L'Sa,a))#L→SL'12#)L')L'aa,a))#S→a13#)L')L',a))#14#)L')L'S,,a))#L'→,SL'15#)L')L'Sa))#16#)L')L'aa))#S→a17#)L')L'))#18#)L')))#L'→19#)L')#20#))#L'→21##9.解答:各非终结符的First集:First(S)={First(A)\{}}∪{First(B)\{}}∪{}∪{b}={a,b,}First(A)={b}∪{}={b,}First(B)={}∪{a}={a,}First(C)={First(A)\{}}∪First(D)∪First(b)={a,b,c}First(D)={a}∪{c}={a,c}各个候选式的First集为:First(AB)={a,b,}First(bC)={b}First()={}First(b)={b}First(aD)={a}First(AD)={a,b,c}First(b)={b}First(aS)={a}First(c)={c}各非终结符的Follow集的计算:Follow(S)={#}∪Follow(D)={#}Follow(A)=(First(B)\{})∪Follow(S)∪First(D)={a,#,c}Follow(B)=Follow(S)={#}Follow(C)=Follow(S)={#}Follow(D)=Follow(B)∪Follow(C)={#}10.解答:(1)求First和Follow集First(E)=First(T)={(,a,b,∧}⑦First(E')={+,}⑥First(T)=First(F)={(,a,b,∧}④First(T')={(,a,b,∧,}⑤First(F)=First(P)={(,a,b,∧}③First(F')={*,}②First(P)={(,a,b,∧}①(计算顺序)Follow(E)={#,)}Follow(E')=Follow(E)={#,)}(1)(使用的产生式)Follow(T)=First(E')\{}∪Follow(T')(1,2)={+}∪{),#}={+,),#}Follow(T')=Follow(T)={+,},#}(3)Follow(F)=First(T')\{}∪Follow(T)(3,4)={(,a,b,∧,+,),#}Follow(F')=Follow(F)(5)={(,a,b,∧,+,),#}Follow(P)=First(F')\{}∪Follow(F)(5,6)={*,(,a,b,∧,+,),#}(2)证明:∵a.文法不含左递归;b.每个非终结符的各个侯选式的First集不相交;c.First(E')∩Follow(E')={+,}∩{#,),}=First(T')∩Follow(T')={(,a,b,∧,}∩{+,)}=First(F')∩Follow(F')={*,}∩{,a,(∧,+,},#}=∴改造后的文法满足LL(1)文法的三个条件,是LL(1)文法。(3)预测分析表如下所示。ab*+∧()#EE→TE'E→TE'E→TE'E'E'→+EE'→E'→TT→FT'T→FT'T→FT'T→FT'T'T'→TT'→TT'→TT'→TT'→T'→FF→PF'F→PF'F→PF'F→PF'F'F'→F'→F'→*F'F'→F'→F'→F'→F'→PP→aP→bP→∧P→(E)11.解答:(1)a.文法不含左递归;b.S,A,B各候选式的First集不相交;c.First(A)∩Follow(A)={a,}∩{b}=First(B)∩Follow(B)={b,}∩=∴该文法为LL(1)文法。(2)a.文法不含左递归;b.S,A,B各候选式的First集不相交;c.First(A)∩Follow(A)={a,b,}∩{b}={b}≠∴该文法不是LL(1)文法。12.解答:①最右推导:E=T=F=(E)=(E+T)=(E+F)=(E+i)=(T+i)=(T*F+i)语法树:图4.1句型(T*F+i)的语法树②短语:(T*F+i),T*F+i,T*F,i素短语:T*F,i最左素短语:T*F③由于E=E+T=E+T*F,故E+T*F为该文法的句型短语:T*F、E+T*F直接短语:T*F句柄:T*F13.解答:最左推导:S=(T)=(T,S)=(S,S)=(a,S)=(a,(T))=(a,(T,S))=(a,(S,S))=(a,(a,S))=(a,(a,a))最右推导:S=(T)=(T,S)=(T,(T))=(T,(T,S))=(T,(T,a))=(T,(T,a))=(T,(a,a))=(S,(a,a))=(a,(a,a))文法中S和T的FirstVT和LastVT集为:FirstVT(S)={a,(}FirstVT(T)={,,a,(}lastVT(S)={a,)}lastVT(T)={,,a,)}文法G[S]的算符优先关系表:S→AbcA→a│B→b│S→AbA→a│B│B→b│根据优先关系表,对每个终结符或#建立符号f与g,把f(和g)分成一组。根据G[S]的算符优先关系表,画出如下的有向图。优先函数如下:用算符优先分析法分析句子(a,(a,a))。给定的输入符号串是文法的一个句子。14.解答:(1)该文法的拓广文法G'为0.S'→S1.S→aSAB2.S→BA3.A→aA4.A→B5.B→b其LR(0)项目集规范族和识别活前缀的DFA如下:I0={S'→·S,S→·aSAB,S→·BA,B→·b}I1={S'→S·}I2={B→b·}I3={S→a·SAB,S→·aSAB,S→·BA,B→·b}I4={S→B·A,A→·aA,A→·B,B→·b}I5={S→aS·AB,A→·aA,A→·B,B→·b}I6={S→aSA·B,B→·b}I7={A→a·A,A→·aA,A→·B,B→·b}I8={A→B·}I9={S→BA·}I10={S→aSAB·}I11={A→aA·}显然,上述状态中没有出现冲突。显然,该文法是LR(0)的文法,因此也是SLR(1)的。求各个非终结符的Follow集,以便构造分析表:Follow(S')={#}Follow(S)={a,b,#}Follow(A)={a,b,#}Follow(B)={a,b,#}构造的SLR(1)分析表如下:(2)该文法的拓广文法G'为0.S'→S1.S→Sab2.S→bR3.R→S4.R→a其LR(0)项目集规范族和识别活前缀的DFA如下:I0={S'→·S,S→·Sab,S→·bR}I1={S'→S·,S→S·ab}I2={S→b·R,R→·S,R→·a,S→·Sab,S→·bR}I3={S→Sa·b}I4={S→bR·}I5={R→S·,S→S·ab}I6={R→a·}I7={S→Sab·}显然,I1和I5存在移进-归约冲突。求S'和R的Follow集:Follow(S')={#}Follow(R)=Follow(S)={a,#}在I5中,出现的移进-归约冲突,且Follow(R)∩{a}={a},不能用SLR(1)方法解决。因此,此文法不是SLR(1)文法。15.解答:(1)构造其拓广文法G'的产生式为0.S'→S1.S→A2.A→BA3.A→4.B→aB5.B→b构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={[S'→·S,#],[S→·A,#],[A→·BA,#,[A→·,#],[B→·aB,a/b/#],[B→·b,a/b/#]}I1={[S'→S·,#]}I2={[S→A·,#]}I3={[A→B·A,#],[A→·BA,#],[A→·,#],[B→·aB,a/b/#],[B→·b,a/b/#]}I4={[B→b·,a/b/#]}I5={[B→a·B,a/b/#],[B→·aB,a/b/#],[B→·b,a/b/#]}I6={[A→BA·,#]}I7={[B→aB·,a/b/#]}该文法的LR(1)项目集规范族中没有冲突,所以该文法是LR(1)文法。构造LR(1)分析表如下:以上分析表无多的定义入口,所以该文法为LR(1)文法。(3)对于输入串abab,其分析过程如下:16.解答:(1)对于产生式S→AaAb|BbBa来说First(AaAb)∩First(BbBa)={a}∩{b}=A,B∈VN仅有一条候选式。因此,这个文法是LL(1)的。(2)下面构造这个文法的识别活前缀的DFA。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={S→BbB·a}I8={S→AaAb·}I9={S→BbBa·}由于Follow(A)=Follow(B)={a,b},因此项目集I0中存在归约-归约冲突。在I0状态下,当输入符号是a或是b时,不知用A→还是B→进行归约。故此文法不是SLR(1)的。但是,此文法时LR(1)的。17.解答:该文法的拓广文法G'为0.S'→S1.S→(SR2.S→a3.R→,SR4.R→)构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={S'→·S,S→·(SR,S
本文标题:编译原理第4章习题解答
链接地址:https://www.777doc.com/doc-2141165 .html