6.3 SLR、LALR 与 LR(1)

LR 是一个家族：机器都使用移进/归约（shift/reduce）栈，但允许完成项（completed item）归约时保留的上下文不同。更多上下文接受更多文法（grammar），也带来更多状态（state）或构造成本。

下面的对照表先给出全貌：

记住一条主线：从上到下，保留的上下文越来越精细，接受的文法越来越多，代价是状态越来越多或构造越来越复杂。

SLR 与 LR(1)

LR(0) 的 A -> alpha . 会在所有向前看符号上归约，常过于粗糙。SLR(1) 使用 FOLLOW(A) 限制归约；它便宜但 FOLLOW 是全局集合，不能区分 A 出现在不同局部上下文的情形。一个文法可能 LR(1) 却不是 SLR。

规范 LR(1) 项写成 [A -> alpha . beta, a]。闭包中 [A -> alpha . B beta, a] 要为 FIRST(beta a) 中每个词法单元加入 B 的项；完成 B 后只在自身向前看符号上归约。这份局部上下文让它最强，但状态图可能很大。

LALR(1) 合并 LR(0) 核心相同的 LR(1) 状态，并合并向前看符号。它通常接近 SLR 的表大小且足够实用；但合并可能制造原规范 LR(1) 没有的归约-归约冲突（reduce/reduce conflict）。报告冲突时应说明它来自文法本身还是合并。

为什么全局 FOLLOW 太宽

若 A 在一处后接 c、另一处后接 d，则 FOLLOW(A)={c,d}。某个具体状态也许已知只处于第一处，SLR 仍会允许在 d 上归约，因为它只看全局 FOLLOW；这可能撞上本应移进的动作。LR(1) 把局部事实写成 [A -> alpha ., c]，该状态只在 c 上归约。

LALR 合并核心相同的规范状态，例如向前看符号 {c} 与 {d} 合成 {c,d}。当这不会使竞争完成项重叠时安全；否则可能制造新的归约-归约冲突。合并不是魔法压缩，必须看具体上下文。

选择提示

• SLR 适合教学和快速基线。

• LALR 适合围绕它建立工具生态的项目。

• 真实文法有 LALR 伪冲突时考虑规范 LR(1)/IELR。

• 看冲突状态/见证，不要只看表大小。