编译原理及实现课后答案.doc

《编译原理及实现课后答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.1考虑以下的文法：S→S;T

2、TT→a（1）为这个文法构造LR(0)的项目集规范族。（2）这个文法是不是LR(0)文法？如果是，则构造LR(0)分析表。（3）对输入串“a;a”进行分析。解：（1）拓广文法G[S’]：0：S’→S1：S→S;T2：S→T3：T→a构造LR(0)项目集规范族状态项目集转换函数0S’→·SS→·S;TS→·TT→·aGO[0，S]＝1GO[0，S]＝1GO[0，T]＝2GO[0，a]＝31S’→S·S→S·;TACCEPTGO[1，;]＝42S→T·R23T→a·R34S→S;·TT→·aGO[4，T]＝

3、5GO[4，a]＝35S→S;T·R1（2）该文法不存在“归约－归约”和“归约－移进”冲突，因此是LR(0)文法。LR(0)分析表如下：状态ACTIONGOTO；a#ST0S3121S4ACCEPT2R2R2R23R3R3R34S355R1R1R1（3）对输入串“a;a”进行分析如下：步骤状态栈符号栈输入符号栈ACTIONGOTO00#a;a#S3103#a;a#R32302#T;a#R21401#S;a#S45014#S;a#S360143#S;a#R3570145#S;T#R11801#S#ACCEPT5.2证明下面文法是SLR(1

4、)文法，但不是LR(0)文法。S→AA→Ab

5、bBaB→aAc

6、a

7、aAb解：文法G[S]：0：S→A1：A→Ab2：A→bBa3：B→aAc4：B→a5：B→aAb构造LR(0)项目集规范族：状态项目集转换函数0S→·AA→·AbA→·bBaGO[0，A]＝1GO[0，A]＝1GO[0，b]＝21S→A·A→A·bACCEPTGO[1，b]＝32A→b·BaB→·aAcB→·aB→·aAbGO[2，B]＝4GO[2，a]＝5GO[2，a]＝5GO[2，a]＝53A→Ab·R14A→bB·aGO[4，a]＝65B→a·AcB→a·B→a

8、·AbA→·AbA→·bBaGO[5，A]＝7R4GO[5，A]＝7GO[5，A]＝7GO[5，b]＝26A→bBa·R27B→aA·cB→aA·bA→A·bGO[7，c]＝8GO[7，b]＝9GO[7，b]＝98B→aAc·R39B→aAb·A→Ab·R5R1状态5存在“归约－移进”冲突，状态9存在“归约－归约”冲突，因此该文法不是LR(0)文法。状态5：FOLLOW(B)＝｛a｝，因此，FOLLOW(B)∩｛b｝＝Φ状态9：FOLLOW(B)＝｛a｝，FOLLOW(A)＝｛#，b，c｝，因此FOLLOW(B)∩FOLLOW(A)＝Φ

9、状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下：状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。5.3证明下面文法是LR(1)文法，但不是SLR(1)文法。S→AaAb

10、BbBaA→εB→ε解：拓广文法G[S’]：0：S’→S1：S→AaAb2：S→BbBa3：A→ε4：B→ε构造LR(0)项目集规范族：状态项目集转换函数0S’→

11、·SS→·AaAbS→·BbBaA→·B→·GO[0，S]＝1GO[0，A]＝2GO[0，B]＝3R3R41S’→S·ACCEPT2S→A·aAbGO[2，a]＝43S→B·bBaGO[3，b]＝54S→Aa·AbGO[4，A]＝6A→·R35S→Bb·BaB→·GO[5，B]＝7R46S→AaA·bGO[6，b]＝87S→BbB·aGO[7，a]＝98S→AaAb·R19S→BbBa·R2状态0存在“归约－归约”冲突，且FOLLOW(A)＝｛a,b｝，FOLLOW(B)＝｛a,b｝，即FOLLOW(A)∩FOLLOW(B)＝｛a,b｝

12、≠Φ，所以该文法不是SLR(1)文法。构造LR(1)项目集规范族：状态项目集转换函数0S’→·S，#S→·AaAb，#S→·BbBa，#A→·，aB→·，bGO[0，S]＝1GO[0，A]＝2GO[0，B]＝3R3R41S’→S·，#ACCEPT2S→A·aAb，#GO[2，a]＝43S→B·bBa，#GO[3，b]＝54S→Aa·Ab，#A→·，bGO[4，A]＝6R35S→Bb·Ba，#B→·，aGO[5，B]＝7R46S→AaA·b，#GO[6，b]＝87S→BbB·a，#GO[7，a]＝98S→AaAb·，#R19S→BbBa·

13、，#R2LR(1)分析表：状态ACTIONGOTOab#SAB0R3R41231ACCEPT2S43S54R365R476S87S98R19R2分析表无重定义，说明该文法是LR(1)文法，不是SLR(1)文