5 6 r1 r3 r1 14． 某语言的文法G为：E → aTd|ε T → Eb|a

证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。 答：

拓广文法G'，增加产生式S'→E 在项目集I0中： 有移进项目E →·aTd 和归约项目E→·

存在移进-归约冲突，所以G不是LR(0)文法。 若产生式排序为： (0) S′→E (1) E → aTd (2) E →ε (3) T → Eb (4) T → a

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

.

由产生式知： Follow(E)={# ，b} Follow(T)= {d} 在I0，I2中:

Follow(E) ∩{a}={# ，b} ∩{a}= 在I5中:

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

Follow(T) ∩ Follow(E) = {d} ∩{# ，b}=

所以在I0， I2， I5中的移进-归约和归约-归约冲突可以由Follow集解决,所以G′是SLR(1)文法。 构造的SLR(1)分析表如下表：

ACTION name a 0 1 2 3 S2 S5 b r2 r2 d S6 # r2 acc r2 E 1 4 T 3 GOTO 4 5 6 7 S5 S7 r2 r1 r4 r3 r2 r1 4 3 15． 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为：S →BD|D B →aD|b D →B

I0:

答： I0：

16． 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为：S →D;D|D D →DB|B B →a|b

I0:

答：

I0:

17． 给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。 G[S]为： S →S;V|V V →VaA|A A →b(S)| ε I0:

答： I0:

18． 文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。 G[M]: 1) M →VbA

2) V →d 3) V →ε

4) A →a 5) A →Aba

6) A →ε

ACTION name b d a # M A V GOTO 0 1 2 3 4 5 6 7 8 答：

r3 S4 r2 r6 r4 S7 r5 S3 S5 S8 acc r6 r4 r1 r5 1 6 2 对串dbba#的分析过程如下表

步骤 1 2 3 4 5 6 7 8 9 状态栈 0 03 02 024 0246 02467 024678 0246 01 文法符号栈 # #d #V #Vb #VbA #VbAb #VbAba #VbA #M 剩余输入符号 dbba# bba# bba# ba# ba# a# # # # 移进 用V →d归约 移进 用A →ε归约 移进 移进 用A →Aba 归约 用M →VbA 归约 接受 动作 19． 文法G[S]及其LR分析表如下，请给出对输入串da;aoa#的分析过程。

G[S]: 0) S′→S

1) S→dSoS

2) S →dS

3) S →S;S

4) S →a

name ACTION GOTO