大三下-編譯最終作業(yè)

自底向上語法分析——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.}狀態(tài)ACTIONGOTOabd#A0S2R3R3R311ACC2S2R3R3R333S5S44R1R1R15R2R2R2SLR(1)分析表增廣文法：AAA

aAdA

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

AaAd

|

aAb

|

判斷該文法是否為SLR(1)文法，若是構造分析表，并對輸入串ab#給出分析過程。狀態(tài)ACTIONGOTOabd#A0S2R3R3R311ACC2S2R3R3R333S5S44R1R1R15R2R2R2SLR(1)分析表增廣文法：(0)AA(1)AaAd(2)AaAb步驟狀態(tài)棧符號棧輸入流動(作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}=

,

解決。I6：

{Ba.Ac,

Ba.,Ba.Ab,A.Ab，A.bBa}存在移進-歸約

。follow{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}=

,

解決。I3：{B.bAb,B.}存在移進-歸約

。follow{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