编译原理 第7章习题解答

第七章 习题解答

7.1 给定文法：

S(A)

AABB

AB

Bb

Bc

① 构造它的基本LR(0)项目集；

② 构造它的LR(0)项目集规范族；

③ 构造识别该文法活前缀的DFA；

④ 该文法是SLR文法吗？若是，构造它的SLR分析表。

7.2 给定文法：

EEE+

EEE*

Ea

① 构造它的LR(0)项目集规范族；

② 它是SLR(1)文法吗？若是，构造它的SLR(1)分析表；

③ 它是LR(1)文法吗？若是，构造它的LR(1)分析表；

④ 它是LALR(1)文法吗？若是，构造它的LALR分析表。

7.3 给出一个非LR(0)文法。

7.4 给出一个SLR(1)文法，但它不是LR(0)文法，构造它的SLR分析表。

7.5 给出一个LR(1)文法，但它不是LALR(1)文法，构造它的规范LR(1)分析表。

7.6 给定二义性文法：

① EE+E

② EE*E

③ E(E)

④ Eid

用所述的无二义性规则和(或)另加一些无二义性规则，例如，给算符*、+施加某种结合规则。

① 构造它的LR(0)项目集规范族及识别活前缀的DFA；

② 构造它的LR分析表。

习题参考答案

7.1 解：文法的基本LR(0)项目集为

S→.(A) S→(.A) S→(A.) S→(A).

A→.ABB A→A.BB A→AB.B A→ABB.

A→.B A→B. B→.b B→b.

B→.c B→c.

构造该文法的识别活前缀的DFSA如下图所示： c S→.(A)

B→b. A→ABB. S→(.A)

A→.ABB

A→.B

B→.b

B→.c

B→c. S→(A).

S→(A.)

A→A.BB

B→.b

B→.c

A→B. A→AB.B

B→.b

B→.c I1 I0

I2

I3 ( )

B b c b c b

I4 I5 I6 I8 I7

B B A

文法的识别活前缀的DFSA

该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8}

因为在构造出来的识别活前缀的DFA中，每一个状态对应的项目集都不含有移进-归约、归约-归约冲突，所以该文法是LR(0)文法，当然也是SLR文法。

因为 FOLLOW(S)={#}

FOLLOW(A)=FIRST{)}∪FIRST(BB)={)，b，c}

FOLLOW(B)=FIRST(B)∪FOLLOW(A)={b，c，)}

其对应的SLR(1)分析表如下表所示。

文法G[S]的SLR(1)分析表

状态 ACTION GOTO

b c ( ) # A B

0 S1

1 S4 S5 2 3

2 S4 S5 S7 6

3 r3 r3 r3

4 r4 r4 r4

5 r5 r5 r5

6 S4 S5 8

7 acc

8 r2 r2 r2

7.2 解：首先构造增广文法如下：

S→E 0

E→EE+ 1

E→EE* 2

E→a 3

(1) 构造它的LR(0)项目集规范族如下图所示。

该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5}

(2) 因为在识别活前缀的DFSA的每一个状态中，都不存在移进-归约冲突和归约-归约冲突，所以文法是LR(0)文法，当然也是SLR(1)文法。

因为 FOLLOW(E)={#，+，*，a}

所以该文法对应的SLR(1)分析表如下表所示。

S→.EE→.EE+E→.EE*E→.aS→E.E→E.E+E→E.E*E→.EE+E→.EE*E→.aE→EE.+E→EE.*E→E.E+E→E.E*E→.EE+E→.EE*E→.aE→EE*.E→EE+.E→a.a+E*EEI1I0I3I2I4I5aa

文法的LR(0)项目集规范族

文法的SLR(1)分析表

状态 ACTION GOTO

a + * # E

0 S2 1

1 S2 acc 3

2 r3 r3 r3 r3

3 S2 S4 S5 7

4 r1 r1 r1 r1

5 r2 r2 r2 r2

(3) 该文法是SLR(1)文法，当然也是LR(1)文法。它的以LR(1)项目集为状态的识别活前缀的DFSA如下图所示。相应的LR(1)分析表如表所示。

[S→E.，#][E→E.E+，#/a][E→E.E*，#/a][E→.EE+，+/*/a][E→.EE*，+/*/a][E→.a，+/*/a][S→.E，#][E→.EE+，#/a][E→.EE*，#/a][E→.a，#/a][E→EE.+，#/a][E→EE.*，#/a][E→E.E+，+/*/a][E→E.E*，+/*/a][E→.EE+，+/*/a][E→.EE*，+/*/a][E→.a，+/*/a][E→a.，#/a][E→a.，+/*/a][E→EE+.，#/a][E→EE*.，#/a]E*I3E[E→EE.+，+/*/a][E→EE.*，+/*/a][E→E.E+，+/*/a][E→E.E*，+/*/a][E→.EE+，+/*/a][E→.EE*，+/*/a][E→.a，+/*/a]+[E→EE+.，+/*/a][E→EE*.，+/*/a]*+I1I0I2EEaaaaI4I7I8I9I5I6

文法的以LR(1)项目集为状态的识别活前缀的DFSA

文法的LR(1)分析表

状态 ACTION GOTO

a + * # E

0 S2 1

1 S4 acc 3

2 r3 r3

3 S4 S5 S6 7 4 r3 r3 r3

5 r1 r1

6 r2 r2

7 S4 S8 S9 7

8 r1 r1 r1

9 r2 r2 r2

(4) 由于文法的以LR(1)项目集为状态的识别活前缀的DFSA中，状态I2和I4、I3和I7、I5和I8、I6和I9是同心项目集，将它们合并后不会产生冲突。因而可构造文法的LALR(1)分析表如下表所示。

文法的LALR(1)分析表

状态 ACTION GOTO

a + * # E

0 S24 1

1 S24 acc 37

24 r3 r3 r3 r3

37 S24 S58 S69 37

58 r1 r1 r1 r1

69 r2 r2 r2 r2

7.3 解：构造二义性文法G：

SaAbScS

SaAbS

G不是LR（0）文法。

7.4 解：构造下面文法G:

SbASB|bA

SdSa|b

BcAa|c

然后构造其SLR分析表。（略)

7.5 解：构造下面的文法G:

SaAa|aBb|bAb|bBa

Ax

Bx

然后构造其LR(1)分析表。(略)

7.6 解：首先构造增广文法如下：

S→E 0

E→E+E 1

E→E*E 2

E→(E) 3

E→id 4

(1) 构造它的识别活前缀的DFSA如下图所示。 *((+S→E.E→E.+EE→E.*EE→E+.EE→.E+EE→.E*EE→.（E）E→.idE→（.E）E→.E+EE→.E*EE→.（E）E→.idE→E*E.E→E.+EE→E.*EE→E+E.E→E.+EE→E.*EE→E*.EE→.E+EE→.E*EE→.（E）E→.idE→（E.）E→E.+EE→E.*EE→（E）.S→.EE→.E+EE→.E*EE→.(E)E→.idE→id.(E(I1+I0EidI3*I4I5idI2idEEI7*I8*++I6I9)

该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8，I9}

(2) 构造它的LR分析表如下表所示。

文法有冲突的LR分析表

状态 ACTION GOTO

id + * ( ) # E

0 S3 S2 1

1 S4 S5 acc

2 S3 S2 6

3 r4 r4 r4 r4 r4 r4

4 S3 S2 r4 7

5 S3 S2 8

6 S4 S5 S9

7 r1 r1/S4 r1/S5 r1 r1 r1

8 r2 r2/S4 r2/S5 r2 r2 r2

9 r3 r3 r3 r3 r3 r3

由于识别文法活前缀的DFSA中，状态I7和I8都存在“移进-归约”冲突，同时，

FOLLOW(E)={#，)，+，*}

即使构造SLR分析表也无法避免冲突。

为此规定*的优先级高于+，且它们均服从左结合，得到无冲突的LR分析表如下表所示。

文法无冲突的LR分析表

状态 ACTION GOTO

id + * ( ) # E

0 S3 S2 1

1 S4 S5 acc

2 S3 S2 6

3 r4 r4 r4 r4 4 S3 S2 r4 7

5 S3 S2 8

6 S4 S5 S9

7 r1 S5 r1 r1

8 r2 r2 r2 r2

9 r3 r3 r3 r3