编译原理第四次作业

小组成员：王战海、吴建明、张泽华、赵方通

3.23 证明下面文法

S->Aa|bAc|Bc|bAa

A->d

B->d

是LR（1）文法，但不是LALR（1）文法。

证明：

拓广文法

S′->S

S->Aa|bAc|Bc|bAa

A->d

B->d

的LR（1）项目集的规范族如下图：

将项目集族I0编号有：

0 S′->·S，$

1 S->·Aa,$

2 S->·bAc,$

3 S->·BC,$

4 S->·bBa,$

5 A->·d,a

6->·d,c

则LR（1）的分析表如下：

假设他是LALR（1）文法，从LR（1）的项目族当中可以看出I5和I8是同心，合并同心后会得到LALR（1）的分析表如下：

从上表中很明晰的可以看出存在r5/r6、r6/r5归约和归约的冲突，故而它不是LALR（1）文法，所以它是LR（1）文法。