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

第1题已知文法AaAd|aAb| 判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：1、拓广文法为G，增加产生式SA，若产生式排序为：0 S A 1 A aAd2 A aAb3 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 )=d,b,#在I0、I2中：Follow(A) a= d，b，# a=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。4、构造的SLR(1)分析表如下： SLR(1)分析表 状态（State）ActionGotoad b #A012345S2r3r3r3 AccS2r3r3r3S4S5r1r1r1 r2r2r21.3对输入串ab#的分析过程状态栈（state stack） 文法符号栈 剩余输入串（input left）动作（action）00 20 2 30 2 30 1#a#aA#aAb#Aab#.b#.b#.#.#.ShiftReduce by :A ShiftReduce by :A aAb分析成功，说明输入串ab是文法的句子。2、若有定义二进制数的文法如下：SL.L|L LLB|BB0|1 (1) 试为该文法构造LR分析表，并说明属哪类LR分析表。(2) 给出输入串101.110的分析过程。解：1、拓广文法为G，增加产生式SS，若产生式排序为：0 S S 1 S L.L 2 S L 3 L LB 4 L B 5 B 0 6 B 1 2、G的LR(0)项目集族及识别活前缀的DFA状态先项目集后继符号后继状态S0S SSS1S L.LS LL LBLS2L BBS3B 00S4B 11S5S1S S #接受S2S L.L.S6S L#规约L LBBS7B 00S4B 11S5S3L B#规约S4B 0#规约S5B 1#规约S6S L. LL LBLS8L BBS3B 00S4B 11S5S7L LB#规约S8S L. L#规约L LBBS7B 00S4B 11S53、判定文法在S2、S8中:：B .0和 B .1为移进项目，S L.（S L. L）为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。文法中：Follow(S ) = # Follow(S ) = # Follow(L ) = .,0,1,# Follow(B ) = .,0,1,#在S2、S8中：Follow(s)01= #01= 所以在I2 、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：4、构造SLR(1)分析表 状态（State）ActionGoto 01 #SLB012345678S4S5 AccS6S4S5r2r4r4r4r4r5r5r5r5r6r6r6r6S4S5r3r3r3r3S4S5r1123.7.83. 75、对输入串101.110#的分析过程状态栈 文法符号栈剩余输入串动作（action）00 50 30 20 2 40 2 70 2 0 2 50 2 70 2 0 2 60 2 6 5 0 2 6 3 0 2 6 8 0 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40 2 6 8 70 1#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#S101.110#.01.110#.01.110#.01.110#.1.110#.1.110#.1.110#.110#.110#.110#.110#.10#.10#.10#.0#.0#.0#.#.#.#.ShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S LBShiftReduce by :B 1Reduce by :S LBShiftShiftReduce by :B 1Reduce by :S