区分LR(0),SLR(1),LR(1)和LALR(1)

目录

对于LR(0)文法：

对于SLR(1)文法：

对于LR(0)和SLR(1)文法：

对于LR(1)和SLR(1)文法：

对于LALR(1)文法：

例题1：

例题2：

例题3：

例题4：

---

这几个文法大致的步骤都相同，只是细节不同：

拓广文法---->项目集规范族---->构造分析表

首先区分几个项目

为什么要进行拓广文法呢？

文法是自底向上，归约时，b和c是归约哪一个S，编译器是不能区分的，那么拓广文法通过S'--->S

区分了两个S

对于LR(0)文法：

对于SLR(1)文法：

若冲突项目存在，那么就无法构表，继续判断是不是SLR（1）文法，如果根据Follow集判断交集为空，那么就是SLR(1)文法，如果不为空，那么就无法构表，既不是LR（0）文法，也不是SLR（1）文法。

对于LR(0)和SLR(1)文法：

如果文法中没有冲突项目，他是LR(0)文法，也是SLR(1)文法，也就是SLR(1)中包含不冲突的项目，也包含符合条件的冲突项目，但是如果该冲突项目也不包含在SLR（1）中，那么既不是LR(0)文法，也不是SLR(1)文法。

所以，SLR(1)文法的目的就是减少冲突的产生

对于LR(1)和SLR(1)文法：

若存在冲突项目：

LR(1)文法根据向前搜索符来判断：如果为空，那么就是LR(1)文法

SLR(1)文法是根据Follow集判断的：如果为空，那么就是SLR（1）文法

LR（1）的使用场景：

若是冲突项目，并且也不满足SLR(1)的条件，那么就要回退，重新构建带向前搜索符号的项目，判断是否为LR(1)文法。

对于LALR(1)文法：

任何一个 SLR(1)文法一定是一个 LALR(1) 文法,即：

LALR(1)SLR(1)

LALR（1）文法与LR（1）文法的区别在于，LALR（1）文法合并了同心集

例题1：

对于I2，S->L?=R和R-->L?产生了（移进--归约冲突）

继续求Follow集

将移进项目的“点”后面的终结符和规约项目的Follow集进行交集，判断是否为空

通过构造向前搜索符号继续判断，在I2中存在（移进---归约）冲突：

通过移进的“点”后面的终结符和归约项目“逗号”后面的向前搜索符号的交集判断是否为空

{=}{#}=，所以是LR（1）文法

例题2：

① 整行填上r，就是LR(0)

② 若同样的表中，不同的行出现了同样的项目，那么就是LR(1)

③ 不同的行中是不同的项目，就是SLR（1）

例题3：

?

例题4：