第六七章-作业与习题参考答案

第七章LR分析法第1题已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S'→A1A→aAd2A→aAb3A→ε由产生式知：First(S')={ε,a}First(A)={ε,a}Follow(S')={#}Follow(A)={d,b,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I0中：A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：题目1的SLR(1)分析表状态（State）ActionGotoadb#A012345S2r3r3r3accS2r3r3r3S4S5r1r1r1r2r2r21.3题目1对输入串ab#的分析过程状态栈（statestack）文法符号栈剩余输入串（inputleft）动作（action）Goto002023023501##a#aA#aAb#Aab#....b#....b#....#....#....S2r3(A→ε)S5r2(A→aAb)acc31分析成功，说明输入串ab是题目1文法的句子第2题若有定义二进制数的文法如下：S→L.L|LL→LB|BB→0|1(1)试为该文法构造LR分析表，并说明属哪类LR分析表。(2)给出输入串101.110的分析过程。解：文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→S若产生式排序为：0S'→S1S→L.L2S→L3L→LB4L→B5B→06B→1由产生式知：First(S')={0,1}First(S)={0,1}First(L)={0,1}First(B)={0,1}Follow(S')={#}Follow(S)={#}Follow(L)={.,0,1,#}Follow(B)={.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I2中：B→.0和B→.1为移进项目，S→L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8中：Follow(s)∩{0，1}={#}∩{0，1}=所以在I2、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：题目2的SLR(1)分析表状态（State）ActionGoto·01#SLB012S4S5accS6S4S5r2123.7345678r4r4r4r4r5r5r5r5r6r6r6r6S4S5r3r3r3r3S4S5r1...83.7题目2对输入串101.110#的分析过程状态栈（statestack）文法符号栈剩余输入串（inputleft）动作（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#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→1Reduceby:S→BShiftReduceby:B→1Reduceby:S→LBShiftReduceby:B→0Reduceby:S→L.L分析成功，说明输入串101.110是题目2文法的句子。3．考虑文法：SAS|bASA|a(1)列出该文法所有的LR（0）项目。（2）按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。（3）此文法是SLR（1）的吗？，若是，构造他的SLR分析表（4）这个文法是LALR或LR（1）的吗？解：(1)构造增广文法，S’S文法的LR(0)项目有：1.S’.S2.S’S.3.S.AS4.SA.S5.SAS.6.S.b7.Sb.8.A.SA9.AS.A10.ASA.11.A.a12.Aa.（2）所产生的NFA略。由规则构造所需的DFA:SSAbaaAaabbSbAabAASS则LR(0)项目集规范族为：C＝｛I0,I1,I2,I3,I4,I5,I6,I7｝（3）可以看到I1,I6,I7存在着移进－归约的冲突。冲突是不能用SLR(1)的方法来解决。比如I6:对于状态SAS.和S.bFollow(S)={#,a,b}与{b}相交不为空。所以以上文法不是SLR(1)文法。（4）为验证该文法是否为LALR或LR(1)的，构造LR(1)项目集。对于I5,产生了移进－归约矛盾，所以这个文法不是LR(1)文法。于是也不是LALR文法。I0:S’.SS.ASS.bA.SAA.aI1:S’S.AS.AA.SAA.aS.ASS.bI2:Aa.I3:Sb.I4:SA.SS.ASS.bA.SAA.aI5:AS.AA.SAAa.S.ASSb.I6:SAS.AS.AA.SAA.aS.ASS.bI7:ASA.SA.SS.ASS.bA.SAA.a第6题文法：S→UTa|TbT→S|Sc|dU→US|e拓广文法为G'，增加产生式S'→S若产生式排序为：0S'→S1S→UTa2S→Tb3T→S4T→Sc5T→d6U→US7U→e由产生式知：First(S')={d,e}First(S)={d,e}First(U)={e}First(T)={d,e}Follow(S')={#}Follow(S)={a,b,c,d,e,#}Follow(U)={d,e}Follow(T)={a,b}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I1中：S'→S.为接受项目，T→S.为归约项目，T→S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR(0)文法。在I1中：Follow(S')∩Follow(T)={#}∩{a，b}=Follow(T)∩{c}={a，b}∩{c}=在I8中：Follow(U)∩Follow(T)∩{c}={d,e}∩{a，b}∩{c}=所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：题目3的SLR(1)分析表状态（State）ActionGotoabcde#SUT012345678910S5S4r3r3S6AccS5S4S9..................r7r7r5r5........................r4r4.........................S10S9.........................r3r3.S6r6r6......r2r2.r2r2r2r2r1r1.r1r1r1r1123.827第8题文法：SA#A→BaBb|DbDaB→εD→ε证明该文法是LR(1)但不是SLR(1)。解：若产生式排序为：0S'→A#1A→BaBb2A→DbDa3B→ε4D→ε由产生式知：First(S')={a,b}First(A)={a,b}First(B)={ε}First(D)={ε}Follow(S')={#}Follow(A)={#}Follow(B)={a,b}Follow(D)={a,b}G′的LR(1)项目集族及识别活前缀的DFA如下图所示：在I0中：B→.,a和T→.，b为归约项目，但它们的搜索符不同，若当前输入符为a时用产生式B→ε归约，为b时用产生式D→ε归约，所以该文法是LR(1)文法。若不看搜索符，在I0中项目B→.和T→.为归约-归约冲突，而Follow(B)∩Follow(D)={a,b}∩{a,b}≠，冲突不能用Follow集解决，所以该文法不是SLR(1)文法。构造的LR(1)分析表如下：题目4的LR(1)分析表StateActionGotoa.b.#ABD0123456789r3r4......AccS4............S5r3r4............S8S9............r1r2123...6710．判断下列各题所示文法是否为LR类文法，若是请说明是LR（0）、SLR（1）、LALR（1）或LR（1）的哪一种，并构造相应分析表（１）SABAaBa|εBbAb|ε（3）SaAd|eBd|aBr|eArAaBa(5)AaB|εBAb|a(6)S(SR|aR.SR|)（1）解：对于该文法构造LR(0)项目规范族：I0:S’.SI1:S’S.I3:Aa.BaI5:Bb.AbI6:AaB.aS.ABI2:SA.BB.bAbA.aBaI7:AaBa.A.aBaB.bAbB.A.I8:BbA.bA-.B.I4:SAB.I9:BbAb.可见存在着移进－归约冲突，这个文法不是LR(0)文法。考虑用SLR(1)来解决问题：构造SLR(1)分析表，发现该文法是SLR(1)文法。状态ACTIONGOTOab#SAB0s3r3r3121acc2r5S5r543r5S5r564r15S3r3r386S77r2r28S99r4r4（3）解：先构造该文法的LR(0)项目集规范族：I0:S’.SI1:S’S.I3:Se.BdI5:SaB.rI9:SaAd.S.AdI2:Sa.AdB.aI6:Aa.I10:SaBr.S.eBdSa.BrSe.ArBa.I11:SeBd.S.aBrA.aA.aI7:SeB.dI12:SeAr.S.eArB.aI4:SaA.dI8:SeA.r该文法存在着归约-归约冲突，所以不是LR（0）文法。对于状态I6:Aa.Ba.Follow(A)={dr}Follow(B)={dr}两个集合相交不为空，所以该文法也不是SLR(1)文法。构造该文法的LR(1)文法可得该文法是LR(1)的。I0:S’S,#I2:Sa.Ad,#I4:SaA.d,#I10:SaAd.,#S.aAd,#Sa.Br,#I5:SaB.r,#I11:SaBr.,#S.eBd,#A.a,dI6:Aa.,dI12:SeBd.,#S.aBr,#B.a,rBb.,rI13:SeAr.,#S.eAr,#I3:Se.Bd,#I7:SeB.d,#I1:S’S.,#Se.Ar,#I8:SeA.r,#B.a,dI9:Ba.,dA.a,rAa.,r构造LR(1)分析表（略）。（5）解：构造LR(0)的分析表：I0:S.AI3:S-aB.I6:B-AB.A.aBI4:B-A.bA.I5:B-a.I1:S-A.A-a.BI2:S-a.BB-.AbB-.AbB-.aB-.aA-.aBA-.aBA-.A-.可以看到存在着移进－归约的冲突，不是LR(0)文法。在I0中Follow(A)与{ｂ}相交不为空。所以也不为SLR(1)文法。构造该文法的LR(1)项目集规范族：I0:S-.A,#I4: