第六七章作业与习题参考答案

第七章 LR分析法

第1题已知文法

A→aAd|aAb|ε

判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。

文法：A→aAd|aAb|ε

拓广文法为G′，增加产生式S′→A

若产生式排序为：

0S' →A

1 A →aAd

2 A →aAb

3 A →ε

由产生式知：

First (S' ) = {ε,a}

First (A ) = {ε,a}

Follow(S' ) = {#}

Follow(A ) = {d,b,#}

G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

在I0中：

A →.aAd和A →.aAb为移进项目，A →.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)

文法。

在I0、I2中：

Follow(A) ∩{a}= {d，b，#} ∩{a}=

所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。

构造的SLR(1)分析表如下：

题目1的SLR(1)分析表

ab#的分析过程

题目1对输入串

第2题若有定义二进制数的文法如下：

S→L.L|L

L→LB|B

B→0|1

(1) 试为该文法构造LR分析表，并说明属哪类LR分析表。

(2) 给出输入串101.110的分析过程。

解：文法：

S→L.L|L

L→LB|B

B→0|1

拓广文法为G′，增加产生式S′→S

若产生式排序为：

0 S' →S

1 S →L.L

2 S →L

3 L →LB

4 L →B

5 B →0

6 B →1

由产生式知：

First (S' ) = {0,1}

First (S ) = {0,1}

First (L ) = {0,1}

First (B ) = {0,1}

Follow(S' ) = {#}

Follow(S ) = {#}

Follow(L ) = {.,0,1,#}

Follow(B ) = {.,0,1,#}

G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

在I2中：

B →.0和B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8中：

Follow(s) ∩{0，1}= { #} ∩{0，1}=

所以在I2、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。

构造的SLR(1)分析表如下：

题目2的SLR(1)分析表

题目2对输入串101.110#的分析过程

分析成功，说明输入串101.110是题目2文法的句子。

3．考虑文法：S→AS|b A→SA|a

(1) 列出该文法所有的LR（0）项目。

（2）按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。

（3）此文法是SLR（1）的吗？，若是，构造他的SLR分析表

（4）这个文法是LALR或LR（1）的吗？

(1)构造增广文法，S’→S

文法的LR(0)项目有：

1. S’→.S

2. S’→S.

3. S→.AS

4. S→A.S

5. S→AS.

6. S→.b

7. S→b.

8. A→.SA

9. A→S.A 10. A→SA. 11. A→.a 12. A→a.

（2）所产生的NFA略。

由规则构造所需的DFA:

则LR(0)项目集规范族为：

C＝｛I0,I1,I2,I3,I4,I5,I6,I7｝

（3）可以看到I1,I6,I7存在着移进－归约的冲突。

冲突是不能用SLR(1)的方法来解决。比如I6:

对于状态S→AS. 和S→.b

Follow(S)={#,a,b}与{b}相交不为空。

所以以上文法不是SLR(1)文法。

（4）为验证该文法是否为LALR或LR(1)的，构造LR(1)项目集。

对于I5,产生了移进－归约矛盾，所以这个文法不是LR(1)文法。于是也不是LALR文法。

文法：

S→UTa|Tb

T→S|Sc|d

U→US|e

拓广文法为G'，增加产生式S'→S

若产生式排序为：

0 S' →S

1 S →UTa

2 S →Tb

3 T →S

4 T →Sc

5 T →d

6 U →US

7 U →e

由产生式知：

First (S' ) = {d,e}

First (S ) = {d,e}

First (U ) = {e}

First (T ) = {d,e}

Follow(S' ) = {#}

Follow(S ) = {a,b,c,d,e,#}

Follow(U ) = {d,e}

Follow(T ) = {a,b}

G′的LR(0)项目集族及识别活前缀的DFA如下图所示：

在I1中：

S' →S.为接受项目，T →S. 为归约项目，T →S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文

法不是LR(0)文法。

在I1中：

Follow(S') ∩ Follow(T)= { #} ∩{a ，b}=

Follow(T) ∩{ c}= { a ，b} ∩{c}=

在I8中：

Follow(U) ∩ Follow(T) ∩{ c}={d,e}∩{ a ，b} ∩{c}=

所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G 是SLR(1)文法。

构造的SLR(1)分析表如下：

题目3的SLR(1)分析表

第8题

文法：S A#A→BaBb|DbDa B→εD→ε

证明该文法是LR(1)但不是SLR(1)。

解：若产生式排序为：

0 S'→A# 1 A →BaBb 2 A →DbDa 3 B →ε 4 D →ε

由产生式知：

First (S' ) = {a,b}

First (A ) = {a,b}

First (B ) = {ε}

First (D ) = {ε}

Follow(S' ) = {#}

Follow(A ) = {#}

Follow(B ) = {a,b}

Follow(D ) = {a,b}

G′的LR(1)项目集族及识别活前缀的DFA如下图所示：

在I0中：

B →.,a和T →.，b为归约项目，但它们的搜索符不同，若当前输入符为a时用产生式B →ε归约，为b时用产生式D →ε归约，所以该文法是LR(1)文法。

若不看搜索符，在I0中项目B →.和T →.为归约-归约冲突，而

Follow(B ) ∩Follow(D ) = {a,b} ∩{a,b}≠，冲突不能用Follow集解决，所以该文法不是SLR(1)文法。

构造的LR(1)分析表如下：

题目4的LR(1)分析表

10．判断下列各题所示文法是否为LR类文法，若是请说明是LR（0）、SLR（1）、LALR（1）或LR（1）的哪一种，并构造相应分析表

（１）S→AB A→aBa|εB→bAb|ε

（3）S→aAd|eBd|aBr|eAr A→a B→a

(5) A→aB|εB→Ab|a

(6) S→(SR|a R→.SR|)

（1）解：对于该文法构造LR(0)项目规范族：

I0: S’→.S I1: S’→S. I3: A→a.Ba I5: B→b.Ab I6: A→aB.a S→.AB I2: S→A.B B→.bAb A→.aBa I7: A→aBa.

A→.aBa B→.bAb B→. A→. I8: B→bA.b

A->. B→. I4: S→AB. I9: B→bAb.

可见存在着移进－归约冲突，这个文法不是LR(0)文法。考虑用SLR(1)来解决问题：构造

（3）解：先构造该文法的LR(0)项目集规范族：

I0: S’→.S I1: S’→S. I3: S→e.Bd I5: S→aB.r I9: S→aAd.

S→.Ad I2: S→a.Ad B→.a I6: A→a. I10:S→aBr.

S→.eBd S→a.Br S→e.Ar B→a. I11:S→eBd.

S→.aBr A→.a A→.a I7: S→eB.d I12:S→eAr.

S→.eAr B→.a I4: S→aA.d I8: S→eA.r

该文法存在着归约-归约冲突，所以不是LR（0）文法。

对于状态I6: A→a.

B→a.

Follow(A)={dr} Follow(B)={dr}

两个集合相交不为空，所以该文法也不是SLR(1)文法。

构造该文法的LR(1)文法可得该文法是LR(1)的。

I0: S’→S,# I2: S→a.Ad,# I4: S→aA.d,# I10: S→aAd.,#

S→.aAd,# S→a.Br,# I5: S→aB.r,# I11: S→aBr.,#

S→.eBd,# A→.a,d I6: A→a.,d I12: S→eBd.,#

S→.aBr,# B→.a,r B→b.,r I13: S→eAr.,#

S→.eAr,# I3: S→e.Bd,# I7: S→eB.d,#

I1: S’→S.,# S→e.Ar, # I8: S→eA.r,#

B→.a,d I9: B→a.,d

A→.a,r A→a.,r

构造LR(1)分析表（略）。

（5）解：构造LR(0)的分析表：

I0: S→.A I3: S->aB. I6: B->AB.

A→.aB I4: B->A.b

A→ . I5: B->a.

I1: S->A. A->a.B

I2: S->a.B B->.Ab

B->.Ab B->.a

B->.a A->.aB

A->.aB A->.

A->.

可以看到存在着移进－归约的冲突，不是LR(0)文法。

在I0中Follow(A)与{ｂ}相交不为空。所以也不为SLR(1)文法。

构造该文法的LR(1)项目集规范族：

I0: S->.A,# I4: B->A.b,# I9: B->a.,b

A->.aB,# I5: B->a.,# A->a.B,b

A->.,# A->a.B,b B->.Ab,b

I1: S->A.,# B->.Ab,b B->.a,b

I2: A->a.B,# B->.a,b A->.aB,b

B->.Ab,#, B->.aB,b A->.,b

B->.a,# A->.aB,b I10:B->AB.,b

A->.aB,b I6: B->Ab.,#

A->.,b I7: A->aB.,b

I3: A->aB.,# I8: B->A.b,b

其中存在冲突，所以文法也不是LR(1)文法。

（6）解：将文法拓广后得：

(0) S’→ S

(1) S→(SR

(2) S→ a

(3) R→.SR

(4) R→)

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

一个文法是LR(0)文法一定也是SLR(1)文法，也是LR(1)文法。但反之则不一定成立。

I0~~I9无冲突项目，所以此文法是LR（0）文法。

构造其LR（1）的DFA（构造过程中，在建立好初态集后，立即产生所有新状态的核集合，然后再逐步扩充）：

LALR(1)项目集规范族：

同心集合并后无冲突，其项目集的个数与LR（0）相同，此文法是LALR（1）文法。

11. 设文法G[S]为：S→AS|ε A→aA|b

(1) 证明G[S]是LR(1)文法

(2) 构造出它的LR(1)分析表

(3) 给出输入符号串abab#的分析过程

一个文法不是SLR(1)时，不能证明它是LR(1)的

解：将文法改写为拓广文法：

(0) S’→S (1) S→AS (2) S→ε (3) A→aA (4) A→b

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

对abab#的分析过程：

第15题：已知文法为： S→a| |(T) T→T,S|S

(1) 构造它的LR(0)、LALR（1），LR（1）分析表

（2）给出对输入符号长(a#和(a,a#的分析过程

（3）说明（1）中三种分析表发现错误的时刻和输入串的出错位置有何区别。

解：构造该文法的LR(0)项目集规范集：

I0: S’→.S I2: S’→a. I5: S→(T.) I9: T→T,S.

S→.a I3: S→∧. T→T.,S

S→.∧I4: S→(.T) I6: T→S.

S→.(T) T→.T,S I7: S→(T).

I1: S’→S. T→.S I8: T→T,.S

S→.a S→.a

S→.∧S→.∧

S→.(T) S→(T)

构造

构造LR(1)规范集族：

I0: S’→.S，# I2: S’→a.，# I5: S→(T.)，# I9: T→T,S.,) S→.a，# I3: S→∧.，# T→T.,S,) I10:S->a.,)

S→.∧，# I4: S→(.T)，# I6: T→S.,) I11:S->∧.,)

S→.(T)，# T→.T,S，）I7: S→(T).,# I12:S->(.T),) I1: S’→S.，# T→.S，）I8: T→T,.S,) T->.T,S,)

S→.a，）S→.a,) T->.S,)

S→.∧，）S→.∧,) S->.a,)

S→.(T)，）S→(T),) S->.∧, I13:S->(T.),) I14:S->(T).,) S->.(T),) T->T.,S,)

构造LR(1)分析表：

和I12、I5和I13、I7和

分析对输入符号为（a#和(a,a#的LR(0),LR(1),LALR(1)分析过程：

（a#的LR(0)分析过程：

(a,a#的LR(0) 分析过程：

（

（3）LR(1)分析表发现问题最早，LALR次之，LR(0)最慢，发现位置相同。