编译原理 第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如下图所示：

I0 S→.(A) ( I7 S→(A). ) S→(A.) A→A.BB B→.b B→.c b c I1 S→(.A) A→.ABB A→.B B→.b B→.c B b A→B. c I2 A B I6 A→AB.B B→.b B→.c b c B I8 A→ABB. I3 I4 B→b. 文法的识别活前缀的DFSA

I5 B→c. 该文法的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)分析表

状态 0 1 2 3 4 5 6 7 8 ACTION b GOTO ) c ( S1 # A B S4 S4 r3 r4 r5 S4 S5 S5 r3 r4 r5 S5 2 3 6 S7 r3 r4 r5 8 acc 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)分析表如下表所示。

I1I0S→.EE→.EE+E→.EE*E→.aaES→E.E→E.E+E→E.E*E→.EE+E→.EE*E→.aaE→a.I3EI4E→EE.+E→EE.*+E→EE+.E→E.E+E→E.E*EI5E→.EE+E→EE*.E→.EE**E→.aaI2 文法的LR(0)项目集规范族

文法的SLR(1)分析表

状态 0 1 2 3 4 5 ACTION a S2 S2 r3 S2 r1 r2 + GOTO * # E 1 3 acc r3 r3 S4 r1 r2 r3 S5 r1 r2 7 r1 r2 (3) 该文法是SLR(1)文法，当然也是LR(1)文法。它的以LR(1)项目集为状态的识别活前缀的DFSA如下图所示。相应的LR(1)分析表如表所示。

I1[S→E.，#][E→E.E+，#/a][E→E.E*，#/a][E→.EE+，+/*/a][E→.EE*，+/*/a][E→.a，+/*/a]I0EEI3[E→EE.+，#/a][E→EE.*，#/a][E→E.E+，+/*/a][E→E.E*，+/*/a][E→.EE+，+/*/a][E→.EE*，+/*/a][E→.a，+/*/a]aEI5+[E→EE+.，#/a]I6*[E→EE*.，#/a]aI4[E→a.，+/*/a]I7a[E→EE.+，+/*/a][E→EE.*，+/*/a][E→E.E+，+/*/a][E→E.E*，+/*/a][E→.EE+，+/*/a][E→.EE*，+/*/a][E→.a，+/*/a]I8+E*[E→EE+.，+/*/a]I9[E→EE*.，+/*/a][S→.E，#][E→.EE+，#/a][E→.EE*，#/a][E→.a，#/a]I2a[E→a.，#/a] 文法的以LR(1)项目集为状态的识别活前缀的DFSA

文法的LR(1)分析表

状态 0 1 2 3 ACTION a S2 S4 r3 S4 + GOTO * # E 1 3 acc r3 S5 S6 7 4 5 6 7 8 9 r3 r1 r2 S4 r1 r2 r3 r3 r1 r2 7 S8 r1 r2 S9 r1 r2 (4) 由于文法的以LR(1)项目集为状态的识别活前缀的DFSA中，状态I2和I4、I3和I7、I5和I8、I6和I9是同心项目集，将它们合并后不会产生冲突。因而可构造文法的LALR(1)分析表如下表所示。

文法的LALR(1)分析表

状态 0 1 24 37 58 69 ACTION a S24 S24 r3 S24 r1 r2 + GOTO * # E 1 37 acc r3 r3 S58 r1 r2 r3 S69 r1 r2 37 r1 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如下图所示。

I4I1+S→E.E→E.+EE→E.*EES→.EE→.E+EE→.E*EE→.(E)E→.idid*I5E→E+.EEE→.E+EE→.E*E(E→.（E）E→.idI7E→E+E.+E→E.+EE→E.*E*I0E→E*.EE→.E+EE→.E*EEidE→.（E）(E→.idI2E→（.E）E→.E+EEE→.E*E(idE→.（E）E→.id+*E→E*E.E→E.+EE→E.*EI6E→（E.）*E→E.+EE→E.*E+)I9E→（E）.I8(I3E→id. 该文法的LR(0)项目集规范族={I0，I1，I2，I3，I4，I5，I6，I7，I8，I9} (2) 构造它的LR分析表如下表所示。

文法有冲突的LR分析表

状态 0 1 2 3 4 5 6 7 8 9 ACTION id S3 GOTO ( S2 + * ) # E 1 S4 S5 acc S3 r4 S3 S3 S2 r4 S2 S2 6 r4 r4 r4 r4 r4 7 8 S4 r1/S4 r2/S4 r3 S5 r1/S5 r2/S5 r3 S9 r1 r2 r3 r1 r2 r3 r1 r2 r3 r1 r2 r3 由于识别文法活前缀的DFSA中，状态I7和I8都存在“移进-归约”冲突，同时， FOLLOW(E)={#，)，+，*}

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

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

文法无冲突的LR分析表

状态 0 1 2 3 ACTION id S3 GOTO ( S2 + * ) # E 1 S4 S5 acc S3 S2 6 r4 r4 r4 r4 4 5 6 7 8 9 S3 S3 S2 S2 r4 7 8 S4 r1 r2 r3 S5 S5 r2 r3 S9 r1 r2 r3 r1 r2 r3

本文来源：https://www.bwwdw.com/article/ci7d.html