编译原理第7章习题解答.doc

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

1、第1题已知文法　　A→aAd

2、aAb

3、ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：1、拓广文法为G′，增加产生式S′→A，若产生式排序为：　0　S'→A　　1　A→aAd　　2　A→aAb　　3　A→ε　2、构造G′的LR(0)项目集族及识别活前缀的DFA如下图所示：3、判定文法在I0、I2中：A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。Follow(S')={#}　　Follow(A)=Follow(S')ÈFirst(d)ÈFirst(b)=

4、{d,b,#}　在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。4、构造的SLR(1)分析表如下：SLR(1)分析表状态（State）ActionGoto a　　　d　　b　　#　A012345S2　　r3　　r3　　r3　　　　　　　　　AccS2　　r3　　r3　　r3S4　　S5　　　r1　　r1　　r1　　r2　　r2　　r21.3对输入串ab#的分析过程状态栈（statestack）文法符号栈剩余输入串（inputleft）动作（actio

5、n）002023023##a#aA#aAbab#....b#....b#....#....ShiftReduceby:A→εShiftReduceby:A→aAb01#A#....分析成功，说明输入串ab是文法的句子。2、若有定义二进制数的文法如下：　　S→L.L

6、L　　L→LB

7、B　　B→0

8、1　　(1)试为该文法构造LR分析表，并说明属哪类LR分析表。　　(2)给出输入串101.110的分析过程。解：1、拓广文法为G′，增加产生式S′→S，若产生式排序为：0　S'→S　　1　S→L.L　　2　S→L　　3　L→LB　　4　L→B　　5　B→0　　6　

9、B→12、G′的LR(0)项目集族及识别活前缀的DFA状态先项目集后继符号后继状态S0S'→×SSS1S→×L.LS→×LL→×LBLS2L→×BBS3B→×00S4B→×11S5S1S'→S×#接受S2S→L×.L.S6S→L×#规约L→L×BBS7B→×00S4B→×11S5S3L→B×#规约S4B→0×#规约S5B→1×#规约S6S→L.×LL→×LBLS8L→×BBS3B→×00S4B→×11S5S7L→LB×#规约S8S→L.L×#规约L→L×BBS7B→×00S4B→×11S53、判定文法在S2、S8中:：B→.0和B→.1为移进项目，S→L

10、.（S→L.L×）为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。文法中：Follow(S')={#}Follow(S)={#}Follow(L)={.,0,1,#}Follow(B)={.,0,1,#}在S2、S8中：Follow(s)∩{0}∩{1}={#}∩{0}∩{1}=所以在I2、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：4、构造SLR(1)分析表状态（State）ActionGoto ·　　0　　　1　　#S　L　B012345678S4　　S5　　　　　　　　　A

11、ccS6　　S4　　S5　　r2r4　　r4　　r4　　r4r5　　r5　　r5　　r5r6　　r6　　r6　　r6S4　　S5r3　　r3　　r3　　r3　　　S4　　S5　　r11　2　3.　　　7...8　3.　　　75、对输入串101.110#的分析过程状态栈文法符号栈剩余输入串动作（action）0050302024027020250270202602650263026802685026870268026840268701##1#B#L#L0#LB#L#L1#LB#L#L.#L.1#L.B#L.L#L.L1#L.LB#L.L#L.L0#L.LB

12、#S101.110#....01.110#....01.110#....01.110#....1.110#....1.110#....1.110#.....110#.....110#.....110#....110#....10#....10#....10#....0#....0#....0#....#....#....#....ShiftReduceby:B→1Reduceby:S→LBShiftReduceby:B→0Reduceby:S→LBShiftReduceby:B→1Reduceby:S→LBShiftShiftReduceby:B→1Re

13、duceby:S→BShiftReduceby:B→1Reduceby:S→LB