编译原理及实现课后答案

5.1考虑以下的文法：

S-*S;T|T

Tfa

(1)为这个文法构造LR(O)的项目集规范族。

(2)这个文法是不是LR(O)文法？如果是，则构造LR(O)分析表。

(3)对输入串“a;a”进行分析。

解：

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

0：S'—S

1：S-*S;T

2：S-T

3：T-*a

构造LR(0)项目集规范族

状态项目集转换函数

0S'f・sG0[0,S]=l

Sf•S;TG0[0,S]=l

S->・TG0[0,T]=2

T—•aG0[0,a]=3

1S'-S・ACCEPT

S—S・；TG0[l,;]=4

2S-T・R2

3T-*a•R3

4SfS;•TGO[4,T]=5

T一•aGO[4,a]=3

5S->S;T•RI

(2)该文法不存在“归约一归约”和“归约一移进”冲突，因此是LR(0)文法。LR(O)分析

表如下：

ACTIONGOTO

状态

♦a#ST

0S312

1S4ACCEPT

2R2R2R2

3R3R3R3

4S35

5RIRIRI

(3)对输入串“a;a”进行分析如下:

步骤状态栈符号栈输入符号栈ACTIONGOTO

00#a;a#S3

103#a;a#R32

302#T;a#R21

401#S;a#S4

5014#s；a#S3

60143#S;a#R35

70145#S;T#RI1

801#S#ACCEPT

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

SfA

A-Ab|bBa

B-►aAc|a|aAb

解：文法G[S]：

0：SfA

1：A-Ab

2：A->bBa

3：B-*aAc

4：Bfa

5：B->aAb

构造LR(0)项目集规范族:

状态项目集转换函数

0Sf•AG0[0,A]=1

Af•AbG0[0,A]=l

Af,bBaG0[0,b]=2

1SfA•ACCEPT

A—A•bG0[l,b]=3

2A-*b•BaGO[2,B]=4

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

Bf•aGO[2,a]=5

B-*•aAbGO[2,a]=5

3AfAb・RI

4AfbB•aGO[4,a]=6

5Bfa-AcGO[5,A]=7

Bfa•R4

B-a•AbGO[5,A]=7

Af•AbGO[5,A]=7

Af,bBaGO[5,b]=2

6A-*bBa,R2

7BfaA-cGO[7,c]=8

BfaA•bGO[7,b]=9

A-A,bGO[7,b]=9

8B—aAc,R3

9B-aAb•R5

AfAb•RI

状态5存在“归约一移进”冲突，状态9存在“归约一归约”冲突，因此该文法不是LR(O)

文法。

状态5：

FOLLOW(B)={a},因此,FOLLOW(B)n{b}=L

状态9：

FOLLOW(B)={a},FOLLOW(A)={#,b,c},因此FOLLOW⑻ClFOLLOW(A)=6

状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(l)分析表如下：

ACTIONGOTO

状态

abc#AB

0S21

1S3ACCEPT

2S54

3RIRIRI

4S6

5R4S27

6R2R2R2

7S9S8

8R3

9R5RIRIRI

该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(O)文法。

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

SfAaAb|BbBa

Afe

Bfe

解：拓广文法G［法］:

0：S'fS

1：SfAaAb

2：S->BbBa

3：A->e

4：Bf8

构造LR(O)项目集规范族:

状态项目集转换函数

0S'f•sG0[0,S]=l

Sf•AaAbG0[0,A]=2

Sf•BbBaG0[0,B]=3

A—•R3

Bf•R4

1S,-S•ACCEPT

2SfA•aAbG0[2,a]=4

3S—B•bBaG0[3,b]=5

4SfAa•AbG0[4,A]=6

Af•R3

5SfBb•BaG0[5,B]=7

Bf•R4

6SfAaA•bG0[6,b]=8

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

8SfAaAb•RI

9S->BbBa•R2

状态0存在“归约一归约”冲突，且FOLLOW(A)={a,b},FOLLOW(B)={a,b},即FOLLOW(A)

nFOLLOW(B)={a,b}W①，所以该文法不是SLR(l)文法。

构造LR(1)项目集规范族:

状态项目集转换函数

0S'f・s,#G0[0,S]=l

Sf•AaAb,#G0[0,A]=2

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

Af•,aR3

B一•,bR4

1S'fS・，#ACCEPT

2S-A・aAb,#G0[2,a]=4

3S^B•bBa,#G0[3,b]=5

4S-Aa・Ab,#G0[4,A]=6

Af•,bR3

5SfBb•Ba,#G0[5,B]=7

Bf•,aR4

6SfAaA•b,#GO[6,b]=8

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

8SfAaAb•,#RI

9S->BbBa•,#R2

LR⑴分析表:

ACTIONGOTO

状态

abSAB

0R3R4123

1ACCEPT

2S4

3S5

4R36

5R47

6S8

7S9

8RI

9R2

分析表无重定义，说明该文法是LR(1)文法，不是SLR(l)文法。

5.4考虑以下的文法：

E-*EE+

E-EE*

Efa

(1)为这个文法构造LR(1)项目集规范族。

(2)构造LR⑴分析表。

(3)为这个文法构造LALR(l)项目集规范族。

(4)构造LALR(l)分析表。

(5)对输入符号串“aa*a+”进行LR⑴和LALR⑴分析。

解：

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

0：S-*E

1:E-EE+

2：E-EE*

3：Efa

构造LR(1)项目集规范族：

状态项目集转换函数

0S一•E,#G0[0,E]=l

Ef-EE+,a:#GO[O,E]=l

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

Ef•a,a:#GO[O,a]=2

1S-E・,#ACCEPT

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

EfE•E*,a:#GO[LE]=3

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

E­•EE*,*:+G0[LE]=3

E—•a,*:+G0[l,a]=4

2,a:#R3

3E-EE,+,a:#GO[3,+]=5

EfEE•*,a:#GO[3,*]=6

E-E•E+,*:+GO[3,E]=7

EfE•E*,*:+GO[3,E]=7

E-•EE+,*:+GO[3,E]=7

Ef•EE*,*:+GO[3,E]=7

Ef•a,*:+GO[3,a]=4

4Efa•,*:+R3

5EfEE+•,a:#RI

6EfEE*•,a:#R2

7E-EE•+,*:+GO[7,+]=8

EfEE•*,*:+GO[7,*]=9

E-E•E+,*：+GO[7,E]=7

EfE•E*,*:+GO[7,E]=7

E-•EE+,*:+GO[7,E]=7

Ef•EE*,*:+GO[7,E]=7

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

8E-EE+•,*:+RI

9EfEE*•,*:+R2

(2)构造LR⑴分析表

ACTIONGOTO

状态

+*a#E

0S21

1S4ACCEPT3

2R3R3

3S5S6S47

4R3R3

5RIRI

6R2R2

7S8S9S47

8RIRI

9R2R2

(3)构造LALR(l)项目集规范族:

状态项目集转换函数

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

Ef・EE+,a:#G0[0,E]=l

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

Ef•a,a:#G0[0,a]=2

1S^E•,#ACCEPT

E-*E•E4-,a:#GO[LE]=3

E-E•E*,a:#GOELE]=3

Ef•EE+,*:+GO[LE]=3

E-•EE*,*:+GO[1,E]=3

E-*•a,*:+GO[La]=2

2E-a•,a:#:*:+R3

3E-EE•+,a:#:*:+G0[3,+]=4

E-EE•*,a:#:*:+G0[3,*]=5

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

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

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

E-•EE*,*：+G0[3,E]=3

Ef•a,*:+G0[3,a]=2

4E-EE+•,a:#:*:+RI

5EfEE*•,a:#:*:+R2

(4)构造LALR(l)分析表。

状态ACTIONGOTO

+*a#E

0S21

1S2ACCEPT3

2R3R3R3R3

3S4S5S23

4R1R1RIRI

5R2R2R2R2

(5)对输入符号串“aa*a+”进行LR⑴分析:

步骤状态栈符号栈输入串ACTIONGOTO

10#aa*a+#S2

202ttaa*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+ttRI1

1101#E#ACCEPT

对输入符号串“aa*a+”进行LALR(l)分析:

步骤状态栈符号栈输入串ACTIONGOTO

10#aa*a+#S2

202ttaa*a+#R31

301#Ea*a+#S2

4012#Ea*a+#R33

5013SEE*a+#S5

60135#EE*a+#R21

701#Ea+#S2

8012#Ea+#R33

9013#EE+#S4

100134#EE+ttRI1

1101#EttACCEPT

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

S->aAd|bBd|aBe|bAe

A-*c

B-*c

解：

拓广文法：

0：S'-*s

1：S—aAd

2：S->bBd

3：SfaBe

4：S->bAe

5：A—c

6：Bfc

构造LR⑴项目集规范族

状态项目集转换函数

0S'一・s,#G0[0,S]=l

Sf•aAd,#G0[0,a]=2

S-•bBd,#G0[0,b]—3

S-**aBe,#G0[0,a]=2

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

1S'fS・,#ACCEPT

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

Sfa•Be,#G0[2,B]=5

Af•c,dG0[2,c]=6

Bf•c,eG0[2,c]=6

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

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

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

Bf•c,dG0[3,c]=9

4SfaA•d,#GO[4,d]=10

5SfaB•e,#G0[5,e]=ll

6A—c•,dR5

Bfc•,eR6

7S->bB•d,ttG0[7,d]=12

8S-*bA•e,#GO[8,e]=13

9A—c•,eR5

B-c•,dR6

10S-*aAd•,#RI

11SfaBe•,#R3

12S-*bBd•,#R2

13S-*bAe•,#R4

构造LR⑴分析表:

ACTIONGOTO

状态

abcde#SAB

0S2S31

1ACCEPT

2S645

3S987

4S10

5S11

6R5R6

7S12

8S13

9R6R5

10R1

11R3

12R2

13R4

同核项目嗅誓合并，构造LALR(l)项目集规范族：

状态项目集转换函数

0S'f・s,#G0[0,S]=l

Sf•aAd,#G0[0,a]=2

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

Sf•aBe,#G0[0,a]=2

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

1S'-S・，#ACCEPT

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

Sfa•Be,#GO[2,B]=5

Af•c,dG0[2,c]=6

Bf•c,eGO[2,c]=6

3S->b•Bd,#G0[3,B]=7

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

Af•c,eG0[3,c]=6

Bf•c,dGO[3,c]=6

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

5SfaB•e,#GO[5,e]=10

6Afc•,d:eR5

Bfc•,d:eR6

7SiB・d,#G0[7,d]=U

8S—bA•e,#G0[8,e]=12

9SfaAd・,#RI

10S-*aBe•,#R3

11S-*bBd•,#R2

12S-bAe•,#R4

构造LALR(l)分析表:

ACTIONGOTO

状态

abcde#SAB

0S2S31

1ACCEPT

2S645

3S987

4S10

5S11

6R5/R6R5/R6

7S12

8S13

9R1

10R3

11R2

12R4

从LR(1)分析表可以看出，分析表无重定义，因此该文法是LR(1)文法。

从LALR(l)分析表可以看出，分析表ACTI0N[6,d]和ACTI0N[6,e]存在重定义，因此该文法

不是LALR(l)文法。

7.1给出编译下面程序的有序符号表。

main()

(

intm,n[5];

realx;

charname;

解:

名字类型维数

mint