SLR
LR(1)
LALR(1)
一、引入：
自上而下分析：实现最右推导很困难
因此经常使用自下而上分析进行最右推导
二、概念
1、归约：最右推导的逆过程的一步
把句柄归约成非终结符代表了某一步最右推导的逆过程
当确定句柄出现在栈顶：1、确定句柄的位置（多长）2、使用哪个非终结符归约
2、句柄：句型中与一个产生式右部匹配的字符串
（1）句柄的右边仅含有终结符
（2）如果文法二义，那么句柄可能不唯一
（3）要判断是否是句柄，可以在按照句柄归约之后的文法是否是文法的右句型(所有能够在最右推导中出现的句型，称为右句型）
（4）句柄是句型的一个子串
三、分析器
1、分析表：确定下一步的动作是移进还是归约，以及归约使用哪一个产生式
2、分析器的四种动作：移进，归约，接收，报错
四、冲突的产生
当出现句柄的时候，可以选择归约也可以选择继续移进
问题1：如何确定右句型中将要归约的子串
问题2：如何确定选择哪一个产生式
移进-归约冲突
归约-归约冲突
为解决冲突，使用LR分析器处理
五、LR(k)文法
1、定义
k是指决定分析动作的时候向前看的符号的个数
k = 1时可以省略，表示分析的时候只要往前看1个符号
注意LR分析方法是自下而上分析的方法
LR分析算法
格局：{栈的内容，尚未处理的输入}
状态
2、活前缀
右句型的前缀，该前缀不超过(<=)最右句柄的右端
活前缀的三种情况
1、活前缀包含句柄的所以符号，可以开始归约了
2、活前缀包含了句柄的部分符号，期待输入串中看到接下来的非终结符
3、活前缀不包含句柄的任何符号，
即已经出现的符号在文法的中接下来是非终结符
这是期待该非终结符推导的符号串出现在输入串中
LR分析器的核心工作就是
识别活前缀的DFA
基于DFA构建分析表
3、LR(0)项目集：LR(0)项目的集合
（1）LR(0)项目
加点产生式：注意ε的特殊性
点的左边：历史信息
点的右边：期望看到的信息
4、构建识别活前缀的DFA
（1）拓广文法：当且仅当分析器使用拓广归约时宣告成功
（2）构造LR(0)项目集规范族
要加入闭包
核心项目：除了非核心项目都是核心项目
非核心项目：对核心项目闭包获得的项目
六、SLR(1)
1、一般步骤：
拓广文法
构建识别活前缀的DFA
基于DFA构建分析表
2、有效项目
3、SLR的缺陷
可能会出现：移进-归约冲突和归约-归约冲突，出现了这些冲突的文法都不是SLR（1）的
原因是一个项目可能对好几个活前缀都是有效的
即一个项目可能有好几个有效项目
七、LR(1)文法（规范的LR文法）
1、和SLR(1)的区别是添加了向前搜索符，增强了描述能力
八、LALR（向前看的LR方法）（具有和SLR相同数目的状态）
有个结论是合并同心集不会产生新的移进-归约冲突，但是会产生新的归约-归约冲突，如果没产生冲突就是 LALR 文法，反之不是
只有当合并同心集产生了归约-归约冲突时才是LR(1)文法。
不会产生移进-归约冲突：是因为可能产生移进-归约的两项在合并前一定是在同一个集合的，而LR(1)文法是不会有冲突的，所以在合并前没有这样的冲突
会产生归约-归约冲突，如果两个不同的非终结符有相同的产生式，在合并的时候就会产生冲突