作业参考答案c7-LR

1、,自底向上语法分析LR分析方法,1. AaAd | aAb | 判断该文法是否为SLR(1)文法，若是构造分析表，并对输入串ab# 给出分析过程。,增广文法： (0)AA (1)A aAd (2)A aAb (3)A,I0：A.A，A.aAd,A.aAb， A. I1 ：AA. I2：Aa.Ad,Aa.Ab， A.aAd,A.aAb，A. I3： AaA.d,AaA.b I4： AaAd. I5： AaAb. 因为I0、I2都包含了移进-归约冲突，所以该文法不是LR(0)文法。,I0的冲突解决： Follow(A)=d,b,#，移进符号集为a， Follow(A) a=, 所以I0遇见a 移进

2、，遇见d,b,#时用A归约。 I2 的解决方法与I0 相同。 该文法通过向前看一个符号，解决了LR(0)冲突，所以是SLR(1)文法。,自底向上语法分析LR分析方法,1. AaAd | aAb | 判断该文法是否为SLR(1)文法，若是构造分析表，并对输入串ab# 给出分析过程。,I0：A.A，A.aAd,A.aAb，A. I1 ：AA. I2：Aa.Ad,Aa.Ab， A.aAd,A.aAb，A. I3： AaA.d,AaA.b I4： AaAd. I5： AaAb.,SLR(1)分析表,增广文法： (0)AA (1)A aAd (2)A aAb (3)A,自底向上语法分析LR分析方法,1.

3、 AaAd | aAb | 判断该文法是否为SLR(1)文法，若是构造分析表，并对输入串ab# 给出分析过程。,SLR(1)分析表,增广文法： (0)AA (1)A aAd (2)A aAb (3)A,输入串 ab# 的分析过程,自底向上语法分析LR分析方法,2. SL*L|L LLB|B B0|1 为该文法构造LR分析表，并说明属哪类分析表，并对输入串101*110给出分析过程。,增广文法： (0)SS (1)SL*L (2)SL (3)LLB (4)LB (5)B0 (6)B1,I0：S.S，S.L*L,S.L，L.LB L.B, B.0, B.1 I1 ：SS. I2：SL.*L,SL.

4、，LL.B,B.0,B.1 I3： LB. I4：B0. I5：B1. I6：SL*.L，L.LB,L.B,B.0,B.1 I7： LLB. I8：SL*L., LL.B, B.0,B.1,因为I2、I8都包含了移进-归约冲突， 所以该文法不是LR(0)文法。,2. SL*L|L LLB|B B0|1 为该文法构造LR分析表，并说明属哪类分析表，并对输入串101*110给出分析过程。,增广文法： (0)SS (1)SL*L (2)SL (3)LLB (4)LB (5)B0 (6)B1,I0：S.S，S.L*L,S.L，L.LB L.B, B.0, B.1 I1 ：SS. I2：SL.*L,SL

5、.，LL.B,B.0,B.1 I3： LB. I4：B0. I5：B1. I6：SL*.L，L.LB,L.B,B.0,B.1 I7： LLB. I8：SL*L., LL.B, B.0,B.1,I2:移进符号集合*,0,1 Follow(S) *,0,1= 遇#用SL归约, 遇 *,0,1 移进.,I8:移进符号集合0,1 Follow(S) 0,1= 遇#用SL*L 归约, 遇 0,1 移进.,该文法通过向前看1个符号,解决冲突,是SLR(1)文法.,2. SL*L|L LLB|B B0|1 为该文法构造LR分析表，并说明属哪类分析表，并对输入串101*110给出分析过程。,增广文法： (0)

6、SS (1)SL*L (2)SL (3)LLB (4)LB (5)B0 (6)B1,I0：S.S，S.L*L,S.L，L.LB L.B, B.0, B.1 I1 ：SS. I2：SL.*L,SL.，LL.B,B.0,B.1 I3： LB. I4：B0. I5：B1. I6：SL*.L，L.LB,L.B,B.0,B.1 I7： LLB. I8：SL*L., LL.B, B.0,B.1,自底向上语法分析LR分析方法,3. SAS|b ASA|a 判断该文法是否为SLR(1)文法，若是构造分析表.,增广文法： (0)SS (1)SAS (2)Sb (3)ASA (4)Aa,I0：S.S，S.AS,S

7、.b，A.SA, A.a I1 ：SS., AS.A, A.SA, A.a, S.AS,S.b I2：SA.S,S.AS,S.b,A.SA, A.a I3： Sb. I4： Aa. I5： ASA., SA.S, S.AS,S.b, A.SA, A.a I6：AS.A, A.SA, A.a, S.AS,S.b I7：SAS.,AS.A, A.SA, A.a, S.AS,S.b,因为I5: I7: 有移进-归约冲突 所以该文法 不是LR(0)文法。,自底向上语法分析LR分析方法,3. SAS|b ASA|a 判断该文法是否为SLR(1)文法，若是构造分析表.,增广文法： (0)SS (1)SAS

8、 (2)Sb (3)ASA (4)Aa,I1 ：SS., AS.A, A.SA, A.a, S.AS,S.b 遇#接受, 遇a,b移进.冲突可以解决. I5： ASA., SA.S, S.AS,S.b, A.SA, A.a followA a,b ,冲突无法解决. I7：SAS.,AS.A, A.SA, A.a, S.AS,S.b followS a,b ,冲突无法解决.,该文法不是SLR(1)文法,自底向上语法分析LR分析方法,6. 文法G=(U,T,S,a,b,c,d,e,P,S),其中P为： S-UTa|Tb，T-S|Sc|d,U-US|e (1)判断G是否LR(0),SLR(1)，LA

9、LR(1),LR(1)，说明理由. (2)构造相应的分析表,增广文法： (0)SS (1)SUTa (2)STb (3)TS (4)TSc (5)Td (6)UUS (7)Ue,I0： S.S, S.UTa, S.Tb, U.US, U.e, T.S,T.Sc, T.d I1 ：SS.,TS.,TS.c I2： SU.Ta,UU.S, T.S,T.Sc,T.d, S.UTa,S.Tb,U.US,U.e I3: ST.b I4： Ue. I5： Td. I6： TSc. I7： SUT.a,ST.b I8： UUS., TS., TS.c I9： STb. I10： SUTa.,I1 、I8 有

10、冲突， 不是LR(0)文法。,自底向上语法分析LR分析方法,增广文法： (0)SS (1)SUTa (2)STb (3)TS (4)TSc (5)Td (6)UUS (7)Ue,I1： 产生冲突 但是，followTc= ,冲突解决。 I8： 产生冲突 但是，followUfollowT= ,且二者均不含移进符号c 所以，移进-归约冲突解决，是SLR(1)文法,6. 文法G=(U,T,S,a,b,c,d,e,P,S),其中P为：S-UTa|Tb， T-S|Sc|d,U-US|e (1)判断G是LR(0),SLR(1)， LALR(1)还是LR(1)，说明理由. (2)构造相应的分析表,增广文法

11、：(0)SS (1)SUTa (2)STb (3)TS (4)TSc (5)Td (6)UUS (7)Ue,I0：S.S,S.UTa,S.Tb,U.US ,U.e,T.S,T.Sc,T.d I1 ：SS.,TS.,TS.c I2：SU.Ta,UU.S,T.S,T.Sc, T.d,S.UTa,S.Tb,U.US,U.e I3: ST.b I4： Ue. I5： Td. I6： TSc. I7： SUT.a,ST.b I8： UUS., TS., TS.c I9： STb. I10： SUTa.,SLR(1)分析表,自底向上语法分析LR分析方法,7. 证明下面文法不是LR(0),但是SLR(1).

12、 SA AAb|bBa BaAc|a|aAb,增广文法： (0)SS (1)SA (2)AAb (3)AbBa (4)BaAc (5)Ba (6)BaAb,I0：S.S，S.A,A.Ab，A.bBa I1 ：ss. I2：SA.,AA.b I3:Ab.Ba,B.aAc,B.a,B.aAb I4： AAb. I5： AbB.a I6： Ba.Ac, Ba.,Ba.Ab, A.Ab，A.bBa I7： AbBa. I8： BaA.c, BaA.b, AA.b I9： BaAc. I10： BaAb., AAb.,I2 、I6 、I10 有冲突， 不是LR(0)文法。,自底向上语法分析LR分析方法,

13、7. 证明下面文法不是LR(0),但是SLR(1). SA AAb|bBa BaAc|a|aAb,增广文法： (0)SS (1)SA (2)AAb (3)AbBa (4)BaAc (5)Ba (6)BaAb,I2：SA.,AA.b 存在移进-归约冲突。 followSb= ,冲突解决。 I6： Ba.Ac, Ba.,Ba.Ab, A.Ab，A.bBa 存在移进-归约冲突。 followBb= ,冲突解决。 I10： BaAb., AAb. 存在归约-归约冲突。 followB followA= , 冲突解决。,增广文法： (0)SS (1)SA (2)AAb (3)AbBa (4)BaAc (

14、5)Ba (6)BaAb,I0：S.S，S.A,A.Ab，A.bBa I1 ：ss. I2：SA.,AA.b I3:Ab.Ba,B.aAc,B.a,B.aAb I4： AAb. I5： AbB.a I6： Ba.Ac, Ba.,Ba.Ab, A.Ab，A.bBa I7： AbBa. I8： BaA.c, BaA.b, AA.b I9： BaAc. I10： BaAb.,AAb.,SLR(1)分析表,自底向上语法分析LR分析方法,10. 判断下列各题所示是否为LR类文法,若是请说明是LR(0),SLR(1),LALR(1)或LR(1)的哪一种，并构造相应的分析表，若不是请说明理由。 （1）SAB

15、，AaBa| BbAb|,增广文法： (0)SS (1)SAB (2)AaBa (3)A (4)BbAb (5)B,I0： S.S，S.AB, A.aBa，A. I1 ：SS. I2： SA.B, B.bAb, B. I3: Sa.Ba,B.bAb,B. I4： SAB. I5： Bb.Ab, A.aBa,A. I6： AaB.a I7： BbA.b I8： AaBa. I9： BbAb.,I0、I2 、I3 、I5 有冲突， 不是LR(0)文法。,自底向上语法分析LR分析方法,10（1）SAB AaBa| BbAb|,I0：A.aBa，A. 存在移进-归约冲突。 followAa= ,冲突解

16、决。 I2： B.bAb, B. 存在移进-归约冲突。 followBb= ,冲突解决。 I3： B.bAb,B. 存在移进-归约冲突。 followBb= ,冲突解决。 I5： A.aBa,A. 存在移进-归约冲突。 同I0. followAa= , 冲突解决。 所以，文法不是LR(0)文法，而是SLR(1)文法。,增广文法： (0)SS (1)SAB (2)AaBa (3)A (4)BaAb (5)B,SLR(1)分析表,I0： S.S，S.AB, A.aBa，A. I1： SS. I2： SA.B,B.bAb, B. I3: Aa.Ba,B.bAb,B. I4： SAB. I5： Bb.

17、Ab, A.aBa,A. I6： AaB.a I7： BbA.b I8： AaBa. I9： BbAb.,增广文法： (0)SS (1)SAB (2)AaBa (3)A (4)BaAb (5)B,自底向上语法分析LR分析方法,10. 判断下列各题所示是否为LR类文法,若是请说明是LR(0),SLR(1),LALR(1)或LR(1)的哪一种，并构造相应的分析表，若不是请说明理由。 （2） SD;B|B， Dd| BB;a|a|,增广文法： (0)SS (1)SD;B (2)SB (3)Dd (4)D (5)BB;a (6)Bd (7)B,I0：S.S, S.D;B, S.B, D.d, D.,B

18、.B;a,B.a,B. I1 ：SS. I2： SD.;B I3: SB.,BB.;a I4： Dd. I5： Ba. I6： SD;.B,B.B;a.B.a,B. I7： BB;.a I8： SD;B.,BB.;a I9： BB;a.,I0 有冲突，移进-归约及归约-归约冲突，不是LR(0)文法。,自底向上语法分析LR分析方法,（2）SD;B|B Dd| BB;a|a|,I0：S.S, S.D;B, S.B, D.d, D.,B.B;a,B.a,B. I0: D-. B-. 有归约-归约冲突， followB followD=;, 不能用SLR(1)解决。,增广文法： (0)SS (1)SD

19、;B (2)SB (3)Dd (4)D (5)BB;a (6)Bd (7)B,SLR(1)分析表,增广文法： (0)SS (1)SD;B (2)SB (3)Dd (4)D (5)BB;a (6)Bd (7)B,I0：S.S,S.D;B,S.B, D.d,D.,B.B;a, B.a,B. I1 ：SS. I2： SD.;B I3: SB.,BB.;a I4： Dd. I5： Ba. I6： SD;.B,B.B;a.B.a,B. I7： BB;.a I8： SD;B.,BB.;a I9： BB;a.,自底向上语法分析LR分析方法,10. 判断下列各题所示是否为LR类文法,若是请说明是LR(0),S

20、LR(1),LALR(1)或LR(1)的哪一种，并构造相应的分析表，若不是请说明理由。 （3）SaAd|eBd|aBr|eAr，Aa, Ba,增广文法： (0)SS (1)S.aAd (2)S.eBd (3)S.aBr (4)S.eAr (5)Aa (6)Ba,I0：S.S, S.aAd, S.eBd， S.aBr, S.eAr I1 ：SS. I2： Sa.Ad,Sa.Br,A.a, B.a I3: Se.Bd,Se.Ar,B.a,A.a I4： SaA.d I5： SaB.r I6： Aa., Ba. 未完。已经发现冲突。,I6 有冲突， 不是LR(0)文法。,自底向上语法分析LR分析方法

21、,（3）SaAd|eBd|aBr|eAr Aa Ba,I6： Aa.,Ba. f(I6,d),f(I6,r)均为归约-归约冲突，不可解决 不是SLR(1)文法，也不是LR(0)文法,增广文法： (0)SS (1)S.aAd (2)S.eBd (3)S.aBr (4)S.eAr (5)Aa (6)Ba,SLR(1)分析表,I0：S.S,S.aAd,S.eBd，S.aBr, S.eAr I1 ：ss. I2：Sa.Ad,Sa.Br,A.a, B.a I3:Se.Bd,Se.Ar,B.a,A.a I4： SaA.d I5： SaB.r I6： Aa., Ba.,增广文法： (0)SS (1)S.aAd (2)S.eBd (3)S.aBr (4)S.eAr (5)Aa (6)Ba,表中有归约、归约冲突。不是SLR(1)文法。,18(p168)：GE 拓广文法如下：(0) SE (3) TT*F (1)