LALR 状态合并

规范LR(1)可能为同一段识别进度保存多份状态，只因它们分别处于不同后续环境。合并后，解析器仍知道“识别到哪里”，却忘记“从哪类前缀环境来到这里”。许多文法不需要后一份区别，因此压缩没有影响。

然而不同前缀可能交换两条归约的允许token。分别看每个状态都能作决定，合并后却把两份名单交叉叠在一起；被忘掉的正是选择归约所需的信息。

一个 LR(1) 却不是 LALR(1) 的文法 ​

取

语言恰含 acd、bce、ace、bcd 四个词。读过前缀 ac 时，规范LR(1)状态为

此时看见 $d$ 就归约为 $A$，看见 $e$ 就归约为 $B$。读过 bc 时则来到

二者的LR(0)核心都为 $\{A\to c\cdot ,B\to c\cdot \}$，所以LALR会合并。合并后，两个完整项目都带 $\{d,e\}$，在两个token上都发生归约/归约冲突：

这份文法的规范LR(1)自动机有14状态，按核心合并后有13状态；唯一被合并的一对便是上述两态。节省一个状态，却恰好丢掉了重要区别。

若在冲突时固定优先归约 $A\to c$，acd 与 bce 能继续，ace 与 bcd 则会在随后期待的终结符上失败；固定优先 $B$ 会反过来丢掉另外两词。因此这不是不影响语言的小消歧设置，更不是原文法本来有两棵树导致的问题。

为什么新冲突只能是归约/归约 ​

假设原规范LR(1)表无冲突。若合并状态在 token $a$ 上同时移进和归约，那么移进意味着其核心含 $C\to \gamma \cdot a\delta$。同组每个状态都有这个核心项目，因此每个原状态都能在 $a$ 上移进。

另一方面，合并后的归约 $[A\to \alpha \cdot ,a]$ 必来自组内某个原状态。那个原状态就已经同时含移进与该归约，与无冲突假设矛盾。因此合并不会新造移进/归约冲突。两条归约却可能分别来自不同原状态，正如上例，所以会新造归约/归约冲突。

这个论证只讨论从无冲突规范LR(1)表合并的情况；若原表本来有移进/归约冲突，LALR当然不会凭这个定理把它自动消除。

LALR与DFA最小化不能互换。DFA最小化公理库有限自动机最小化Finite automaton minimization · DFA minimization删除不可达状态并按全部未来后缀的行为划分状态，构造识别同一语言的唯一最小 DFA。按未来输入的接受行为等价来合并；LALR按项目核心相同合并，可能失去确定解析能力。不能因为二者都减少状态，就把“最小化保持语言”的定理直接用于LALR表。

教学上先构造完整LR(1)表再合并最容易核查：保留分组映射，逐条合并向前看，再重建动作检查冲突。工程实现也可在LR(0)图上传播lookahead，避免先物化全部规范状态；这是计算同一类信息的更紧凑方法，不能在分析复杂度时把“已经建完巨大的LR(1)表”隐去。

若原表有 $q$ 个状态和 $m_1$ 条项目记录，按规范化核心排序或哈希可对记录作分组；随后遍历项目与边合并。具体成本随集合表示而定，至少需读取这些 $m_1$ 条记录。结果状态数不超过LR(0)可达状态数，固定文法的运行时仍为单栈线性解析。

单元任务：检查压缩是否丢了信息 ​

对上述四词文法，要求列出读过 ac 与 bc 的完整项目，构造合并行，并说明一个固定冲突优先级会丢掉哪些合法输入。解答就是表中的两行交换关系：优先 $A$ 丢掉 ace,bcd，优先 $B$ 丢掉 acd,bce。

验收必须把“合并前两态分别无冲突”“合并后只有一行”“每个合法词所需的归约”连起来。只报告状态数从14变13，无法说明压缩是否正确。若需要保留原文法与全部分析，继续使用规范LR(1)，或让GLR公理库广义 LR 与图结构栈Generalized LR parsing · GLR parsing以图结构栈共享冲突分支，并以打包森林保存多种语法树的LR泛化方法。显式保存冲突分支。