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

编译原理作业参考答案 - 17 -第七章 LR分析法第1题 已知文法AaAd|aAb| 判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。文法： AaAd|aAb| 拓广文法为G，增加产生式SA若产生式排序为：0 S A 1 A aAd2 A aAb3 A 由产生式知： First (S ) = ,aFirst (A ) = ,aFollow(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）ActionGotoad b #A012345S2r3r3r3 accS2r3r3r3S4S5r1r1r1 r2r2r21.3题目1对输入串ab#的分析过程状态栈（state stack） 文法符号栈 剩余输入串（input left）动作（action）Goto00 20 2 30 2 350 1#a#aA#aAb#Aab#.b#.b#.#.#.S2r3(A )S5r2(A aAb)acc 3 1分析成功，说明输入串ab是题目1文法的句子第2题若有定义二进制数的文法如下：SL.L|L LLB|BB0|1 (1) 试为该文法构造LR分析表，并说明属哪类LR分析表。(2) 给出输入串101.110的分析过程。解：文法： SL.L|L LLB|BB0|1 拓广文法为G，增加产生式SS若产生式排序为：0 S S 1 S L.L 2 S L 3 L LB 4 L B5 B 06 B 1 由产生式知： First (S ) = 0,1First (S ) = 0,1 First (L ) = 0,1First (B ) = 0,1Follow(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 #SLB012345678S4S5 accS6S4S5r2r4r4r4r4r5r5r5r5r6r6r6r6S4S5r3r3r3r3S4S5r1123.7.83. 7题目2对输入串101.110#的分析过程状态栈（state stack） 文法符号栈剩余输入串（input left）动作（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 BShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S L.L分析成功，说明输入串101.110是题目2文法的句子。3考虑文法：SAS|b ASA|a(1) 列出该文法所有的LR（0）项目。（2） 按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。（3） 此文法是SLR（1）的吗？，若是，构造他的SLR分析表（4） 这个文法是LALR或LR（1）的吗？解：(1) 构造增广文法，SS文法的LR(0)项目有：1. S.S2. SS.3. S.AS4. SA.S5. SAS.6. S.b7. Sb.8. A.SA9. AS.A10. ASA.11. A.a12. Aa.（2）所产生的NFA略。由规则构造所需的DFA:I5:AS.AA.SAAa.S.ASSb.I1:SS.AS.AA.SAA.aS.ASS.b S S A b aI7:ASA.SA.SS.ASS.bA.SAA.a a AI0:S.SS.ASS.bA.SAA.aI2:Aa. aa bI3:Sb. b S bAI6:SAS.AS.AA.SAA.aS.ASS.bI4:SA.SS.ASS.bA.SAA.a abA A S S则LR(0)项目集规范族为：CI0,I1,I2,I3,I4,I5,I6,I7（3）可以看到I1,I6,I7存在着移进归约的冲突。冲突是不能用SLR(1)的方法来解决。比如I6:对于状态SAS. 和S.bFollow(S)=#,a,b与b相交不为空。所以以上文法不是SLR(1)文法。（4）为验证该文法是否为LALR或LR(1)的，构造LR(1)项目集。对于I5,产生了移进归约矛盾，所以这个文法不是LR(1)文法。于是也不是LALR文法。第6题文法：SUTa|Tb TS|Sc|dUUS|e 拓广文法为G，增加产生式SS若产生式排序为：0 S S1 S UTa 2 S Tb 3 T S 4 T Sc5 T d 6 U US 7 U e 由产生式知： First (S ) = d,eFirst (S ) = d,eFirst (U ) = e First (T ) = d,eFollow(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）ActionGotoa b c d e#SUT012345678910 S5S4r3r3S6AccS5S4S9.r7r7r5r5. r4r4.S10S9.r3r3.S6r6r6. r2r2.r2r2r2r2r1r1.r1r1r1r1123.827 第8题文法： SA#ABaBb|DbDa BD 证明该文法是LR(1)但不是SLR(1)。解：若产生式排序为：0 SA#1 A BaBb 2 A DbDa 3 B 4 D 由产生式知： First (S ) = a,b First (A ) = a,bFirst (B ) = First (D ) = Follow(S ) = #Follow(A ) = # Follow(B ) = a,bFollow(D ) = a,bG的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.67 10判断下列各题所示文法是否为LR类文法，若是请说明是LR（0）、SLR（1）、LALR（1）或LR（1）的哪一种，并构造相应分析表（）SAB AaBa| BbAb|（3）SaAd|eBd|aBr|eAr Aa Ba(5) AaB| BAb|a (6) S(SR|a R.SR|)（1）解：对于该文法构造LR(0)项目规范族：I0:S.SI1:SS.I3:Aa.BaI5:Bb.AbI6:AaB.a S.ABI2:SA.BB.bAbA.aBaI7:AaBa.A.aBaB.bAbB.A.I8:BbA.bA-.B.I4:SAB.I9:BbAb.可见存在着移进归约冲突，这个文法不是LR(0)文法。考虑用SLR(1)来解决问题：构造SLR(1)分析表，发现该文法是SLR(1)文法。状态ACTIONGOTOab#SAB0s3r3r3121acc2r5S5r543r5S5r564r15S3r3r386S77r2r28S99r4r4（3）解：先构造该文法的LR(0)项目集规范族：I0:S.SI1:SS.I3:Se.BdI5:SaB.rI9:SaAd.S.AdI2:Sa.AdB.aI6:Aa.I10:SaBr.S.eBdSa.BrSe.ArBa.I11:SeBd.S.aBrA.aA.aI7:SeB.dI12:SeAr.S.eArB.aI4:SaA.dI8:SeA.r该文法存在着归约-归约冲突，所以不是LR（0）文法。对于状态I6:Aa.Ba.Follow(A)=drFollow(B)=dr两个集合相交不为空，所以该文法也不是SLR(1)文法。构造该文法的LR(1)文法可得该文法是LR(1)的。I0:SS,#I2:Sa.Ad,#I4:SaA.d,#I10: SaAd.,#S.aAd,#Sa.Br,#I5:SaB.r,#I11: SaBr.,#S.eBd,#A.a,dI6:Aa.,dI12: SeBd.,#S.aBr,#B.a,rBb.,rI13: SeAr.,#S.eAr,#I3:Se.Bd,#I7:SeB.d,#I1:SS.,#Se.Ar,#I8:SeA.r,#B.a,dI9:Ba.,dA.a,rAa.,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:B-A.b,#I9:B-a.,bA-.aB,#I5:B-a.,#A-a.B,bA-.,#A-a.B,bB-.Ab,bI1:S-A.,#B-.Ab,bB-.a,bI2:A-a.B,#B-.a,bA-.aB,bB-.Ab,#,B-.aB,bA-.,bB-.a,#A-.aB,bI10:B-AB.,bA-.aB,bI6:B-Ab.,#A-.,bI7:A-aB.,bI3:A-aB.,#I8:B-A.b,b其中存在冲突，所以文法也不是LR(1)文法。（6）解：将文法拓广后得：(0) S S(1) S(SR(2) S a (3) R.SR(4) R)构造LR(0)的项目集规范族：一个文法是LR(0)文法一定也是SLR(1)文法，也是LR(1)文法。但反之则不一定成立。 I0: SS S(SRSaI1: SSI2: S(SRS(SRSaI4: S aI6: R.SRS(SRSaI7: R)I3: S(SRR.SRR)SRS.(S(aI5: S (SR.)I9: R.SR(I8: R.SRR.SRR)aa.)I0I9无冲突项目，所以此文法是LR（0）文法。构造其LR（1）的DFA（构造过程中，在建立好初态集后，立即产生所有新状态的核集合，然后再逐步扩充）：状态核集合项目集 (核集合 + 闭包增加项目)I0SS,#SS，# S(SR，#Sa，#I1SS,#SS,#I2S(SR，#S(SR, #S(SR, ./)Sa, ./)I3Sa，#Sa，#I4S(SR, #S(SR, #R.SR, #R), #I5S(SR, ./)S(SR, ./)S(SR, ./) - I5Sa, ./) - I6I6Sa, ./)Sa, ./)I7S(SR, #S(SR, #I8R.SR, #R.SR, #S(SR, ./) - I5Sa, ./) - I6I9R), #R), #I10S(SR, ./)S(SR, ./)R.SR, ./)R), ./)I11R.SR, #R.SR, #R.SR, # -I8R), # -I9I12S(SR, ./)S(SR, ./)I13R.SR, ./)R.SR, ./)S(SR, ./) - I5Sa, ./) - I6I14R), ./)R), ./)I15R.SR, #R.SR, #I16R.SR, ./)R.SR, ./)R.SR, ./) -I13R), ./) -I14I17R.SR, ./)R.SR, ./)无移进-规约冲突和规约-规约冲突，此文法是LR(1)文法。对同心集合并，得LALR(1)项目集规范族：状态核集合项目集 (核集合 + 闭包增加项目)I0SS,#SS，# S(SR，#Sa，#I1SS,#SS,#I2,5S(SR，#S(SR, ./)/#S(SR, ./)Sa, ./)I3,6Sa，#Sa，./)/#I4,10S(SR, #S(SR, ./)/#R.SR, #R), #I7,12S(SR, #S(SR, ./)/#I8,13R.SR, #R.SR, ./)/#S(SR, ./) - I5Sa, ./) - I6I9,14R), #R), ./)/#I11,16R.SR, #R.SR,./)/#R.SR, # -I8R), # -I9I15,17R.SR, #R.SR, ./)/#同心集合并后无冲突，其项目集的个数与LR（0）相同，此文法是LALR（1）文法。11. 设文法GS为：SAS| AaA|b(1) 证明GS是LR(1)文法(2) 构造出它的LR(1)分析表(3) 给出输入符号串abab#的分析过程一个文法不是SLR(1)时，不能证明它是LR(1)的解：将文法改写为拓广文法： (0) SS (1) SAS (2) S (3) AaA (4) Ab 构造其LR(1)项目集规范族：状态核集合项目集 (核集合 + 闭包增加项目)I0SS,#SS，# SAS，#S，#AaA, a/b/#Ab, a/b/#I1SS,#SS,#I2SAS，#SAS，#SAS，# -I2S，#AaA, a/b/# -I3Ab, a/b/# -I4I3AaA, a/b/#AaA, a/b/#AaA, a/b/# -I3Ab, a/b/# -I4I4Ab, a/b/#Ab, a/b/#I5SAS，#SAS，#I6AaA, a/b/#AaA, a/b/#LR(1)分析表：状态ACTIONGOTOab#SA0S3S4r2121acc2S3S4r2523S3S464r4r4r45r16r3r3r3对abab#的分析过程：步骤状态栈符号栈输入串ACTIONGOTO10#abab#S3203#abab#S43034#abab#r464036#aAab#r35502#Aab#S36023#Aab#S470234#Aab#r480236#AaA#r329022#AA#r25100225#AAS#r1511025#AS#r111201#S#acc第15题：已知文法为： Sa|(T) TT,S|S (1) 构造它的LR(0)、LALR（1），LR（1）分析表（2） 给出对输入符号长(a#和(a,a#的分析过程（3）说明（1）中三种分析表发现错误的时刻和输入串的出错位置有何区别。解：构造该文法的LR(0)项目集规范集：I0:S.SI2:Sa.I5:S(T.)I9:TT,S.S.aI3:S.TT.,SS.I4:S(.T)I6:TS.S.(T)T.T,SI7:S(T).I1:SS.T.SI8:TT,.SS.aS.aS.S.S.(T)S(T)构造LR(0)分析表：状态ACTIONGOTOa(),#ST0S2S3S411acc2r2r2r2r2r2r23r3r3r3r3r3r34S2S3S4655S8S76r6r6r6r6r6r67r4r4r4r4r4r48S2S3S499r5r5r5r5r5r5构造LR(1)规范集族：I0:S.S，#I2:Sa.，#I5:S(T.)，#I9:TT,S.,)S.a，#I3:S.，#TT.,S,)I10:S-a.,)S.，#I4:S(.T)，#I6:TS.,)I11:S-.,)S.(T)，#T.T,S，）I7:S(T).,#I12:S-(.T),)I1:SS.，#T.S，）I8:TT,.S,)T-.T,S,)S.a，）S.a,)T-.S,)S.，）S.,)S-.a,)S.(T)，）S(T),)S-.,I13:S-(T.),)I14:S-(T).,)S-.(T),)T-T.,S,)构造LR(1)分析表：状态ACTIONGOTOa(,)#ST0S2S3S411acc2r23r34S10S11S12655S8S76r67r48S10S11S1299r510r211r312S10S11S121313S8S1414R4参看LR(1)的规范集合，可以看到I2和I10、I3和I11、I4和I12、I5和I13、I7和I14是同心