资源描述：
《编译原理 第七章 习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章习题答案1．拓广该文法：(0)S→A(1)A→aAd(2)A→aAb(3)A→ε构造LR(0)项目集规范族如下：由图可知，在项目集I0、I2中存在移进-归约冲突，该文法不是LR(0)文法。在I0中，移进符号为a，而归约符号为Follow(A)={b,d,#}，交集为空，可以解决冲突；在I2中，移进符号为a，而归约符号为Follow(A)={b,d,#}，交集为空，可以解决冲突。因此，该文法是SLR(1)文法。SLR(1)分析表状态ActionGotoabd#A0S2r3r3r311acc2S2r3r3r333S4S54r1r1r15r2r2r2输入串ab#的分析过程步骤
2、状态栈符号栈输入串ActionGoto(1)0#ab#S2(2)02#ab#r33(3)023#aAb#S4(4)0234#aAb#r1(5)01#A#acc7．拓广该文法：(0)S’→S(1)S→A(2)A→Ab(3)A→bBa(4)B→aAc(5)B→a(6)B→aAb构造LR(0)项目集规范族如下：由图可知，在项目集I2、I6中存在移进-归约冲突，该文法不是LR(0)文法。Follow(S’)={#}Follow(S)=Follow(S’)={#}Follow(A)=Follow(S)∪{b,c}={b,c,#}Follow(B)={a}在I2中，移进符号为b，归约符号
3、为Follow(S)={#}，交集为空，可以解决冲突；在I6中，移进符号为b，归约符号为Follow(B)={a}，交集为空，可以解决冲突。因此，该文法为SLR(1)文法。8．拓广该文法：(0)S’→S(1)S→A$(2)A→BaBb(3)A→DbDa(4)B→ε(5)D→ε构造LR(0)项目集规范族如下：由图可知，在项目集I0中存在归约-归约冲突，该文法不是LR(0)文法。Follow(S’)={#}Follow(S)=Follow(S’)={#}Follow(A)={$}Follow(B)={a,b}Follow(D)={a,b}在I0中，归约项目B→·的归约符号集为Fo
4、llow(B)={a,b}，归约项目D→·的归约符号集为{a,b}，交集不为空，因此，该文法不是SLR(1)文法。构造LR(1)项目集规范族如下：由图可知，不存在任何冲突，该文法是LR(1)文法。18．文法G[E]：E→E+T
5、TT→T*F
6、FF→(E)
7、i（1）构造算符优先关系表和LR分析表，并对其进行适当的改写后构造预测分析表。a、计算每个非终结符的FIRSTVT集合：FIRSTVT(E)=FIRSTVT(E)∪{+}∪FIRSTVT(T)={+,*,(,i}FIRSTVT(T)=FIRSTVT(T)∪{*}∪FIRSTVT(F)={*,(,i}FIRSTVT(F)={(
8、,i}={(,i}计算每个非终结符的LASTVT集合：LASTVT(E)={+}∪LASTVT(T)={+,*,),i}LASTVT(T)={*}∪LASTVT(F)={*,),i}LASTVT(F)={},i}={},i}①关系由#E#可知：##由(E)可知：()②关系E#LASTVT(E)#→{+,*,),i}#E+LASTVT(E)+→{+,*,),i}+T*LASTVT(T)*→{*,),i}*E)LASTVT(E))→{+,*,),i})③关系#E#FISRTVT(E)→#{+,*,(,i}+T+FISRTVT(T)→+{*,(,i}*F*FISRTVT(F)→*{
9、(,i}(E(FISRTVT(E)→({+,*,(,i}构造优先关系表如下：+*()i#+*()i#b、拓广该文法：(0)E’→E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i构造LR(0)项目集规范族如下：由图可知，在项目集I2、I9中存在移进-归约冲突，该文法不是LR(0)文法。Follow(E’)={#}Follow(E)=Follow(E’)∪{+}∪{)}={#,+,)}Follow(T)=Follow(E)∪{*}={#,+,),*}Follow(F)=Follow(T)={#,+,),*}在I2中，移进符号为*，归约符号集为
10、Follow(E)={#,+,)}，交集为空，可以解决冲突；在I9中，移进符号为*，归约符号集为Follow(E)={#,+,)}，交集为空，可以解决冲突；因此，该文法为SLR(1)文法。SLR(1)分析表状态+*()i#ETF0S51231S6acc2r2S7r2r23r4r4r4r44S4S58235r6r6r6r66S4S5937S4S5108S6S119r1S7r1r110r3r3r3r311r5r5r5r5c、消除左递归后文法为：E→TE’E’→+TE’
11、εT→FT’T’→*FT’
12、εF→(E
