大三下-编译最终作业

自底向上语法分析——LR分析方法1.

AaAd

|

aAb

|

判断该文法是否为SLR(1)文法，若是构造分析表，并对输入串ab#给出分析过程。增广文法：AAA

aAdA

aAbAI0

：{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)文法。0I

的

解决：Follow(A)={d,b,#}，移进符号集为｛a｝，Follow(A)

｛a}=,所以I0遇见a移进，遇见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.}2I

：{Aa.Ad,Aa.Ab，A.aAd,A.aAb，A.}I

：{AaA.d,AaA.b}3I4：

{AaAd.}5I

：{AaAb.}状态ACTIONGOTOabd#A0S2R3R3R311ACC2S2R3R3R333S5S44R1R1R15R2R2R2SLR(1)分析表增广文法：AAA

aAdA

aAbA自底向上语法分析——LR分析方法1.

AaAd

|

aAb

|

判断该文法是否为SLR(1)文法，若是构造分析表，并对输入串ab#给出分析过程。状态ACTIONGOTOabd#A0S2R3R3R311ACC2S2R3R3R333S5S44R1R1R15R2R2R2SLR(1)分析表增广文法：(0)AA(1)AaAd(2)AaAb步骤状态栈符号栈输入流动(作3)A00#ab#S2102#ab#r32023#aAb#S530235#aAb#r2401#A#acc输入串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)B1I0：{S.S，S.L*L,S.L，L.LBL.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}因为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)B1I0：{S.S，S.L*L,S.L，L.LBL.B,

B.0,

B.1}I1

：{SS.}I2：{SL.*L,SL.，LL.B,B.0,B.1}I3：

{LB.}

I4：{B0.}

I5：{B1.}I

：{SL*.L，L.LB,L.B,B.0,B.1}6I7：

{LLB.}I8：{SL*L.,

LL.B,

B.0,B.1}followS’0,1#S0,1#L0,1*,0,1,#B0,1*,0,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给出分析过程。I0：{S.S，S.L*L,S.L，L.LBL.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}增广文法：(0)SS

(1)SL*L

(2)SL(3)LLB

(4)LB

(5)B0(6)B1自底向上语法分析——LR分析方法3.SAS|b

ASA|a判断该文法是否为SLR(1)文法，若是构造分析表.增广文法：(0)SS

(1)SAS(2)Sb

(3)ASA(4)AaI0：{S.S，S.AS,S.b，A.SA,

A.a}1I ：{SS.,

AS.A,

A.SA,

A.a,S.AS,S.b}I2：{SA.S,S.AS,S.b,A.SA,

A.a}3

4I

：{Sb.} I

：{Aa.}I5：

{ASA.,

SA.S,

S.AS,S.b,A.SA,

A.a}I6：{AS.A,

A.SA,

A.a,

S.AS,S.b}7I

：{SAS.,AS.A,

A.SA,

A.a,S.AS,S.b}因为II7:有移进-归约所以该文法不是LR(0)文法。5:

S->.bA->.aA->SA.

用A->SA归约S->AS.A->.aS->.b遇b移进遇a移进用S->AS归约遇a移进遇b移进自底向上语法分析——LR分析方法3.SAS|b

ASA|a判断该文法是否为

SLR(1)文法，若是构造分析表.增广文法：(0)SS

(1)SAS(2)Sb

(3)ASA(4)AaI1

：{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}follow{A}{a,b}

,

无法解决.7I

：{SAS.,AS.A,

A.SA,

A.a,S.AS,S.b}follow{S}{a,b}

,

无法解决.followSa,ba,b,#Aa,ba,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)，LALR(1),LR(1)，说明理由.(2)构造相应的分析表增广文法：(0)SS

(1)SUTa

(2)STb(3)TS

(4)TSc

(5)Td(6)UUS

(7)UeI0：

{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}I4：

{Ue.} I5：

{Td.}I8：

{UUS.,

TS.,

TS.c}I3:

{ST.b}I6：

{TSc.}I7：

{SUT.a,ST.b}I9：

{STb.}I10：

{SUTa.}I1

、I8

有，不是LR(0)文法。自底向上语法分析——LR分析方法(0)SS

(1)SUTa

(2)STb(3)TS

(4)TSc

(5)Td(6)UUS

(7)Ue1解I8：但是，

follow{U}follow{T}=

,且二者均不含移进符号c所以，移进-归约 解决，是SLR(1)文法followTa,bUd,eS#,a,b,c,d,e但是，follow{T}{c}=

,决。U->US.T->S.T->S.c用r3归约产用r生归6遇c移进产归约生T->S.c

遇c移进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)，说明理由I.：T->S.(2)构造相应的分析表增广文法：增广文法：(0)SS

(1)SUTa(2)STb

(3)TS

(4)TSc(5)Td (6)UUS

(7)UeI0：{S.S,S.UTa,S.Tb,U.USI2：{SU.Ta,UU.S,T.S,T.Sc,I4：

{Ue.}e}I3:

{ST.b}I5：

{Td.}I6：

{TSc.}I7：

{SUT.a,ST.b}I8：

{UUS.,

TS.,

TS.c}9I

：{STb.}10I ：

{SUTa.}followT a,

bU

d,eS

#,a,b,c,d,ea

b

c

d

e

#S

T U

,U.e,T.S,T.Sc,T.d}0S5

S41

32

I1

：{SS.,TS.,TS.c}1

r1

r3

S6acc2S5

S48

72

T.d,S.UTa,S.Tb,U.US,U.3S947r

r755

r

r546

r

r467

S

S938

r

r3

S6

r6

r629

r

r2

r2

r2

r2

r2110

r1

r1

r1

r

r

r1

1SLR(1)分析表自底向上语法分析——LR分析方法增广文法：(0)SS

(1)SA

(2)AAb(3)AbBa

(4)BaAc

(5)Ba(6)BaAb7.证明下面文法不是LR(0),但是SLR(1).SA

AAb|bBa

BaAc|a|aAbI0

：{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分析方法7.证明下面文法不是LR(0),但是SLR(1).SA

AAb|bBaBaAc|a|aAb增广文法：(0)SS

(1)SAAAbAbBa

(4)BaAc(5)Ba

(6)BaAbI2：{SA.,AA.b}存在移进-归约

。follow{S}{b}=

,

解决。I6：

{Ba.Ac,

Ba.,Ba.Ab,A.Ab，A.bBa}存在移进-归约

。follow{B}{b}=

,

解决。I10：

{BaAb.,

AAb.}存在归约-归约

。follow{B}

follow{A}=

,解决。followSb#Abb,c,#BaaI0

：

{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}I

：

{AbBa.}7I8：

{BaA.c,

BaA.b,

AA.b}9I

：{BaAc.}babc#SAB0S3121acc2S4R13S654R2R2R25S76R5S387R3R3R38S10S9增广文法I

：：{BaAb.,AA10(0)SS

(1)SA(2)AAb

(3)AbBa(4)BaAc

(5)Ba(6)BaAbfollow9R4Sb#10R6R2R2R2Abb,c,#SLR(1)分析表Baa自底向上语法分析——LR分析方法10.判断下列各题所示是否为LR类文法,若是请说明是

LR(0),SLR(1),LALR(1)或LR(1)的哪一种，并构造相应的分析表，若不是请说明理由。（1）SAB，AaBa|

BbAb|增广文法：(0)SS

(1)SAB

(2)AaBa(3)A

(4)BbAb

(5)BI0：

{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.}20

35I

、I 、I 、I

有

，不是LR(0)文法。自底向上语法分析——LR分析方法10（1）SABAaBa|

BbAb|I0：{A.aBa，A.}存在移进-归约

。follow{A}{a}=

,

解决。I2：

{B.bAb,

B.}存在移进-归约

。follow{B}{b}=

,

解决。I3：{B.bAb,B.}存在移进-归约

。follow{B}{b}=

,

解决。I5：{A.aBa,A.}存在移进-归约

。

同I0.follow{A}{a}=

,

解决。followS#Ab,#Ba,#增广文法：(0)SS

(1)SAB

(2)AaBa(3)A

(4)BaAb

(5)B动作表转换表ab#SAB0S3r3r3121acc2r5S5r543r5S5r564r15S3r3r376S87S98r

2r

29r4r4SLR(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.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)BfollowS#Ab,#Ba,

#自底向上语法分析——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)B0I

：{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.}I0

有，移进-归约及归约-归约，不是LR(0)文法。自底向上语法分析——LR分析方法（2）SD;B|BDd|

BB;a|a|I0：{S.S,

S.D;B,

S.B,D.d,

D.,B.B;a,B.a,B.}I0:D->.B->.有归约-归约，follow{B}

follow{D}={;},不能用SLR(1)解决。followS#B;

#D;增广文法：(0)SS

(1)SD;B

(2)SB(3)Dd

(4)D

(5)BB;a(6)Bd

(7)Bad;#SBD0S5S4r4r7r71321acc2S63S7r24r35r6r66S5r7r787S98S7r19r5r5SLR(1)分析表增广文法：(0)SS

(1)SD;B(2)SB

(3)Dd(4)D

(5)BB;a(6)Bd

(7)BI0：{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.}5I

：{Ba.}I

：{SD;.B,B.B;a.B.a,B.}6I7：

{BB;.a}I8：

{SD;B.,B