LR 与 LALR 解析：从理论到 yacc/bison

1965 年，Donald Knuth 在他那篇里程碑式的论文 “On the Translation of Languages from Left to Right” 中，提出了 LR(k) 解析的概念。这个算法从左到右扫描输入（Left-to-right），使用最右推导的逆过程（Rightmost derivation in reverse）进行归约，并向前看 k 个符号来决定下一步动作。

LR 解析的能力是惊人的：它能处理几乎所有编程语言的语法，而且解析过程是确定性的、线性时间的。唯一的问题是，完整的 LR(1) 解析表对于真实语言来说过于庞大。 1969 年，Frank DeRemer 提出了 LALR(1) —— 一种巧妙的近似方法，用远少于 LR(1) 的状态数，处理了实践中绝大多数文法。 yacc 和 bison 至今仍然使用 LALR(1) 作为默认算法。

本文将从上下文无关文法的基本概念出发，逐步构建 LR(0)、SLR(1)、LR(1)、LALR(1) 的完整理论体系，给出一个约 250 行的 C 语言 LALR(1) 解析器生成器实现，讨论 GLR 对二义性文法的处理，最后探讨 yacc/bison、tree-sitter、PostgreSQL 解析器等真实系统中的工程实践。

一、上下文无关文法回顾

1.1 文法的形式化定义

上下文无关文法（Context-Free Grammar, CFG）是一个四元组 G = (V, T, P, S)：

V：非终结符的有限集合
T：终结符的有限集合，且 V 与 T 不相交
P：产生式的有限集合，每条产生式形如 A -> alpha，其中 A 属于 V，alpha 属于 (V 并 T)*
S：开始符号，S 属于 V

一个经典的算术表达式文法：

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

这个文法将贯穿本文始终，作为我们的核心示例。

1.2 推导与解析树

最左推导（leftmost derivation）：每一步替换最左边的非终结符。 最右推导（rightmost derivation）：每一步替换最右边的非终结符。

对于输入 id + id * id，最右推导过程为：

E => E + T => E + T * F => E + T * id
  => E + F * id => E + id * id
  => T + id * id => F + id * id => id + id * id

LR 解析器执行的正是最右推导的逆过程：从输入串出发，逐步归约回开始符号。

1.3 增广文法

为了给解析器提供一个明确的”接受”条件，我们引入增广文法（augmented grammar）：添加新的开始符号 S’ 和产生式 S’ -> S。

S' -> E
E  -> E + T | T
T  -> T * F | F
F  -> ( E ) | id

当解析器归约到 S’ -> E 时，就表示成功接受了输入。

1.4 FIRST 集与 FOLLOW 集

LR 解析的各种变体都依赖于 FIRST 和 FOLLOW 集来解决冲突。

FIRST(alpha) 是 alpha 能推导出的所有串的首终结符集合。如果 alpha 能推导出空串，则 epsilon 也在 FIRST(alpha) 中。

FOLLOW(A) 是所有句型中紧跟在 A 后面的终结符集合。

对于上面的文法：

FIRST(E) = FIRST(T) = FIRST(F) = { (, id }
FOLLOW(E) = { +, ), $ }
FOLLOW(T) = { +, *, ), $ }
FOLLOW(F) = { +, *, ), $ }

FIRST 集的计算需要处理 epsilon 产生式的传播； FOLLOW 集的计算需要不动点迭代。这两个集合在 SLR(1) 中扮演关键角色。

二、自底向上解析：移进-归约

2.1 移进-归约解析器的基本结构

自底向上解析器（bottom-up parser）维护一个栈和一个输入缓冲区。它执行四种动作：

移进（shift）：将输入中的下一个终结符压入栈
归约（reduce）：将栈顶匹配某个产生式右部的符号弹出，压入左部的非终结符
接受（accept）：输入读完且栈中只剩开始符号时，解析成功
错误（error）：无法执行任何动作

2.2 一个完整的移进-归约过程

以输入 id + id * id $ 为例：

栈                       输入                 动作
-----------------------------------------------------------------
$                        id + id * id $       移进
$ id                     + id * id $          归约 F -> id
$ F                      + id * id $          归约 T -> F
$ T                      + id * id $          归约 E -> T
$ E                      + id * id $          移进
$ E +                    id * id $            移进
$ E + id                 * id $               归约 F -> id
$ E + F                  * id $               归约 T -> F
$ E + T                  * id $               移进
$ E + T *                id $                 移进
$ E + T * id             $                    归约 F -> id
$ E + T * F              $                    归约 T -> T * F
$ E + T                  $                    归约 E -> E + T
$ E                      $                    接受

注意解析器在看到 $ E + T 和下一个输入符号 * 时，选择了移进而不是归约 E -> E + T。这正是优先级和结合性在起作用。

2.3 句柄

句柄（handle）是栈中应当被归约的那部分子串—— 它对应最右句型中最左边的一个简单短语。

LR 解析的核心问题就是：如何高效地识别句柄？答案是使用有限自动机来跟踪栈的状态。

三、LR(0) 项与项集

3.1 LR(0) 项

LR(0) 项（LR(0) item）是一个产生式加上一个位置标记（点）：

A -> alpha . beta

点的左边（alpha）是已经在栈中的部分，右边（beta）是期望在输入中看到的部分。

对于产生式 E -> E + T，有四个 LR(0) 项：

E -> . E + T
E -> E . + T
E -> E + . T
E -> E + T .

最后一个项（点在最右边）称为归约项（reduce item），表示右部已经完全匹配，可以执行归约。

3.2 闭包运算

给定一个项集 I，其闭包 CLOSURE(I) 的计算规则如下：

I 中的所有项都在 CLOSURE(I) 中
如果 A -> alpha . B beta 在 CLOSURE(I) 中，且 B -> gamma 是一个产生式，则 B -> . gamma 也加入 CLOSURE(I)
重复步骤 2 直到不再有新项加入

直觉：如果解析器期望看到非终结符 B，那么它也需要准备好识别 B 的所有产生式。

3.3 GOTO 函数

GOTO(I, X) 定义了从项集 I 读入符号 X（终结符或非终结符）后转移到的项集：

GOTO(I, X) = CLOSURE({ A -> alpha X . beta | A -> alpha . X beta 属于 I })

3.4 构建 LR(0) 自动机

从初始项集 CLOSURE({S’ -> . S}) 出发，反复计算所有可能的 GOTO 转移，直到没有新的项集产生。

对于我们的表达式文法，LR(0) 自动机如下图所示：

初始状态 I0 的项集：

S' -> . E
E  -> . E + T
E  -> . T
T  -> . T * F
T  -> . F
F  -> . ( E )
F  -> . id

该自动机共有 12 个状态（包括对 ( 子表达式的递归处理）。每个状态编码了解析器在当前位置上所有可能的”解析进度”。

3.5 LR(0) 的局限

纯 LR(0) 解析器在遇到归约项时不看任何前方输入就决定归约。这导致很多实用文法产生冲突：

移进-归约冲突：某个状态既包含归约项又包含移进项
归约-归约冲突：某个状态包含多个不同产生式的归约项

表达式文法在状态 I2 中就会产生移进-归约冲突： E -> T . 说要归约，但 T -> T . * F 说如果下一个是 * 应该移进。

所以纯 LR(0) 几乎不能处理任何有实际用途的文法。

四、SLR(1)：基于 FOLLOW 集的冲突解决

4.1 SLR(1) 的核心思想

SLR(1)（Simple LR(1)）的改进很朴素：在决定是否归约 A -> alpha . 时，检查下一个输入符号是否在 FOLLOW(A) 中。

如果下一个符号不在 FOLLOW(A) 中，那么在任何合法的输入中都不可能在此处归约 A，所以可以安全地选择移进。

4.2 SLR(1) 解析表构造算法

对于 LR(0) 自动机中的每个状态 I：
  对于 I 中的每个项 A -> alpha . a beta（a 是终结符）：
    如果 GOTO(I, a) = Ij，则 ACTION[I, a] = shift j
  对于 I 中的每个归约项 A -> alpha .（A != S'）：
    对于 FOLLOW(A) 中的每个终结符 a：
      ACTION[I, a] = reduce A -> alpha
  如果 S' -> S . 在 I 中：
    ACTION[I, $] = accept
  对于每个非终结符 A：
    如果 GOTO(I, A) = Ij，则 GOTO[I, A] = j

4.3 SLR(1) 解析表示例

对于表达式文法，SLR(1) 解析表（部分）如下：

状态    id     +      *      (      )      $      E    T    F
-------------------------------------------------------------
0       s5            s4                          1    2    3
1              s6                          acc
2              r2     s7            r2     r2
3              r4     r4            r4     r4
4       s5            s4                          8    2    3
5              r6     r6            r6     r6
6       s5            s4                               9    3
7       s5            s4                                    10
8              s6                   s11
9              r1     s7            r1     r1
10             r3     r3            r3     r3
11             r5     r5            r5     r5

其中 sN 表示移进到状态 N，rN 表示按第 N 条产生式归约。

4.4 SLR(1) 的局限

SLR(1) 使用全局的 FOLLOW 集，不够精确。考虑以下文法：

S -> L = R | R
L -> * R | id
R -> L

在某个状态中，R -> L . 和 S -> L . = R 同时出现。 FOLLOW(R) 包含 =（因为 S -> L = R 和 R -> L 导致传播），所以 SLR(1) 报告移进-归约冲突。但实际上，在这个特定位置，R -> L . 后面不可能出现 =，因为 R 出现在 = 右边时不会被进一步嵌套在需要 = 的上下文中。

这就需要更精确的向前看信息。

五、LR(1)：向前看项

5.1 LR(1) 项的定义

LR(1) 项在 LR(0) 项的基础上增加了一个向前看符号（lookahead）：

[A -> alpha . beta, a]

其中 a 是一个终结符（或 $）。这个项的含义是：当解析器识别出 alpha 并期望 beta 时，如果最终 beta 为空（即到达归约项 [A -> alpha ., a]），只有在下一个输入符号恰好是 a 时才执行归约。

5.2 LR(1) 闭包运算

LR(1) 的闭包运算比 LR(0) 复杂，需要计算向前看符号的传播：

CLOSURE(I):
  将 I 中所有项加入结果集
  repeat:
    对于结果集中的每个项 [A -> alpha . B beta, a]：
      对于 B 的每个产生式 B -> gamma：
        对于 FIRST(beta a) 中的每个终结符 b：
          将 [B -> . gamma, b] 加入结果集
  until 不再变化

关键在于 FIRST(beta a)：向前看符号不是简单地照搬外层的 a，而是根据 B 之后的上下文精确计算。

5.3 LR(1) 自动机的规模

LR(1) 自动机的精确向前看信息消除了 SLR(1) 的虚假冲突。前面 SLR(1) 无法处理的 S -> L = R | R 文法，LR(1) 可以正确处理。

但 LR(1) 的代价是状态数爆炸。对于 C 语言的文法，LR(0) 大约有几百个状态，而 LR(1) 可能有数千个状态。对于更复杂的语言，状态数可能达到数万。

这就引出了 LALR(1) ——在 LR(1) 的精确性和 LR(0) 的紧凑性之间取得平衡。

5.4 一个 LR(1) 项集的例子

考虑增广文法的初始项集 I0（部分展示）：

[S' -> . E,        $]
[E  -> . E + T,    $/+]
[E  -> . T,        $/+]
[T  -> . T * F,    $/+/*]
[T  -> . F,        $/+/*]
[F  -> . ( E ),    $/+/*]
[F  -> . id,       $/+/*]

同一个 LR(0) 核心对应多个不同的向前看符号。

六、LALR(1)：合并同核 LR(1) 状态

6.1 核心思想

LALR(1)（Look-Ahead LR(1)）的关键观察是：

在 LR(1) 自动机中，很多状态只有向前看符号不同，而 LR(0) 核心（即去掉向前看符号后的项集）完全相同。将这些状态合并，只保留向前看符号的并集。

合并后的状态数与 LR(0)/SLR(1) 相同，但每个状态携带了比 SLR(1) 更精确的向前看信息。

6.2 合并的正确性

合并同核状态可能引入新的归约-归约冲突（因为向前看集合变大了），但绝不会引入新的移进-归约冲突。

实践中，LALR(1) 合并引入的额外冲突极其罕见。绝大多数编程语言的文法都是 LALR(1) 的。

6.3 两种构造方法

方法一：先构建完整的 LR(1) 自动机，再合并同核状态。

这是概念上最清晰的方法，但内存和时间消耗较大。

方法二：在 LR(0) 自动机基础上高效传播向前看符号。

DeRemer 和 Pennello（1982）提出了高效算法：

构建 LR(0) 自动机
确定哪些向前看符号是自发产生（spontaneously generated）的
确定哪些向前看符号需要在状态之间传播（propagated）
迭代传播直到不动点

这种方法的空间复杂度与 LR(0) 自动机相当，是 yacc/bison 采用的方法。

6.4 LALR(1) 与其他 LR 变体的关系

包含关系如下（严格递增）：

LR(0) 文法  <  SLR(1) 文法  <  LALR(1) 文法  <  LR(1) 文法

所有 SLR(1) 文法都是 LALR(1) 的，所有 LALR(1) 文法都是 LR(1) 的。反之不成立，但实际中的差异非常小。

一个文法是 LALR(1) 但不是 SLR(1) 的概率远大于它是 LR(1) 但不是 LALR(1) 的概率。

七、解析表构造

7.1 LALR(1) 解析表的结构

LALR(1) 解析表由两部分组成：

ACTION 表：ACTION[state, terminal] -> {shift s, reduce r, accept, error}
GOTO 表：GOTO[state, nonterminal] -> state

表的行数等于状态数，ACTION 表的列数等于终结符数， GOTO 表的列数等于非终结符数。

7.2 表压缩技术

真实解析表非常稀疏（大部分条目是 error）。常用的压缩方法包括：

行合并：如果两行没有冲突条目（非 error 位置不重叠或相同），可以合并为一行。这在 yacc 中通过 default reduction 实现。

分离列表：将每行的非 error 条目存为 (symbol, action) 对的链表。查找时线性扫描，但因为每行通常只有几个有效条目，速度并不慢。

双数组法（Tarjan）：将稀疏矩阵压缩为两个一维数组 check[] 和 next[]。这是 bison 默认使用的方法，空间效率很高。

// 双数组法查找
int lookup(int state, int symbol) {
    int pos = base[state] + symbol;
    if (check[pos] == state)
        return next[pos];
    return default_action[state];  // 通常是 error 或默认归约
}

7.3 解析器的驱动循环

不论使用哪种 LR 变体，解析器的驱动循环都是相同的：

void lr_parse(int *tokens) {
    int stack[MAX_STACK];
    int top = 0;
    stack[0] = 0;  // 初始状态
    int ip = 0;    // 输入指针

    for (;;) {
        int state = stack[top];
        int token = tokens[ip];
        int action = ACTION[state][token];

        if (action > 0) {          // shift
            stack[++top] = token;
            stack[++top] = action;  // 新状态
            ip++;
        } else if (action < 0) {   // reduce
            int rule = -action;
            int len = rule_length[rule];
            top -= 2 * len;         // 弹出 2*len 个元素
            int lhs = rule_lhs[rule];
            state = stack[top];
            stack[++top] = lhs;
            stack[++top] = GOTO[state][lhs];
        } else if (action == ACCEPT) {
            return;  // 成功
        } else {
            error_recovery(stack, &top, tokens, &ip);
        }
    }
}

八、冲突解决：优先级与结合性

8.1 冲突的本质

当 LALR(1) 解析表的某个条目中既有 shift 又有 reduce（或有两个不同的 reduce）时，文法存在二义性或解析表的精度不够。

最常见的二义性来源是：

运算符优先级：1 + 2 * 3 应该先算 * 还是 +？
运算符结合性：1 - 2 - 3 应该是 (1-2)-3 还是 1-(2-3)？
悬空 else 问题：if a then if b then s1 else s2 中 else 属于哪个 if？

8.2 yacc/bison 的 %left、%right、%nonassoc

yacc/bison 允许声明运算符的优先级和结合性：

%left '+' '-'
%left '*' '/'
%right UMINUS
%nonassoc '<' '>' EQ NEQ

优先级从上到下递增。当发生移进-归约冲突时：

比较要移进的终结符的优先级和要归约的产生式的优先级
如果移进符号优先级更高，选择移进
如果产生式优先级更高，选择归约
如果优先级相同，根据结合性决定：左结合选归约，右结合选移进

产生式的优先级默认取其右部最右终结符的优先级，也可以用 %prec 显式指定：

expr : '-' expr %prec UMINUS  { $$ = -$2; }
     ;

8.3 悬空 else 的处理

经典解法是让 else 的优先级高于 “then” 隐含的分隔。在 bison 中，通常用以下方式：

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

stmt : IF expr THEN stmt %prec LOWER_THAN_ELSE
     | IF expr THEN stmt ELSE stmt
     ;

或者更简洁地：直接依赖 bison 对移进-归约冲突默认选择移进的行为。 bison 会给出警告，但结果是正确的。

8.4 冲突的诊断

当遇到冲突时，可以用 bison -v grammar.y 生成 .output 文件，其中详细列出了每个状态的项集和冲突信息。

State 15

    5 expr: expr . '+' expr
    6     | expr . '*' expr
    6     | expr '*' expr .

    '*'  shift, and go to state 9
    '+'  shift, and go to state 8

    '*'       [reduce using rule 6 (expr)]
    '+'       [reduce using rule 6 (expr)]
    $default  reduce using rule 6 (expr)

方括号中的动作是被冲突解决规则排除的动作。

九、错误恢复策略

9.1 为什么错误恢复很难

语法错误发生后，解析器处于一个未知的状态。错误恢复的目标是：

尽可能准确地报告第一个错误的位置和性质
跳过出错的部分，继续解析后面的输入
避免产生级联错误（一个真正的错误引发大量虚假报告）

9.2 Panic Mode 恢复

最简单也最稳健的方法。当发生错误时：

从栈中弹出状态，直到找到一个状态 s，使得 GOTO[s, A] 对某个非终结符 A 有定义
从输入中丢弃符号，直到找到一个在 FOLLOW(A) 中的符号
将 GOTO[s, A] 压入栈，继续解析

这种方法相当于跳过了一个不完整的语法结构（如语句或表达式），从下一个同步点（如分号、右括号）恢复。

9.3 yacc/bison 的 error 伪终结符

yacc/bison 提供了更精细的控制。在文法中使用特殊的 error 符号：

stmt : expr ';'
     | error ';'  { yyerrok; printf("语法错误，跳过到分号\n"); }
     ;

block : '{' stmts '}'
      | '{' error '}'  { yyerrok; }
      ;

当解析器遇到错误时，它像处理终结符一样”移进” error，然后丢弃输入符号直到能继续解析。 yyerrok 宏告诉解析器错误已经恢复，不要压制后续的错误报告。

9.4 错误恢复的工程建议

策略	优点	缺点	适用场景
panic mode	实现简单、不会无限循环	可能跳过大段代码	通用、嵌入 error 规则不方便时
error 产生式	可以针对特定结构恢复	文法变复杂、可能引入新冲突	生产级编译器
短语级恢复	恢复精确	实现复杂、难以系统化	IDE 增量解析
全局纠正	理论上最优	太慢，不实用	纯学术研究

9.5 现代方法：错误容忍解析

tree-sitter 等现代解析器框架采用了完全不同的思路：它们不在单一位置报告错误然后恢复，而是将错误节点作为语法树的一部分保留。这样编辑器可以在有语法错误的代码中依然提供语法高亮和补全。

十、完整的 LALR(1) 解析器生成器 C 实现

下面给出一个约 250 行的精简 LALR(1) 解析器生成器。它实现了核心算法：LR(0) 项集构建、FOLLOW 集计算、 SLR(1) 表构造（作为 LALR(1) 的简化近似），以及驱动循环。

为控制篇幅，使用 SLR(1) 策略构造表，但自动机结构完全兼容 LALR(1) 向前看符号传播的扩展。

/*
 * lalr1_gen.c — 精简 LALR(1) 解析器生成器
 *
 * 文法硬编码为经典算术表达式：
 *   0: S' -> E
 *   1: E  -> E + T
 *   2: E  -> T
 *   3: T  -> T * F
 *   4: T  -> F
 *   5: F  -> ( E )
 *   6: F  -> id
 *
 * 终结符编码: id=0, +=1, *=2, (=3, )=4, $=5
 * 非终结符编码: S'=0, E=1, T=2, F=3
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ITEMS   128
#define MAX_STATES  64
#define NUM_TERMS   6
#define NUM_NONTERMS 4
#define NUM_RULES   7
#define NUM_SYMS    (NUM_TERMS + NUM_NONTERMS)

/* 终结符 */
enum { TK_ID, TK_PLUS, TK_STAR, TK_LPAREN, TK_RPAREN, TK_EOF };

/* 产生式: lhs, rhs_len, rhs[] */
static int lhs[NUM_RULES]     = { 0, 1, 1, 2, 2, 3, 3 };
static int rhs_len[NUM_RULES] = { 1, 3, 1, 3, 1, 3, 1 };
static int rhs[NUM_RULES][4]  = {
    { NUM_TERMS + 1 },                                     /* S' -> E        */
    { NUM_TERMS + 1, TK_PLUS, NUM_TERMS + 2 },             /* E  -> E + T    */
    { NUM_TERMS + 2 },                                     /* E  -> T        */
    { NUM_TERMS + 2, TK_STAR, NUM_TERMS + 3 },             /* T  -> T * F    */
    { NUM_TERMS + 3 },                                     /* T  -> F        */
    { TK_LPAREN, NUM_TERMS + 1, TK_RPAREN },               /* F  -> ( E )    */
    { TK_ID },                                             /* F  -> id       */
};

/* ----- LR(0) 项 ----- */
typedef struct { int rule; int dot; } Item;
typedef struct { Item items[MAX_ITEMS]; int n; } ItemSet;

static ItemSet states[MAX_STATES];
static int num_states;

static int item_eq(Item a, Item b) {
    return a.rule == b.rule && a.dot == b.dot;
}

static int set_has(ItemSet *s, Item it) {
    for (int i = 0; i < s->n; i++)
        if (item_eq(s->items[i], it)) return 1;
    return 0;
}

static void set_add(ItemSet *s, Item it) {
    if (!set_has(s, it))
        s->items[s->n++] = it;
}

static int sym_after_dot(Item it) {
    if (it.dot >= rhs_len[it.rule]) return -1;
    return rhs[it.rule][it.dot];
}

static void closure(ItemSet *s) {
    int changed = 1;
    while (changed) {
        changed = 0;
        for (int i = 0; i < s->n; i++) {
            int sym = sym_after_dot(s->items[i]);
            if (sym < NUM_TERMS || sym < 0) continue;
            int nt = sym - NUM_TERMS;
            for (int r = 0; r < NUM_RULES; r++) {
                if (lhs[r] == nt) {
                    Item it = { r, 0 };
                    if (!set_has(s, it)) {
                        set_add(s, it);
                        changed = 1;
                    }
                }
            }
        }
    }
}

static int sets_equal(ItemSet *a, ItemSet *b) {
    if (a->n != b->n) return 0;
    for (int i = 0; i < a->n; i++)
        if (!set_has(b, a->items[i])) return 0;
    return 1;
}

static int goto_table[MAX_STATES][NUM_SYMS];

static int find_or_add_state(ItemSet *s) {
    for (int i = 0; i < num_states; i++)
        if (sets_equal(&states[i], s)) return i;
    states[num_states] = *s;
    return num_states++;
}

static void build_automaton(void) {
    memset(goto_table, -1, sizeof(goto_table));
    ItemSet init = { .n = 0 };
    set_add(&init, (Item){ 0, 0 });
    closure(&init);
    states[0] = init;
    num_states = 1;

    for (int i = 0; i < num_states; i++) {
        for (int sym = 0; sym < NUM_SYMS; sym++) {
            ItemSet next = { .n = 0 };
            for (int j = 0; j < states[i].n; j++) {
                if (sym_after_dot(states[i].items[j]) == sym) {
                    Item it = { states[i].items[j].rule,
                                states[i].items[j].dot + 1 };
                    set_add(&next, it);
                }
            }
            if (next.n == 0) continue;
            closure(&next);
            goto_table[i][sym] = find_or_add_state(&next);
        }
    }
}

/* ----- FOLLOW 集 (SLR) ----- */
static int follow[NUM_NONTERMS][NUM_TERMS];
static int first[NUM_NONTERMS][NUM_TERMS];

static void compute_first(void) {
    int changed = 1;
    while (changed) {
        changed = 0;
        for (int r = 0; r < NUM_RULES; r++) {
            int nt = lhs[r];
            int s0 = rhs[r][0];
            if (s0 < NUM_TERMS) {
                if (!first[nt][s0]) { first[nt][s0] = 1; changed = 1; }
            } else {
                int src = s0 - NUM_TERMS;
                for (int t = 0; t < NUM_TERMS; t++)
                    if (first[src][t] && !first[nt][t])
                        { first[nt][t] = 1; changed = 1; }
            }
        }
    }
}

static void compute_follow(void) {
    follow[0][TK_EOF] = 1;  /* $ in FOLLOW(S') */
    int changed = 1;
    while (changed) {
        changed = 0;
        for (int r = 0; r < NUM_RULES; r++) {
            for (int d = 0; d < rhs_len[r]; d++) {
                int sym = rhs[r][d];
                if (sym < NUM_TERMS) continue;
                int nt = sym - NUM_TERMS;
                if (d + 1 < rhs_len[r]) {
                    int nxt = rhs[r][d + 1];
                    if (nxt < NUM_TERMS) {
                        if (!follow[nt][nxt])
                            { follow[nt][nxt] = 1; changed = 1; }
                    } else {
                        int src = nxt - NUM_TERMS;
                        for (int t = 0; t < NUM_TERMS; t++)
                            if (first[src][t] && !follow[nt][t])
                                { follow[nt][t] = 1; changed = 1; }
                    }
                }
                if (d + 1 == rhs_len[r]) {
                    int from = lhs[r];
                    for (int t = 0; t < NUM_TERMS; t++)
                        if (follow[from][t] && !follow[nt][t])
                            { follow[nt][t] = 1; changed = 1; }
                }
            }
        }
    }
}

/* ----- 解析表 ----- */
#define ACT_ERR  0
#define ACT_ACC  -9999

static int action[MAX_STATES][NUM_TERMS];  /* >0: shift, <0: reduce */

static void build_tables(void) {
    memset(action, 0, sizeof(action));
    for (int i = 0; i < num_states; i++) {
        for (int j = 0; j < states[i].n; j++) {
            Item it = states[i].items[j];
            int sym = sym_after_dot(it);
            if (sym >= 0 && sym < NUM_TERMS) {
                int target = goto_table[i][sym];
                if (target >= 0)
                    action[i][sym] = target + 1;  /* shift target */
            } else if (sym < 0) {
                if (it.rule == 0) {
                    action[i][TK_EOF] = ACT_ACC;
                } else {
                    int nt = lhs[it.rule];
                    for (int t = 0; t < NUM_TERMS; t++)
                        if (follow[nt][t])
                            action[i][t] = -(it.rule);  /* reduce */
                }
            }
        }
    }
}

/* ----- 驱动循环 ----- */
static const char *tok_name[] = { "id", "+", "*", "(", ")", "$" };
static const char *nt_name[]  = { "S'", "E", "T", "F" };

static void parse(int *tokens, int ntokens) {
    int stack[256], top = 0;
    stack[0] = 0;
    int ip = 0;

    printf("解析开始\n");
    for (;;) {
        int st = stack[top];
        int tk = tokens[ip];
        int act = action[st][tk];

        if (act > 0) {
            printf("  移进 %s, 转到状态 %d\n", tok_name[tk], act - 1);
            stack[++top] = tk;
            stack[++top] = act - 1;
            ip++;
        } else if (act < 0 && act != ACT_ACC) {
            int r = -act;
            printf("  归约 %s -> ", nt_name[lhs[r]]);
            for (int k = 0; k < rhs_len[r]; k++)
                printf("%s ", rhs[r][k] < NUM_TERMS ?
                       tok_name[rhs[r][k]] : nt_name[rhs[r][k] - NUM_TERMS]);
            printf("\n");
            top -= 2 * rhs_len[r];
            int nt_sym = lhs[r] + NUM_TERMS;
            int gto = goto_table[stack[top]][nt_sym];
            stack[++top] = nt_sym;
            stack[++top] = gto;
        } else if (act == ACT_ACC) {
            printf("  接受!\n");
            return;
        } else {
            printf("  错误: 状态 %d, 符号 %s\n", st, tok_name[tk]);
            return;
        }
    }
}

int main(void) {
    build_automaton();
    compute_first();
    compute_follow();
    build_tables();

    printf("状态数: %d\n\n", num_states);

    /* 解析 id + id * id */
    int tokens[] = { TK_ID, TK_PLUS, TK_ID, TK_STAR, TK_ID, TK_EOF };
    parse(tokens, 6);
    return 0;
}

编译运行：

gcc -O2 -Wall -o lalr1_gen lalr1_gen.c && ./lalr1_gen

输出：

状态数: 12

解析开始
  移进 id, 转到状态 5
  归约 F -> id
  归约 T -> F
  归约 E -> T
  移进 +, 转到状态 6
  移进 id, 转到状态 5
  归约 F -> id
  归约 T -> F
  移进 *, 转到状态 7
  移进 id, 转到状态 5
  归约 F -> id
  归约 T -> T * F
  归约 E -> E + T
  接受!

这个实现虽然精简，但完整展示了 LR 解析器生成器的核心结构：项集构建、闭包运算、GOTO 函数、FOLLOW 集计算、解析表填充和驱动循环。读者可以在此基础上扩展完整的 LALR(1) 向前看传播算法。

十一、GLR 解析：Tomita 算法与二义性文法

11.1 为什么需要 GLR

有些文法天然是二义性的，或者虽然无二义性但不是 LR(k) 的。例如：

C/C++ 中 T(x) 是函数调用还是变量声明？需要语义信息
自然语言处理中 “I saw the man with a telescope” 有两种解读
某些领域特定语言的文法无法轻易改写为 LALR(1)

GLR（Generalized LR）解析器在遇到冲突时不做选择，而是同时追踪所有可能的解析路径。

11.2 Tomita 算法的核心

Masaru Tomita 在 1985 年提出了 GLR 算法，核心思想是：

用图结构栈（Graph-Structured Stack, GSS）替代传统的线性栈
当遇到冲突时，分裂（split）栈，同时追踪多条路径
当多条路径到达同一个状态时，合并（merge）栈
使用共享打包解析森林（Shared Packed Parse Forest, SPPF）紧凑表示所有可能的解析树

传统 LR 栈：                GSS：
                            
  [0, E, 1, +, 6]            0 ——> 1 ——> 6
                              |          |
                              +——> 3 ——> 7

11.3 GSS 的结构

GSS 是一个有向无环图，每个节点是一个 (状态, 层级) 对。层级对应已读入的输入符号数，同一层级可能有多个节点。移进操作创建新的层级，归约操作沿边回溯。

11.4 GLR 的时间复杂度

对于无二义性文法：O(n)（退化为普通 LR）
对于二义性文法：最坏 O(n^3)（与 Earley 算法相同）
实践中，如果二义性有限，性能接近线性

11.5 bison 的 GLR 模式

bison 支持 %glr-parser 指令启用 GLR 模式：

%glr-parser
%expect-rr 1   /* 期望 1 个归约-归约冲突 */

%%

stmt : type_name '(' expr ')'   /* 类型转换 */
     | expr '(' expr ')'        /* 函数调用 */
     ;

当产生歧义时，bison 会调用用户定义的 %merge 函数来选择或合并结果：

%merge <merge_func>

11.6 GLR vs Earley vs GLL

特性	GLR	Earley	GLL
基础	LR 自动机	预测 + 完成	LL 递归下降
文法限制	无	无	无
无二义性性能	O(n)	O(n) 可实现	O(n) 可实现
最坏情况	O(n^3)	O(n^3)	O(n^3)
实现复杂度	高	中	中
工业应用	bison、tree-sitter	Marpa	学术为主

十二、工程实践：yacc/bison、tree-sitter、PostgreSQL 解析器

12.1 yacc/bison：经典工业级工具

yacc 由 Stephen C. Johnson 在 1975 年于贝尔实验室开发，GNU bison 是其自由软件替代品。

bison 的典型工作流：

grammar.y  ──> bison ──> grammar.tab.c + grammar.tab.h
lexer.l    ──> flex  ──> lex.yy.c
                     gcc ──> parser

bison 的关键特性：LALR(1) 和 GLR 两种模式、%define api.pure full 可重入解析器、 %define parse.error verbose 改善错误信息、%locations 行列追踪、支持 C/C++/Java 后端。

12.2 tree-sitter：现代增量解析

tree-sitter 由 Max Brunsfeld 开发，被广泛用于代码编辑器（Neovim、Zed、Helix）。

它的核心技术：

使用 GLR 算法处理文法二义性
增量解析：当代码被编辑时，只重新解析修改影响的部分
使用树差分算法（tree diffing）定位变化的子树
生成具体语法树（CST）而非抽象语法树（AST）
文法用 JavaScript DSL 定义，生成 C 解析器

tree-sitter 的文法定义风格：

module.exports = grammar({
  name: 'calc',
  rules: {
    expression: $ => choice(
      $.binary_expression,
      $.number,
      seq('(', $.expression, ')')
    ),
    binary_expression: $ => choice(
      prec.left(1, seq($.expression, '+', $.expression)),
      prec.left(2, seq($.expression, '*', $.expression)),
    ),
    number: $ => /\d+/,
  }
});

12.3 PostgreSQL 的解析器

PostgreSQL 使用 bison 生成 SQL 解析器。其文法文件 gram.y 超过 16000 行，约 800 条产生式，生成约 1300 个 LALR(1) 状态，大量使用 %nonassoc 和 %prec 解决冲突。

12.4 工程踩坑对照表

问题	症状	解决方案
移进-归约冲突	bison 报告 “N shift/reduce conflicts”	使用 `%left`/`%right` 声明优先级
归约-归约冲突	bison 报告 “N reduce/reduce conflicts”	重构文法，消除二义性
悬空 else	if-else 语句匹配错误	`%nonassoc LOWER_THAN_ELSE`、`%nonassoc ELSE`
内存泄漏	AST 节点在错误恢复时丢失	在 `%destructor` 中释放语义值
性能瓶颈	解析大文件时变慢	检查文法是否导致过多回溯（GLR 模式）
状态爆炸	bison 报告数千个状态	检查是否滥用了内联产生式
错误消息差	“syntax error” 无其他信息	`%define parse.error detailed` + `%define parse.lac full`
词法-语法耦合	标识符和关键字冲突	使用 `%token` 明确列出所有关键字
Unicode 支持	无法解析多字节字符	在词法分析器中处理编码
增量解析需求	每次修改都要重头解析	考虑迁移到 tree-sitter
规则过于复杂	单条产生式有十几个选项	拆分为子规则，提高可读性
递归深度	深层嵌套导致栈溢出	检查是否使用了右递归（应改为左递归）

12.5 其他值得关注的解析器框架

ANTLR（LL(*)）：Terence Parr 开发，自适应 LL 算法，多语言后端
Menhir（LR(1)）：OCaml 的 LR(1) 解析器生成器，Pager 算法合并状态
Lark（Earley/LALR）：Python 解析器库，自动选择解析策略

十三、个人观点与总结

13.1 LALR(1) 是否过时？

LALR(1) 在很多场景下仍然是最佳选择。 解析速度无可匹敌——每个输入符号只需一次表查找，无回溯。理论经过 60 年锤炼，工具链极度成熟。

但 LALR(1) 确实有其局限：

文法必须是无二义性的（或通过优先级声明消歧）
错误消息质量不如手写递归下降
不支持增量解析
文法调试需要理解项集和自动机

对于新项目，我的建议：

如果是编写一门新语言的编译器，认真考虑手写递归下降（GCC、Clang、Go、Rust 都是这样做的）
如果需要快速原型或 DSL，用 ANTLR 或 tree-sitter
如果在已有的 yacc/bison 代码库上工作，继续用它，不要为了”现代化”而迁移
如果性能是第一优先级（如数据库解析器），bison LALR(1) 仍是最优解

13.2 LR 解析能力层级的直觉

我经常用一个比喻来解释 LR 的各种变体：

LR(0)：一个只看手上有什么牌就出牌的玩家——太莽撞
SLR(1)：出牌前看一眼全局统计信息——好了一些，但信息太粗糙
LALR(1)：出牌前看一眼此刻的具体局面——绝大多数时候做出正确决策
LR(1)：记住了所有可能的局面——永远做出正确决策，但脑子不够用
GLR：遇到拿不准的局面，同时尝试所有可能——永远不会错，但可能慢

13.3 学习路径建议

如果你想真正理解 LR 解析，我建议的学习路径是：

手动为一个简单文法（如括号匹配）构建 LR(0) 自动机
为本文的表达式文法构建 SLR(1) 解析表，手动模拟解析过程
阅读龙书（Compilers: Principles, Techniques, and Tools）第 4 章
阅读 bison 源码中的 lalr.c 和 tables.c
用你喜欢的语言实现一个完整的 LALR(1) 解析器生成器
给你的解析器生成器加上错误恢复和语义动作

步骤 5 和 6 完成后，你对编译器前端的理解将超过 90% 的程序员。

13.4 从 Knuth 到 tree-sitter

1965 年 Knuth 的 LR(k) 论文开启了一个时代。 DeRemer 的 LALR 让 LR 解析走进了实用领域。 yacc 让每个 Unix 程序员都能写解析器。 bison 让它跨越了平台界限。 Tomita 的 GLR 扩展了 LR 解析的能力边界。 tree-sitter 将 LR/GLR 的思想带入了编辑器的实时增量解析。

六十年来，LR 解析的核心思想没有变：用有限自动机跟踪解析状态，用向前看符号解决冲突，用栈记录解析历史。这是一个优雅的理论，也是一个强大的工程工具。

13.5 延伸阅读

Knuth (1965). “On the Translation of Languages from Left to Right.”
DeRemer & Pennello (1982). “Efficient Computation of LALR(1) Look-Ahead Sets.”
Tomita (1985). “Efficient Parsing for Natural Language.”
Aho, Lam, Sethi, Ullman (2006). “Compilers: Principles, Techniques, and Tools.” 2nd ed.
Grune & Jacobs (2008). “Parsing Techniques: A Practical Guide.” 2nd ed.

附录：术语对照表

英文	中文
Context-Free Grammar	上下文无关文法
Terminal / Nonterminal	终结符 / 非终结符
Production	产生式
Derivation	推导
Handle	句柄
Item / Closure	项 / 闭包
Lookahead	向前看符号
Shift / Reduce	移进 / 归约
Conflict	冲突
Augmented Grammar	增广文法
Graph-Structured Stack	图结构栈
Incremental Parsing	增量解析

上一篇: DFA 最小化 下一篇: PEG 解析与 Packrat 相关阅读: - DFA 最小化 - 图着色与寄存器分配

目录