LR 分析

LR 分析从左向右读取 token，并通过移进和归约构造最右推导的逆过程。它先积累已经看到的结构，再决定这些符号属于哪个产生式。与朴素递归下降不同，确定性 LR 能直接处理许多左递归文法。

运行时通常只是状态栈加查表循环；复杂的部分在于生成表、理解冲突以及设计语义动作。小文法可以手工构造，工程中通常由工具生成。

移进、归约与状态栈

以 E → E + n | n 和输入 n + n 为例：先移进 n，再把它归约为 E；随后移进加号和第二个 n，最后将 E + n 归约为 E。归约时可同时构造 AST 节点。

若分别维护状态栈与语义值栈，归约长度为 r 的右部就各弹出 r 项，状态栈底部还保留起始状态；若把状态与文法符号交错存储，弹出数量的说法会不同。空产生式弹出 0 项，但仍要通过 GOTO 进入归约后的状态。

项目：点标识一条产生式识别到了哪里

项目 E → E · + n 表示已识别一个 E，接下来可以识别加号与 n；E → E + n · 表示右部已经完整，可考虑归约。

一个状态往往包含多个项目，代表当前前缀可能处在多种语法上下文。它记录的是可行前缀信息，并不是只对应一个源码 token。

对 LR(0) 项目集合，closure 遇到 A → α · B β 时，把 B 的所有产生式 B → · γ 加入，并递归扩展。goto(I, X) 先将 I 中点前为 X 的项目向右移动一位，再取闭包。不断对新集合执行 goto，可构造项目集自动机。

终结符上的边形成移进动作，非终结符上的边形成 GOTO。至于完成项目在哪些前瞻上归约，正是 LR 各变体的关键区别。

五个状态跑完 n+n：归约以后先回到旧状态，再查 GOTO

为开头文法编号：规则 1 为 E→E+n，规则 2 为 E→n。采用以下状态编号，它们是本例手工指定的，不要求与生成器输出一致。

状态 0 的闭包含 E→·E+n 与 E→·n；识别 E 后到状态 1，期待加号或结束；识别 n 后到状态 2，可以归约 E→n。状态 3 表示 E→E+·n，状态 4 则完成 E→E+n·。FOLLOW(E)={+, $}，因此在这两个前瞻上填写相应归约。

ACTION = {
    (0, "n"): ("shift", 2), (1, "+"): ("shift", 3),
    (1, "$"): ("accept", 0), (2, "+"): ("reduce", 2),
    (2, "$"): ("reduce", 2), (3, "n"): ("shift", 4),
    (4, "+"): ("reduce", 1), (4, "$"): ("reduce", 1),
}
GOTO = {(0, "E"): 1}


def parse(tokens):
    if any(t not in ("n", "+") for t in tokens):
        raise SyntaxError("invalid token")
    source = list(tokens) + ["$"]
    states, values, pos, trace = [0], [], 0, []
    while True:
        action = ACTION.get((states[-1], source[pos]))
        if action is None:
            raise SyntaxError(f"unexpected {source[pos]} at token {pos}")
        kind, number = action
        trace.append((tuple(states), pos, kind))
        if kind == "shift":
            states.append(number)
            values.append(("n",) if source[pos] == "n" else "+")
            pos += 1
        elif kind == "reduce":
            length = 3 if number == 1 else 1
            rhs = values[-length:]
            value = ("+", rhs[0], rhs[2]) if number == 1 else rhs[0]
            del values[-length:]
            del states[-length:]
            states.append(GOTO[(states[-1], "E")])
            values.append(value)
        else:
            assert len(values) == 1 and pos == len(tokens)
            return values[0], trace


node, trace = parse(["n", "+", "n"])
assert node == ("+", ("n",), ("n",))
assert [p for stack, p, action in trace] == [0, 1, 1, 2, 3, 3]
assert parse(["n", "+", "n", "+", "n"])[0] == ("+", node, ("n",))
assert parse(["n"])[0] == ("n",)
for tokens in ([], ["+", "n"], ["n", "n"], ["n", "+"], ["n", "$"]):
    try:
        parse(tokens)
    except SyntaxError:
        pass
    else:
        raise AssertionError("invalid input accepted")

读完第二个 n 后栈为 [0,1,3,4]，归约长度 3 弹回 [0]，再查 GOTO(0,E)=1。此时前瞻仍是 $，下一步才接受。不能按归约前的栈顶 4 查 GOTO，也不能因为执行了归约就顺手消费 $。

本例没有空规则，故代码的 length 总大于零。扩展到 ε 时必须专门处理零长度；Python 的 del stack[-0:] 等同于清空整栈，不是“不弹出任何项”。这正是将算法说明直接照抄成切片代码时容易遗漏的边界。

归约改变了栈，前瞻为什么没有前进？

观察一次归约时，应同时保留弹栈前和弹栈后的状态。图中的前瞻有自己的位置，只有 shift 才移动它；reduce 则先移除右部，再用留下的栈顶查 GOTO。你可以直接选中任何动作，也可播放整段栈变化。无效输入同样走真实查表流程，在没有表项的位置停止，不会为了演示完整而跳过错误。

SLR、LR(1) 与 LALR 保留多少上下文

LR(1) 项目 [A → α · B β, a] 的闭包，对 B 的产生式使用 FIRST(βa) 中的终结符作为前瞻。a 表示 A 完成后允许跟随什么，不能简单理解成点后立即要读的字符。

规范 LR(1) 比 LALR(1) 能处理更多文法，但仍不是全部上下文无关文法。歧义文法无法在没有消歧规则的情况下由确定性 LR 表给出唯一分析。

一个 LR(1) 但非 LALR(1) 的例子

S → a A d | b A e | a B e | b B d
A → c
B → c

该文法只生成 acd、bce、ace、bcd 四个串，各有唯一推导。读完 ac 时，后接 d 应把 c 归约成 A，后接 e 则归约成 B；读完 bc 时恰好相反。

这说明冲突可能来自表构造对上下文的压缩，⁠看到 reduce/reduce 冲突不能立即断言原文法有歧义⁠。SLR 的全局 FOLLOW 也会产生类似的精度问题。Bison 手册专门讨论了这种 LALR 限制造成的冲突及采用 IELR 或规范 LR 的办法。Mysterious Conflicts

用生成器区分“文法冲突”与“合并造成的冲突”

将上面的四串文法写成 conflict.y，字符终结符用单引号：

%start S
%%
S: 'a' A 'd' | 'b' A 'e' | 'a' B 'e' | 'b' B 'd';
A: 'c';
B: 'c';
%%

bison -Dlr.type=lalr --report=states,lookaheads -o lalr.c conflict.y
bison -Dlr.type=canonical-lr --report=states,lookaheads -o canonical.c conflict.y

这一步只生成表和报告，不需要 lexer，也还不是可运行程序。LALR 应出现两个 reduce/reduce 冲突，规范 LR 则能保留 ac 与 bc 后的不同上下文而无这类冲突。检查报告时定位完成项目 A→c· 与 B→c· 的前瞻，别只比较状态总数。

若继续使用有冲突的 LALR 默认选择，某些串可能走错归约；因此“工具仍生成了 C 文件”不等于语言已被正确实现。工程上应明确选择合适构造方法或重写文法，而不是忽略警告。Bison 手册源码中的算法说明

合并状态时，丢掉了哪一项对应关系？

合并前，两条来源分别保存“前缀、完成项目、允许前瞻”的对应关系。合并后 A 与 B 各自得到前瞻并集，却不再知道 d 是从哪条前缀带来的。下面始终保留原始两行，便于对照压缩丢失了什么。四个输入串在原文法中仍各有唯一推导，表的冲突不能替代对歧义的证明。

区分两类冲突与解决依据

shift/reduce 表示同一状态与前瞻下，既能移进又能归约。例如 E → E + E | E * E | n 没有表达优先级，n + n * n 就有不同树形。可以重写分层文法，也可用工具的优先级、结合性声明表达语言规则。

reduce/reduce 表示同一位置有多个候选归约。它可能是真歧义，也可能是上述上下文合并结果。应查看项目、前瞻、最短触发输入和反例，而不是单纯压掉警告。

优先级声明是语义选择，不是对任意冲突的正确性证明。尤其是两个归约执行不同语义动作时，默认选择某条规则可能改变 AST 或副作用。

Bison 与 LALRPOP：名字不等于算法

Bison 支持 LALR、IELR、规范 LR 和 GLR 等配置。LALRPOP 虽然名字含 LALR，项目说明中的默认算法是 LR(1)。不能把所有工具统一写成“默认 LALR”，也不能给规范 LR 与 LALR 的状态数量规定一个固定倍率。Bison 文法与分析能力、LALRPOP 项目说明

GLR 可在冲突点保留多个分析分支，之后淘汰或合并，但歧义语义仍要定义，最坏成本也不同于确定性 LR。延迟语义动作、共享树表示和错误处理都需要额外设计。

错误恢复：error 是特殊机制

Bison 中可以写这样的恢复产生式：

statement: error ';' { yyerrok; };

error 是 parser 的特殊符号，不是 lexer 返回的“任意字符”规则。恢复时，parser 可以弹栈直到某个状态能移进 error，然后视需要丢弃输入以找到可继续的 token。同步到分号只是该规则提供的出口，不是所有错误都会自然停在分号。

被丢弃符号的资源需要正确释放；恢复后的语义值也应有明确表示，避免后续阶段把错误结构当正常节点。某些恢复会暂时抑制级联诊断，不能因此把“解析器返回”当作源码完全正确。Bison 错误恢复

工程判断

确定性 LR 的查表过程对输入长度通常是线性的，前提包括固定文法、无循环空归约以及受控的语义动作；构造表和错误恢复成本另算。增量编辑支持也依赖树结构、重用策略与词法上下文，不能仅凭 LL/LR 标签判断。

理解冲突时，先还原“已读前缀、当前项目、一个前瞻、候选动作”，再判断是语言规则、文法表达还是算法精度问题。继续阅读 AST 设计与错误恢复。

Keywords: LR, item, closure, goto, shift reduce, SLR, LALR, canonical LR, IELR, GLR, lookahead, conflict, Bison, LALRPOP