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

1、.编译原理作业参考答案 - 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 .为归约项目，存在移进-归约

2、冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A) a= d，b，# a=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下： 题目1的SLR(1)分析表 状态（State）ActionGoto ad b #A012345S2r3r3r3 accS2r3r3r3S4S5r1r1r1 r2r2r21.3题目1对输入串ab#的分析过程状态栈（state stack） 文法符号栈 剩余输入串（input left）动作（action）Goto00 20 2 30 2 350 1#a#aA#aAb#Aab

3、#.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,1Fi

4、rst (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 

5、;· 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.

6、#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 1Re

7、duce by :S LBShiftReduce by :B 0Reduce by :S L.L分析成功，说明输入串101.110是题目2文法的句子。3考虑文法：SàAS|b Aà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&

8、#224;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:I5:AàS.AAà.SAAàa.Sà.ASSàb.I1:SàS.AàS.AAà.SAAà.aSà.ASSà.b S S A b aI7:AàSA.Sà

9、;A.SSà.ASSà.bAà.SAAà.a a AI0:Sà.SSà.ASSà.bAà.SAAà.aI2:Aàa. aa bI3:Sàb. b S bAI6:SàAS.AàS.AAà.SAAà.aSà.ASSà.bI4:SàA.SSà.ASSà.bAà.SAAà.a abA A S S则LR(0)项目集规范族为：CI0,I1,I2,I3,I4,I5,I6,I7（3）可以看到I

10、1,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文法。第6题文法：SUTa|Tb TS|Sc|dUUS|e 拓广文法为G'，增加产生式S'S若产生式排序为：0 S' S1 S UTa 2 S Tb 3 T S 4 T Sc5 T d 6 U US 7 U e

11、由产生式知： 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=Follo

12、w(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）ActionGoto a b c d e#SUT012345678910 S5S4r3r3S6AccS5S4S9.r7r7r5r5. r4r4.S10S9.r3r3.S6r6r6. r2r2.r2r2r2r2r1r1.r1r1r1r1123.827 第8题文法： Sà

13、A#ABaBb|DbDa BD 证明该文法是LR(1)但不是SLR(1)。解：若产生式排序为：0 S'A#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

14、时用产生式D 归约，所以该文法是LR(1)文法。若不看搜索符，在I0中项目B .和T .为归约-归约冲突，而Follow(B ) Follow(D ) = a,b a,b，冲突不能用Follow集解决，所以该文法不是SLR(1)文法。构造的LR(1)分析表如下：题目4的LR(1)分析表 StateActionGoto a.b.#ABD0123456789r3r4. AccS4.S5r3r4.S8S9.r1r2123.67 10判断下列各题所示文法是否为LR类文法，若是请说明是LR（0）、SLR（1）、LALR（1）或LR（1）的哪一种，并构造相应分析表（）SàAB A

15、24;aBa| BàbAb|（3）SàaAd|eBd|aBr|eAr Aàa Bàa(5) AàaB| BàAb|a (6) Sà(SR|a Rà.SR|)（1）解：对于该文法构造LR(0)项目规范族：I0:Sà.SI1:SàS.I3:Aàa.BaI5:Bàb.AbI6:AàaB.a Sà.ABI2:SàA.BBà.bAbAà.aBaI7:AàaBa.Aà.aBaBà.bAbBà.A&#

16、224;.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à

17、.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)=drFollow(B)=dr两个集合相交不为空

18、，所以该文法也不是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

19、.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->

20、.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->.,

21、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: SàS Sà(SRS

22、àaI1: SàSI2: Sà(SRSà(SRSàaI4: Sà aI6: Rà.SRSà(SRSàaI7: Rà)I3: Sà(SRRà.SRRà)SRS.(S(aI5: Sà (SR.)I9: Rà.SR(I8: Rà.SRRà.SRRà)aa.)I0I9无冲突项目，所以此文法是LR（0）文法。构造其LR（1）的DFA（构造过程中，在建立好初态集后，立即产生所有新状态的核集合，然后再逐步扩充）：状态核集合项目集

23、(核集合 + 闭包增加项目)I0SS,#SàS，# Sà(SR，#Sàa，#I1SàS,#SàS,#I2Sà(SR，#Sà(SR, #Sà(SR, ./)Sàa, ./)I3Sàa，#Sàa，#I4Sà(SR, #Sà(SR, #Rà.SR, #Rà), #I5Sà(SR, ./)Sà(SR, ./)Sà(SR, ./) -à I5Sàa, ./) -à I6I6Sàa, ./

24、)Sàa, ./)I7Sà(SR, #Sà(SR, #I8Rà.SR, #Rà.SR, #Sà(SR, ./) -à I5Sàa, ./) -à I6I9Rà), #Rà), #I10Sà(SR, ./)Sà(SR, ./)Rà.SR, ./)Rà), ./)I11Rà.SR, #Rà.SR, #Rà.SR, # -àI8Rà), # -àI9I12Sà(SR, ./)S

25、24;(SR, ./)I13Rà.SR, ./)Rà.SR, ./)Sà(SR, ./) -à I5Sàa, ./) -à I6I14Rà), ./)Rà), ./)I15Rà.SR, #Rà.SR, #I16Rà.SR, ./)Rà.SR, ./)Rà.SR, ./) -àI13Rà), ./) -àI14I17Rà.SR, ./)Rà.SR, ./)无移进-规约冲突和规约-规约冲突，此文法是LR(1)文法。对同心

26、集合并，得LALR(1)项目集规范族：状态核集合项目集 (核集合 + 闭包增加项目)I0SS,#SàS，# Sà(SR，#Sàa，#I1SàS,#SàS,#I2,5Sà(SR，#Sà(SR, ./)/#Sà(SR, ./)Sàa, ./)I3,6Sàa，#Sàa，./)/#I4,10Sà(SR, #Sà(SR, ./)/#Rà.SR, #Rà), #I7,12Sà(SR, #Sà(SR, ./)/#I8,13Rà.S

27、R, #Rà.SR, ./)/#Sà(SR, ./) -à I5Sàa, ./) -à I6I9,14Rà), #Rà), ./)/#I11,16Rà.SR, #Rà.SR,./)/#Rà.SR, # -àI8Rà), # -àI9I15,17Rà.SR, #Rà.SR, ./)/#同心集合并后无冲突，其项目集的个数与LR（0）相同，此文法是LALR（1）文法。11. 设文法GS为：SàAS| AàaA|b(1) 证明GS是L

28、R(1)文法(2) 构造出它的LR(1)分析表(3) 给出输入符号串abab#的分析过程一个文法不是SLR(1)时，不能证明它是LR(1)的解：将文法改写为拓广文法： (0) SS (1) SàAS (2) Sà (3) AàaA (4) Aàb 构造其LR(1)项目集规范族：状态核集合项目集 (核集合 + 闭包增加项目)I0SS,#SàS，# SàAS，#Sà，#AàaA, a/b/#Aàb, a/b/#I1SàS,#SàS,#I2SàAS，#SàAS，#S

29、24;AS，# -àI2Sà，#AàaA, a/b/# -àI3Aàb, a/b/# -àI4I3AàaA, a/b/#AàaA, a/b/#AàaA, a/b/# -àI3Aàb, a/b/# -àI4I4Aàb, a/b/#Aàb, a/b/#I5SàAS，#SàAS，#I6AàaA, a/b/#AàaA, a/b/#LR(1)分析表：状态ACTIONGOTOab#SA0S3S4r2121acc2S3S4r252

30、3S3S464r4r4r45r16r3r3r3对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题：已知文法为： Sàa|Ù|(T) TàT,S|S (1) 构造它的LR(0)、LALR（1），LR（1）分析表（2） 给出对输入符号长(a#和(a,a#的分析过程（3）

31、说明（1）中三种分析表发现错误的时刻和输入串的出错位置有何区别。解：构造该文法的LR(0)项目集规范集：I0:Sà.SI2:Sàa.I5:Sà(T.)I9:TàT,S.Sà.aI3:Sà.TàT.,SSà.I4:Sà(.T)I6:TàS.Sà.(T)Tà.T,SI7:Sà(T).I1:SàS.Tà.SI8:TàT,.SSà.aSà.aSà.Sà.Sà.(T)Sà(T)构造LR(

32、0)分析表：状态ACTIONGOTOa(),#ST0S2S3S411acc2r2r2r2r2r2r23r3r3r3r3r3r34S2S3S4655S8S76r6r6r6r6r6r67r4r4r4r4r4r48S2S3S499r5r5r5r5r5r5构造LR(1)规范集族：I0:Sà.S，#I2:Sàa.，#I5:Sà(T.)，#I9:TàT,S.,)Sà.a，#I3:Sà.，#TàT.,S,)I10:S->a.,)Sà.，#I4:Sà(.T)，#I6:TàS.,)I11:S->.,)Sà.(T)，#Tà.T,S，）I7:Sà(T).,#I12:S->(.T),)I1:SàS.，#Tà.S，）I8:TàT,.S,)T->.T,S,)Sà.a，）Sà.a,)T->.S,)Sà.，）Sà.,)S->.a,)Sà.(T)，）Sà(T),)S->.,I13:S->(T.),)I