更强的LR分析方法SLR(1)与LR(1)

SLR(1)分析法

LR0文法比较简单，描述的语言也比较有限，如下面这个文法不属于LR0，先构造LR0项目集规范族可以看出。

注意 I1 I2 I9出现了移进和归约的冲突

消解移进归约冲突是有可能的，可以细分。

如，当前输入的单词不在要归约生成的A的FOLLOW集中，那不能采取归约动作。

如，当前单词是+时，那它不在S‘的FOLLOW集合中，不采用归约，而是采用移进。 相当于向后看了一个单词，所以是1不是0

SLR1冲突解决方法

将这个方法一般化后得到

称为 SLR(1)冲突解决方法

SLR分析表构建

文法拓广

1. 开始符号只有唯一产生式
2. G’只有唯一的接收状态
3. 文法开始符号不会出现在产生式右部

最重要的还是第三步——构造ACTION和GOTO表，和LR0分析表构造有差异。

主要注意第二步，如果状态集中存在归约项目，遇到该非终结符的FOLLOW集中的终结符时，进行归约（使用对应该归约项目的产生式）。

与LR0分析表的区别，LR0分析表的归约是不加区分的放在了Ik的所有列，而SLR1先要判断这一列对应的符号在非终结符的FOLLOW集中，减少了冲突

构建示例

对于之前的非LR(0)文法来说

当前已经拓广了文法以及构建了DFA。之后需要消解冲突。

注意，（待约项目的）非终结符FOLLOW集中不能有同一项目集中移进项目需要的符号，如下面两个FOLLOW集对于I1，S'的FOLLOW集没有出现+号(+号是归约时需要的符号)，对于I2，E的FOLLOW集中没有出现*号。

？FOLLOW集怎么求，还不够熟练

注意状态1的状态转换函数，分别检查了待约和移进项目，仅对于指定的符号进行状态转换。

状态2也是，如果采用的是之前LR0分析方法，*这一列会同时出现移进s7和归约r2冲突。

注意第三个状态，虽然只有一个待约项目，但是也进行了FOLLOW集的检测。

LR1分析法

SLR1分析法的局限性

SLR冲突消解方法还是存在一些问题。如在同一个项目集中，归约项目的非终结符的FOLLOW集和移进项目期待的下一个终结符（点后面的终结符）有交集。

但是实际上状态二位于分析栈栈顶，面临输入符号=时，也不能归约，因为所有的规范句型中，不存在R=为前缀的规范句型，只有以*R=为前缀的规范句型(在L0中)，之所以=能在R的FOLLOW集中，是因为R前面有*。

所以状态2处于栈顶时，面临输入串=是不能按照I2中的归约项目进行归约的。

FOLLOW集合计算得到的超前符号集合可能大于实际能够出现的超前符号集！！存在局限性 如该表中

*R后面才能加=号

所以我们需要更加精确的预测信息，不能只看FOLLOW集合，来判断下一步操作，所以需要LR1分析方法。

构造LR1分析表

LR1的项目

a1a2ak是终结符，称为向前搜索串（展望串)，每个状态除了LR(0)项目，还有和项目相关的展望信息。而不是用FOLLOW集合做展望。

展望串对归约项目具有指导意义。

如能否把α归约为A，还需要看后面的k个终结符。如果是SLR中，只需要后面的一个单词在FOLLOW集合中即可归约，这点它们是不同的。

对于移进项目，展望串没有直接意义，随着点向后移动，展望串最终传递到规约项目。

一般只使用k=1的情况

LR1有效项目

α和β都形成，即将归约的时候，面临的单词应该是a。

之所以是βa的FIRST集，因为β可能是空串。

LR1项目集规范族

通过计算有效项目，构造项目集规范族

第一个项目的展望串是#，因为希望归约到开始符时，所有的串都处理完了，面临句末符。

分析表构造

注意归约项目仅仅放在 a的那一列，（SLR1中放在FOLLOW集合中的列）

第四项指的是归约到A后，对应状态j

使用了更加精确的展望信息。

展望信息哪来的??

构造示例

I0中第三项展望串为a或b的原因，aB归约成B的时候，后面跟着的会是B（第二项），B的开头是a或者b。

注意I2中的展望串变了，因为后面没有东西了（这是第二个B）。

I3中a后面期望的是B，B的开头是a/b

另外注意I6，识别a后剩下的B是在末尾的B，所以展望串是#，因为后面不会再有一个额外的B，和I3不一样。

注意，移进项目的展望串传递到了后面的归约项目

分析示例

LR分析器，总是根据当前栈顶与当前单词查找分析表，只向前检查一个单词，所以称为LR1分析。