LR分析法浅理解

LR分析法是自下而上的分析，从句子开始，向上归约，归约到文法的开始符号。LR(0)分析法局限很大，但是建立其他分析表的基础。

相比LL分析法，LR分析增加了状态栈，LL分析程序每步动作由栈顶元素$X$和输入$a$决定，而后者将对栈顶元素的考量转化为对状态的考量。

LR(0)分析法

点在产生式右部的中间实际代表部分匹配，点在最后代表已经匹配了，可以用该产生式进行归约。

如果进行归约，则状态栈需要弹出产生式右部长度个数量的状态，相应地这些状态之间的连接弧上对应的字符和输入状态匹配了。

拓广文法，简化程序的逻辑，无需对接收项目特殊处理。
闭包求取，这个过程产生的新项目数不会超过产生式的个数，而且往往遵循一个固定的模式，这里可以用新符号简化替代由某个非终结符号带来的项目集合。

LR(0)分析表的构造，根据Go，填写Action的sis_isi​和Goto，之后结合每个状态中的归约项目，填写rkr_krk​。

SLR

相比于LR(0)分析法，填归约项目时考虑$a\in Follow(A)$，利用Follow集合向后看一个符号，即通过该产生式归约得到A，必须保证a会在A之后出现，否则a无法匹配！从这里也可以看到LR(0)中有些归约项目不仅会冲突，还会导致错误。
SLR分析表相比LR(0)分析表减少了一些错误项。

LR(1)分析法

实际上，并不是a出现在Follow集合中就可以用该产生式归约，还需要在一定条件下，因而在构建项目时加入对搜索符号的考量，考虑一个搜索符则是LR(1)分析法。

LR(1)项目有一个搜索符，$First(\beta a)$考量了什么情况（输入符号是什么，这些符号一定在$Follow(B)$集合中出现）下可以使用该产生式进行归约。这里可以$\beta =ϵ$，所以是求$First(\beta a)$。

LR(1)分析表相比SLR分析表又减少了一些错误的归约项。

LR(1)分析表仍可能存在移进-归约冲突，因为文法本身是二义文法。这时可通过运算符的运算次序 or 约定，决定归约 or 移进。

这里状态8，输入字符e时产生移进-归约冲突，r3r_3r3​代表可以用$S⟶iS$，这意味着此时栈顶为$iS$，根据约定，$else$与最近的$if$结合，比如$iiSeS$，应用$i|iSeS$的方式“断句”，所以输入$e$是不应归约前面的$iS$，而是等待到最后一起归约$iSeS$。

reference
山东大学编译原理郑艳伟老师ppt

smoking info