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 解析器等真实系统中的工程实践。

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

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

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

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

最左推导（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 解析器执行的正是最右推导的逆过程： 从输入串出发，逐步归约回开始符号。

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

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

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

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) 中扮演关键角色。

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

以输入 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。 这正是优先级和结合性在起作用。

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

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

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）， 表示右部已经完全匹配，可以执行归约。

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

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

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

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

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

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

初始状态 I0 的项集：

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

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

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

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

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

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

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

对于 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

对于表达式文法，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 条产生式归约。

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) 项在 LR(0) 项的基础上增加了一个向前看符号（lookahead）：

[A -> alpha . beta, a]

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

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 之后的上下文精确计算。

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) 的紧凑性之间取得平衡。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

真实解析表非常稀疏（大部分条目是 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 或默认归约
}

不论使用哪种 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);
        }
    }
}

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

最常见的二义性来源是：

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

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

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

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

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

经典解法是让 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 会给出警告，但结果是正确的。

当遇到冲突时，可以用 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)

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

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

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

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

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

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

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

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

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

下面给出一个约 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) 向前看传播算法。

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

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

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

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

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

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

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

%%

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

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

%merge <merge_func>

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 后端。

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

它的核心技术：

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+/,
  }
});

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

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

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

对于新项目，我的建议：

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

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

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

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

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

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

优先读同系列或同问题的下一篇，把单篇消费变成主题集群。

2026-06-14 · algorithms

寄存器分配是编译器后端对程序性能影响最大的优化。

2026-04-22 · algorithms

汇总本站算法工程相关文章，覆盖排序、哈希、树、字符串、近似数据结构、SIMD、随机化与编译器相关算法。

2025-07-15 · algorithms

从零开始实现一个基于有限状态机（FSM）的 JSON 解析器，不依赖第三方库，顺手吃透词法分析与语法分析的基础。

2025-07-15 · algorithms

从乔姆斯基层级、Thompson 构造到 NFA/DFA 与代码实现，系统理解正则表达式背后的理论与工程。