- 4.12 LR(1) 分析算法
- 4.12.1 SLR 分析算法的评价
- 4.12.2 SLR 分析算法的问题
- 4.12.3 SLR 算法的改进——LR(1)
- 4.12.4 LR(1) 示例
- 4.13 LALR(1) 分析算法
- 4.13.1 LR(1) 分析算法的评价
- 4.13.2 LR(1) 算法的变动——LALR(1)
- 4.13.3 示例
- 4.13.4 LALR(1) 分析算法的特点
- 优点：
- 有可能减少需要归约的情况
- 有可能去除需要移进-归约冲突
- 缺点：
- 仍然有冲突出现的可能
4.12.2 SLR 分析算法的问题
SLR 主要存在两个问题：
- 只是简单的考察下一个输入符号 y 是否∈FOLLOW(X)， 但 y∈FOLLOW(X) 只是进行归约的一个必要条件，而非充分条件
- 不是对 FOLLOW(X) 中的所有符号，都应该进行归约
对于上述情况，我们可以知道，I5 和 I7 发生了“移进—归约”冲突，而实际上却是：
对于 I5，只需要面对 d 时进行归约，c 应该移进。
对于 I7，只需要面对 c 时进行归约，d 应该移进。
4.12.3 SLR 算法的改进——LR(1) 在项目中加入超前扫描符号 / 向前搜索符 / 后继符 / 前看符号的信息。
（1）前看符号的引入
每个项目形式变为： [ X → α ∙ β , a ] [X\rightarrow \alpha\bullet\beta,\ a] [X→α∙β, a] 其中， a a a 是一个终结符集合（前看符号集合），为 FOLLOW(X) 的子集。但是能够精确表示产生式需要归约的情况。
也就是说，只在遇到属于集合 a a a 中的字符时进行归约，这里的集合 a a a 相当于 SLR 里面的 FOLLOW(X) 集合。
（2）闭包的变化
-
对于第一个产生式 S ′ → S # S'\rightarrow S\# S′→S#，对应的项目集为： [ S ′ → ∙ S , # ] [S'\rightarrow \bullet S,\ \#] [S′→∙S, #]
-
对项目 [ X → α ∙ Y β , a ] [X\rightarrow\alpha\bullet Y\beta,\ a] [X→α∙Yβ, a] 进行闭包计算时，改为添加以下式子： [ y → ∙ γ , b ] [y\rightarrow\bullet\gamma,\ b] [y→∙γ, b] 其中， b ∈ F I R S T _ S ( β a ) b\in FIRST\_S(\beta a) b∈FIRST_S(βa)。
-
其余的操作无变化
（1）例 1
上图中红色的项目集依照顺序依次闭包。其中，
- 第 2 行由第一行的闭包产生；
- 第 4/5 行由第 2 行的闭包产生；
- 第 6 行由第 3 行的闭包产生；
- 第 7/8 行由第 6 行的闭包产生。
之后第 7 行产生的闭包和第 6 行一模一样，因此不再闭包了。
最后将第 4/5 行和第 7/8 行合并，得到：
这就是根据 LR(1) 文法得到的第一个状态。
列出剩余的状态集：
如果除前看符号外，两个 LR(1) 项目集是相同的，则称这两个项目集是同心的。
（2）例 2
若状态集 Ii 中含有推出空串的产生式：（n 为文法行号） [ X → ∙ ε , a ] [X\rightarrow\bullet\varepsilon,\ a] [X→∙ε, a] 也需要在 ACTION[a] 表中填入对应的归约式：rn。
4.13 LALR(1) 分析算法 LALR：lookahead-LR。
4.13.1 LR(1) 分析算法的评价-
优点：对搜索符的计算方法比较确切，可以解决 SLR 方法解决不了的问题
-
缺点：但对同心集的分裂使状态数目剧烈增长，导致存储容量的急剧增加：
（1）变动
- 把 LR(1) 中类似的项目集（同心集）进行合并
- 同心集：具有相同核心的项目集，即第一部分一样
- 需要修改 ACTION 表和 GOTO 表，以反映合并的效果
- 若合并同心集后不产生新的冲突，则为 LALR(1) 项目集
（2）说明
- 同心集经转换函数所达的项目集仍为同心集，也合并
- 若文法是 LR(1) 文法，合并同心集后
- 若有冲突也是归约-归约冲突，不可能是移进—归约冲突（LR(1) 文法没有移进—归约冲突）
- 若有冲突，则不能称为是 LALR(1) 文法
- 合并同心集后，会推迟错误的发现
I3/I6、I4/I7、I8/I9 有相同的核，将其称为同心集。
（1）LR(1) 分析表
（2）LALR(1) 分析表
4.13.4 LALR(1) 分析算法的特点
- 形式上与 LR(1) 相同
- 大小上与 LR(0) / SLR 相当
- 分析能力介于 SLR 和 LR(1) 二者之间：
- SLR < LALR(1) < LR(1)
- 合并后的展望符集合仍为 FOLLOW 集的子集
