編譯原理及實(shí)現(xiàn)課后答案

5.1考慮以下的文法：

S-S;T|T

Tfa

(1)為這個(gè)文法構(gòu)造LR(0)的項(xiàng)目集規(guī)范族。

(2)這個(gè)文法是不是LR(0)文法？如果是，則構(gòu)造LR(0)分析表。

(3)對(duì)輸入串“a;a”進(jìn)行分析。

解：

(1)拓廣文法G[S']：

0：S'-S

1：S-S;T

2：S-T

3：T-a

構(gòu)造LR(0)項(xiàng)目集規(guī)范族

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'?SG0[0,S]=l

S-?S;TG0[0,S]=l

S-?TG0[0,T]=2

T—?aG0[0,a]=3

1S'—S?ACCEPT

S-S?；TGO[1,;]=4

2S->T?R2

3T—a?R3

4S-S;*TGO[4,T]=5

T—?aG0[4,a]=3

5S—S;T?RI

(2)該文法不存在“歸約一歸約”和“歸約一移進(jìn)”沖突，因此是LR(0)文法。LR(0)分析

表如下：

ACTIONGOTO

狀態(tài)

?a#ST

0S312

1S4ACCEPT

2R2R2R2

3R3R3R3

4S35

5RIRIRI

(3)對(duì)輸入串“a;a”進(jìn)行分析如下:

步驟狀態(tài)棧符號(hào)棧輸入符號(hào)棧ACTIONGOTO

00#a;a#S3

103#a;a#R32

302#T;a#R21

401#S;a#S4

5014#s；a#S3

60143#S;anR35

70145#S;TnRI1

801#SACCEPT

5.2證明下面文法是SLR(l)文法，但不是LR(O)文法。

S-*A

A—Ab|bBa

B-*aAc|a|aAb

解：文法G[S]：

0：S-A

1：AfAb

2：A-**bBa

3：B-aAc

4：Bfa

5：B—aAb

構(gòu)造LR(0)項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0Sf?AG0[0,A]=l

A—?AbG0[0,A]=l

A—?bBaG0[0,b]=2

1SfA?ACCEPT

A-A?bGO[1,b]=3

2A—b?BaGO[2,B]=4

Bf?aAcGO[2,a]=5

B-**aGO[2,a]=5

Bf?aAbGO[2,a]=5

3AfAb?RI

4A--bB,aGO[4,a]=6

5B-a-AcGO[5,A]=7

B-a?R4

B—a?AbGO[5,A]=7

A->?AbGO[5,A]=7

A-**bBaGO[5,b]=2

6A—bBa?R2

7BfaA?cGO[7,c]=8

B—aA?bGO[7,b]=9

AfA?bGO[7,b]=9

8B—aAc?R3

9BfaAb?R5

A—Ab-RI

狀態(tài)5存在“歸約一移進(jìn)”沖突，狀態(tài)9存在“歸約一歸約”沖突，因此該文法不是LR(O)

文法。

狀態(tài)5：

FOLLOW(B)={a},因此，F(xiàn)OLLOW(B)n=6

狀態(tài)9：

FOLLOW(B)={a},FOLLOW(A)={#,b,c),因此FOLLOW(B)DFOLLOW(A)=①

狀態(tài)5和狀態(tài)9的沖突均可用SLR(l)方法解決，構(gòu)造SLR(l)分析表如下：

ACTIONGOTO

狀態(tài)

abc#AB

0S21

1S3ACCEPT

2S54

3RIRIRI

4S6

5R4S27

6R2R2R2

7S9S8

8R3

9R5RIRIRI

該SLR(l)分析表無(wú)重定義，因此該文法是SLR(1)文法，不是LR(O)文法。

5.3證明下面文法是LR(1)文法，但不是SLR(l)文法。

S-*AaAb|BbBa

A—e

Bfe

解：拓廣文法G[S']：

0：S'fs

1：S-AaAb

2：S-BbBa

3：Ai

4：B-e

構(gòu)造LR(0)項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'—?SG0[0,S]=l

S-**AaAbG0[0,A]=2

S-?BbBaGO[0,B]=3

A-**R3

B-?R4

1S'--s?ACCEPT

2S-*A?aAbG0[2,a]=4

3S-*B?bBaG0[3,b]=5

4S-*Aa?AbG0[4,A]=6

A一,R3

5S-*Bb?BaG0[5,B]=7

Bf?R4

6S-*AaA?bG0[6,b]=8

7S-BbB-aG0[7,a]=9

8SfAaAb?RI

9S—BbBa?R2

狀態(tài)0存在“歸約一歸約”沖突，且FOLLOW(A)={a,b},FOLLOW(B)={a,b},即FOLLOW(A)

AFOLLOW(B)={a,b}H①，所以該文法不是SLR(1)文法。

構(gòu)造LR(1)項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'?S,#G0[0,S]=l

S—?AaAb,#G0[0,A]=2

S->?BbBa,#G0[0,B]=3

A—?,aR3

Bf?，bR4

1S'~S?，#ACCEPT

2SfA?aAb,#G0[2,a]=4

3S-*B?bBa,#G0[3,b]=5

4SfAa?Ab,#G0[4,A]=6

A一?,bR3

5S-*Bb?Ba,#G0[5,B]=7

B-*?,aR4

6S-AaA?b,#G0[6,b]=8

7S-*BbB?a,#G0[7,a]=9

8SfAaAb,,#RI

9S-BbBa?，#R2

LR⑴分析表:

ACTIONGOTO

狀態(tài)

abSAB

0R3R4123

1ACCEPT

2S4

3S5

4R36

5R47

6S8

7S9

8RI

9R2

分析表無(wú)重定義，說(shuō)明該文法是LR(1)文法，不是SLR(l)文法。

5.4考慮以下的文法：

E—EE+

E^EE*

E-*a

(1)為這個(gè)文法構(gòu)造LR(1)項(xiàng)目集規(guī)范族。

(2)構(gòu)造LR⑴分析表。

(3)為這個(gè)文法構(gòu)造LALR(l)項(xiàng)目集規(guī)范族。

(4)構(gòu)造LALR⑴分析表。

(5)對(duì)輸入符號(hào)串“aa*a+”進(jìn)行LR⑴和LALR(1)分析。

解：

(1)拓廣文法G[S]：

0：SfE

1：EfEE+

2：EfEE*

3：Efa

構(gòu)造LR⑴項(xiàng)目集規(guī)范族：

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0Sf?E,#G0[0,E]=l

E->?EE+,a:#G0[0,E]=l

E-**EE*,a:#G0[0,E]=l

Ef?a,a:#GOEO,a]=2

1SfE?，#ACCEPT

E-*E?E+,a:#G0[l,E]=3

EfE?E*,a:#G0[LE]=3

E-*?EE+,*:+G0[l,E]=3

Ef?EE*,*:+G0[LE]=3

E—?a,*:+G0[La]=4

2Efa?,a:#R3

3EfEE?+,a:#G0[3,+]=5

E-EE?*,a:#G0[3,*]=6

EfE?E+,*:+G0[3,E]=7

E-E*E*,*:+G0[3,E]=7

Ef?EE+,*:+G0[3,E]=7

Ef?EE*,*:+G0[3,E]=7

E—?a,*:+G0[3,a]=4

4E-a*,*:+R3

5EfEE+?,a:#RI

6E-EE*?,a:#R2

7EfEE-+,*:+G0[7,+]=8

EfEE?*,*:+G0[7,*]=9

E—E?E+,*:+G0[7,E]=7

E->E*E*,*:+G0[7,E]=7

Ef?EE+,*:+G0[7,E]=7

Ef-EE*,*:+G0[7,E]=7

E-**a,*:+G0[7,a]=4

8EfEE+*,*:+RI

9E-EE**,*:+R2

(2)構(gòu)造LR⑴分析表

ACTIONGOTO

狀態(tài)

+*anE

0S21

1S4ACCEPT3

2R3R3

3S5S6S47

4R3R3

5RIRI

6R2R2

7S8S9S47

8RIRI

9R2R2

(3)構(gòu)造LALR(l)項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S->?E,#G0[0,E]=l

E-?EE+,a:#G0[0,E]=l

Ef?EE*,a:#G0[0,E]=l

E—?a,a:#G0[0,a]=2

1SfE?,#ACCEPT

EfE?E+,a:#GO[1,E]=3

E-*E,E*,a:#GO[1,E]=3

Ef?EE+,*:+G0[l,E]=3

E—?EE*,*:+GO[1,E]=3

E-?a.*:+GO[1,a]=2

2Efa?,a:#:*:+R3

3E~EE?+,a:#:*:+G0[3,+]=4

E—EE?*,a:#:*：+G0[3,*]=5

EfE?E+,*:+G0[3,E]=3

E—E*E*,*:+G0[3,E]=3

Ef?EE+,*:+G0[3,E]=3

E—?EE*,*:+G0[3,E]=3

E-?a,*:+G0[3,a]=2

4EfEE+?,a:#:*:+RI

5E—EE*?,a:#:*:+R2

(4)構(gòu)造LALR⑴分析表。

狀態(tài)ACTIONGOTO

+*a#E

0S21

1S2ACCEPT3

2R3R3R3R3

3S4S5S23

4R1R1RIRI

5R2R2R2R2

(5)對(duì)輸入符號(hào)串“aa*a+”進(jìn)行LR(D分析:

步驟狀態(tài)棧符號(hào)棧輸入串ACTIONGOTO

10#aa*a+#S2

202a*a+#R31

301#Ea*a+#S4

4014#Ea*a+#R33

5013#EE*a+#S6

60136#EE*a+#R21

701#Ea+#S4

8014#Ea+#R33

9013#EE+#S5

100135#EE+RI1

1101#E#ACCEPT

對(duì)輸入符號(hào)串“aa*a+”進(jìn)行LALR(l)分析:

步驟狀態(tài)棧符號(hào)棧輸入串ACTIONGOTO

10#aa*a+#S2

202#aa*a+#R31

301#Ea*a+#S2

4012#Ea*a+#R33

5013#EE*a+#S5

60135#EE*ai#R21

701#Ea+#S2

8012#Ea+#R33

9013#EE+#S4

100134#EE+RI1

1101#EACCEPT

5.5說(shuō)明以下的文法是LR(1)文法，但不是LALR(l)文法。

S-*aAd|bBd|aBe|bAe

A-*c

B-*c

解：

拓廣文法：

0：S'fS

1：SfaAd

2：S—bBd

3：S-aBe

4：S-*-bAe

5：A—c

6：Bfc

構(gòu)造LR⑴項(xiàng)目集規(guī)范族

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'?S,#G0[0,S]=l

S一,aAd,#G0[0,a]=2

Sf?bBd,#G0[0,b]=3

S—,aBe,#G0[0,a]=2

Sf?bAe,#G0[0,b]=3

1S'fS?,#ACCEPT

2Sfa?Ad,#GO⑵A]=4

S-*a-Be,UG0[2,B]=5

A—,c>dG0[2,c]=6

Bf?c,eGO⑵c]=6

3S~b?Bd,#G0[3,B]=7

Sfb?Ae,#G0[3,A]=8

Af?c,eG0[3,c]=9

B—,c,dG0[3,c]=9

4SfaA?d,#G0[4,d]=10

5SfaB,e,#GOS,e]=ll

6A—c?,dR5

Bfc?,eR6

7S-*bB?d,#G0[7,d]=12

8S—bA?e,#G0[8,e]=13

9A—c?,eR5

Bfc?,dR6

10SfaAd?f#RI

11S—aBe?,#R3

12S-bBd?,#R2

13S->bAe?,#R4

構(gòu)造LR⑴分析表:

ACTIONGOTO

狀態(tài)

abcde#SAB

0S2S31

1ACCEPT

2S645

3S987

4S10

5S11

6R5R6

7S12

8S13

9R6R5

10R1

11R3

12R2

13R4

同核項(xiàng)目集合并，構(gòu)造LALR(l)項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'?S,#G0[0,S]=l

S->?aAd,#G0[0,a]=2

S-**bBd,#G0[0,b]=3

S—?aBe,#G0[0,a]=2

S-**bAe,#G0[0,b]=3

1S'fS?,#ACCEPT

2S-a?Ad,#GO[2,A]=4

S-*a?Be,#GO[2,B]=5

A一,c,dGO[2,c]=6

B-**c,eGO[2,c]=6

3Si?Bd,#GO[3,B]=7

S-*b?Ae,#GO[3,A]=8

Af?c,eGO[3,c]=6

B—?c,dG0[3,c]=6

4S-aA?d,#G0[4,d]=9

5S-*aB?e,#G0[5,e]=10

6A-*c??d:eR5

B-*c?,d:eR6

7S-bB?d,#G0[7,d]=ll

8S->bA?e,#GO?e]=12

9S->aAd-,#RI

10S-*aBe?,#R3

11S-*bBd?,#R2

12S—bAe?,#R4

構(gòu)造LALR(l)分析表:

ACTIONGOTO

狀態(tài)

abcdeSAB

0S2S31

1ACCEPT

2S645

3S987

4S10

5S11

6R5/R6R5/R6

7S12

8S13

9R1

10R3

11R2

12R4

從LR(1)分析表可以看出，分析表無(wú)重定義，因此該文法是LR(1)文法。

從LALR(l)分析表可以看出，分析表ACTI0N［6,d］和ACTIONS,e］存在重定義，因此該文法

不是LALR(l)文法。

7