编译原理 第7章习题解答

《编译原理 第7章习题解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章习题解答7.1给定文法：S®(A)A®ABBA®BB®bB®c①构造它的基本LR(0)项目集；②构造它的LR(0)项目集规范族；③构造识别该文法活前缀的DFA；④该文法是SLR文法吗？若是，构造它的SLR分析表。7.2给定文法：E®EE+E®EE*E®a①构造它的LR(0)项目集规范族；②它是SLR(1)文法吗？若是，构造它的SLR(1)分析表；③它是LR(1)文法吗？若是，构造它的LR(1)分析表；④它是LALR(1)文法吗？若是，构造它的LALR分析表。7.3给出一个非LR(0)文法。7.4给出一个SLR(1)文法，但它不是LR

2、(0)文法，构造它的SLR分析表。7.5给出一个LR(1)文法，但它不是LALR(1)文法，构造它的规范LR(1)分析表。7.6给定二义性文法：①E®E+E②E®E*E③E®(E)④E®id用所述的无二义性规则和(或)另加一些无二义性规则，例如，给算符*、+施加某种结合规则。①构造它的LR(0)项目集规范族及识别活前缀的DFA；②构造它的LR分析表。习题参考答案7.1解：文法的基本LR(0)项目集为S→.(A)S→(.A)S→(A.)S→(A).A→.ABBA→A.BBA→AB.BA→ABB.A→.BA→B.B→.bB→b.B→.cB→c

3、.构造该文法的识别活前缀的DFSA如下图所示：文法的识别活前缀的DFSA该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8}因为在构造出来的识别活前缀的DFA中，每一个状态对应的项目集都不含有移进-归约、归约-归约冲突，所以该文法是LR(0)文法，当然也是SLR文法。因为FOLLOW(S)={#}FOLLOW(A)=FIRST{)}∪FIRST(BB)={)，b，c}FOLLOW(B)=FIRST(B)∪FOLLOW(A)={b，c，)}其对应的SLR(1)分析表如下表所示。文法G[S]的SLR(1)分

4、析表状态ACTIONGOTObc()#AB0S11S4S5232S4S5S763r3r3r34r4r4r45r5r5r56S4S587acc8r2r2r27.2解：首先构造增广文法如下：S→E0E→EE+1E→EE*2E→a3(1)构造它的LR(0)项目集规范族如下图所示。该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5}(2)因为在识别活前缀的DFSA的每一个状态中，都不存在移进-归约冲突和归约-归约冲突，所以文法是LR(0)文法，当然也是SLR(1)文法。因为FOLLOW(E)={#，+，*，a}所以该文法对应的S

5、LR(1)分析表如下表所示。文法的LR(0)项目集规范族文法的SLR(1)分析表状态ACTIONGOTOa+*#E0S211S2acc32r3r3r3r33S2S4S574r1r1r1r15r2r2r2r2(3)该文法是SLR(1)文法，当然也是LR(1)文法。它的以LR(1)项目集为状态的识别活前缀的DFSA如下图所示。相应的LR(1)分析表如表所示。文法的以LR(1)项目集为状态的识别活前缀的DFSA文法的LR(1)分析表状态ACTIONGOTOa+*#E0S211S4acc32r3r33S4S5S674r3r3r35r1r16r2r

6、27S4S8S978r1r1r19r2r2r2(4)由于文法的以LR(1)项目集为状态的识别活前缀的DFSA中，状态I2和I4、I3和I7、I5和I8、I6和I9是同心项目集，将它们合并后不会产生冲突。因而可构造文法的LALR(1)分析表如下表所示。文法的LALR(1)分析表状态ACTIONGOTOa+*#E0S2411S24acc3724r3r3r3r337S24S58S693758r1r1r1r169r2r2r2r27.3解：构造二义性文法G：S®aAbScSS®aAbSG不是LR（0）文法。7.4解：构造下面文法G:S®bASB

7、b

8、AS®dSa

9、bB®cAa

10、c然后构造其SLR分析表。（略)7.5解：构造下面的文法G:S®aAa

11、aBb

12、bAb

13、bBaA®xB®x然后构造其LR(1)分析表。(略)7.6解：首先构造增广文法如下：S→E0E→E+E1E→E*E2E→(E)3E→id4(1)构造它的识别活前缀的DFSA如下图所示。该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8，I9}(2)构造它的LR分析表如下表所示。文法有冲突的LR分析表状态ACTIONGOTOid+*()#E0S3S211S4S5acc2S3S263r4r4r

14、4r4r4r44S3S2r475S3S286S4S5S97r1r1/S4r1/S5r1r1r18r2r2/S4r2/S5r2r2r29r3r3r3r3r3r3由于识别文法活前缀的DFSA中，状