TL;DR

LALR(1)（Look-Ahead LR）是一个自底向上的语法解析算法，它与 yacc/bison 工具链深度绑定。PostgreSQL 在 1980 年代诞生于 UC Berkeley，当时 yacc 是 Unix 系统的标配，加之 SQL 语法天然适合 LALR(1) 表达，这一技术选型延续至今。

从 CFG 到解析器

任何编程语言或 DSL（Domain-Specific Language，领域特定语言，包括SQL）都需要一个解析器（parser），它将字符串输入转换为抽象语法树（AST）。解析器的理论基础是上下文无关文法（Context-Free Grammar, CFG）。

CFG 由四元组 (N, T, P, S) 定义：

  • N：非终结符集合（如 SELECT 子句、expression）
  • T：终结符集合（如 SELECT、FROM、+、* 等 token）
  • P：产生式规则集合（如 select_stmt → SELECT expr FROM table）
  • S：起始符号

解析算法的任务就是：给定一串 token，判断它能否从起始符号推导出来，并同时构造 AST。

大体上，解析算法分为两个流派：

流派方向代表算法典型工具
自顶向下（Top-Down）从 S 开始推导 token 串LL(k)、递归下降ANTLR、手写
自底向上（Bottom-Up）从 token 串归约到 SLR(0)、SLR(1)、LR(1)、LALR(1)yacc、bison

LR 家族：一步步走向 LALR(1)

LR(0)：最基础的自底向上解析

LR 解析器的核心是一个 DFA（确定有限自动机），它的状态由 LR(0) 项（item）构成。每个项是一个”带点”的产生式，点 . 标记当前解析位置：

E → E .+ T    ← 已经看到了 E，期望下一个是 + 和 T
E → E + .T    ← 已经看到了 E +，期望下一个归约为 T

LR(0) 解析器在每个状态只做两件事：

  • 移进（shift）：读入一个 token，点向右移动
  • 归约（reduce）：点到达产生式末尾，用产生式左部替换右部

当某个状态同时允许 shift 和 reduce 时，发生冲突。LR(0) 无法解决任何冲突，表达能力非常有限。

SLR(1)：引入 FOLLOW 集

SLR(1)（Simple LR）在 LR(0) 的基础上引入了一个简单的消歧策略：

在状态 S 中，如果同时允许归约 A → α· 和移进 token b，则查看 b 是否在 FOLLOW(A) 中。如果不在，则只做移进。

这解决了一部分冲突，但仍然不够——对于大多数实际编程语言的语法，SLR(1) 的表会充满冲突。

LR(1)：引入前瞻符号

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

[A → α·β, a]

含义：我们在解析位置 α·β，并且期望归约后能合法地后跟 token a。

LR(1) 表达能力极强——几乎所有确定性上下文无关语言都可以用 LR(1) 文法描述。但代价是状态数量爆炸：相比于 LR(0)，LR(1) 的状态数可能增长 10 倍甚至更多。

以一个简单的表达式文法为例：

  • LR(0) 状态数：~20
  • LR(1) 状态数：~200+

LALR(1)：合并同心状态

LALR(1) 的核心思想非常精妙：

将 LR(1) 中核心相同（即 LR(0) 部分相同，仅前瞻符号不同）的状态合并。

LR(1) 状态 3:  { [A → B·C, d], [E → F·, d] }
LR(1) 状态 7:  { [A → B·C, e], [E → F·, e] }

合并后的 LALR(1) 状态: { [A → B·C, d/e], [E → F·, d/e] }

这样的合并带来了巨大的收益：

属性LR(0)SLR(1)LALR(1)LR(1)
状态数基准同 LR(0)与 LR(0) 相同5-10× LR(0)
表达能力弱中等足够覆盖大多数语言最强
表大小小小小大

LALR(1) 的表大小与 LR(0) 相同，表达能力接近 LR(1)——这是它在上世纪 70-80 年代内存受限环境下成为主流的关键原因。

LALR(1) 的工程实践：yacc 与 bison

在理解了 LALR(1) 的理论优势后，工程上选择它还有一个关键原因——工具链。

yacc：Unix 的标配语法工具

yacc（Yet Another Compiler Compiler）由 Stephen C. Johnson 于 1975 年在 Bell Labs 开发，几乎是 Unix 系统的标准配置。yacc 的工作流程如下：

gram.y  ──[yacc]──►  y.tab.c  ──[cc]──►  parser

开发者只需编写 .y 语法文件，yacc 自动生成 C 语言的 LALR(1) 解析器。这让语言实现的门槛大幅降低。

PostgreSQL 项目诞生于 1986 年的 UC Berkeley，那时的 Unix 环境几乎只有 yacc 这一个解析器生成工具可用。

bison：GNU 的 yacc 替代品

PostgreSQL 目前使用的是 bison（GNU 版本的 yacc），其 gram.y 文件位于 src/backend/parser/gram.y，超过 15000 行。编译流程：

# PostgreSQL 构建中 bison 的调用等价于：
bison -d -o gram.c gram.y
# -d: 生成 gram.h（token 编号定义）
# -o: 输出 C 文件

生成的 gram.c 包含一个完整的 LALR(1) 解析表驱动的 DFA，每次 yyparse() 调用就是一次 SQL 语句解析。

一个简化的 SQL 语法示例

下面展示一段简化的 SQL 语法片段如何被 LALR(1) 接受：

/* grammar.y 简化片段 */
simple_select:
    SELECT opt_target_list
    FROM from_list
    WHERE a_expr
    ;

opt_target_list:
    target_list
    | /* empty */
    ;

target_list:
    target_el
    | target_list ',' target_el
    ;

规则中的左递归（target_list → target_list ',' target_el）对 LALR(1) 完全友好，并且是高效的（不会像递归下降那样导致栈溢出）。这一点是 LALR(1) 相比 LL 系解析器的天然优势——LALR(1) 天生支持左递归。

为什么 PostgreSQL 选择 LALR(1)

这不是一个单纯的技术问题，而是技术 + 历史的综合结果。

1. 历史路径依赖（1980 年代的 Berkeley）

1986 年，Michael Stonebraker 教授在 UC Berkeley 领导 POSTGRES 项目（PostgreSQL 的前身）。那时的技术选型非常有限：

  • yacc 是 Unix 标准工具，几乎所有做语言/DSL 的项目都用它
  • bison 尚未诞生（1987 年才出现第一个版本）
  • 手写递归下降（recursive descent）虽然理论上可行，但当时认为用生成工具更「工业化」
  • ANTLR 要到 1992 年才出现
  • 没有 LLVM、没有 Rust、没有 Go

在那种环境下，用 yacc/LALR(1) 几乎是唯一的选择。

2. SQL 文法的特性天然匹配 LALR(1)

SQL 是一种高度结构化的声明式语言，它的语法有几个特点：

  • 大量关键字驱动：SELECT、FROM、WHERE、GROUP BY、HAVING、ORDER BY —— 每个子句都有明显的起始关键字作为前瞻 token，这是 LALR(1) 的理想场景
  • 左递归友好：列表、表达式等大量使用左递归，LALR(1) 天然支持
  • 无歧义或低歧义：SQL 标准刻意设计为 LALR(1) 可解析的
-- 每个子句的关键字都是天然的 lookahead token
SELECT a, b          -- SELECT 告诉我们这是 select 子句
FROM t1              -- FROM 告诉我们进入 from 子句
WHERE a > 10         -- WHERE 告诉我们进入 where 子句
ORDER BY b DESC;     -- ORDER BY 告诉我们进入 order 子句

这种语法结构意味着 LALR(1) 解析器所需的前瞻信息几乎总是在下一个 token 中明确给出，冲突较少。

3. 状态表紧凑，适合当时的硬件

1980 年代末的硬件条件：

  • 典型服务器内存：8-32 MB
  • 编译器/解析器需要和数据库引擎共享这些内存

LALR(1) 的状态数与 LR(0) 相同（对于 SQL 文法约 2000-3000 个状态），而完整的 LR(1) 可能需要 15000+ 个状态。对于解析表的大小，这个差距是决定性的。

什么是递归下降？

在讨论 LALR(1) 的对比方案之前，有必要先理解什么是递归下降（Recursive Descent）。

递归下降是一种自顶向下（Top-Down）的解析方法。它的核心思想非常简单：为文法中的每个非终结符写一个函数，函数之间相互递归调用。整个解析过程从起始符号对应的函数开始，逐层展开，直到匹配到所有的 token。

以一段极简的 SQL 为例：

非终结符：select_stmt, target_list, target_el
产生式：
  select_stmt  → SELECT target_list FROM ID
  target_list  → target_el | target_el ',' target_list
  target_el    → ID

对应的递归下降解析器代码如下：

// 每个非终结符对应一个函数
ASTNode* parse_select_stmt() {
    expect(SELECT);                      // 消费 SELECT token
    ASTNode* targets = parse_target_list();
    expect(FROM);                        // 消费 FROM token
    char* table = expect_id();           // 消费表名
    return make_select_node(targets, table);
}

ASTNode* parse_target_list() {
    ASTNode* list = parse_target_el();   // 至少一个元素
    while (next_token() == COMMA) {      // 通过前瞻判断是否继续
        consume(COMMA);
        list = append(list, parse_target_el());
    }
    return list;
}

ASTNode* parse_target_el() {
    return make_id_node(expect_id());
}

实战走读：SELECT * FROM t1;

以 SELECT * FROM t1; 为例，词法分析后的 token 流为：

[SELECT] [STAR] [FROM] [ID:t1] [SEMICOLON]

按照上述文法，递归下降的调用栈如下：

1. parse_select_stmt()
   │
   ├─ expect(SELECT)           ✅ 消费 SELECT
   │
   ├─ parse_target_list()
   │   └─ parse_target_el()
   │       └─ expect_id()      → 当前 token 是 STAR，不是 ID！
   │
   └─ ... 解析失败！

等等——* 并不是一个 ID。这说明上面的极简文法不够精确。真实场景中，target_el 的规则要复杂得多：

target_el → ID           // 列名
          | STAR         // SELECT *
          | ID '.' STAR  // SELECT t1.*

修正后的 parse_target_el()：

ASTNode* parse_target_el() {
    if (next_token() == STAR) {
        consume(STAR);
        return make_star_node();           // SELECT *
    }
    char* id = expect_id();
    if (next_token() == DOT) {
        consume(DOT);
        expect(STAR);
        return make_table_star_node(id);   // SELECT t1.*
    }
    return make_id_node(id);               // SELECT col
}

现在重新走读整个调用链：

输入 token 流: [SELECT] [STAR] [FROM] [ID:t1] [SEMICOLON]

parse_select_stmt()
├─ expect(SELECT)                          → 消费 SELECT，剩余: [STAR][FROM][ID:t1][;]
├─ parse_target_list()
│   └─ parse_target_el()
│       ├─ next_token() == STAR?           → 是！
│       ├─ consume(STAR)                   → 消费 STAR，剩余: [FROM][ID:t1][;]
│       └─ return make_star_node()         返回 * 节点
├─ expect(FROM)                            → 消费 FROM，剩余: [ID:t1][;]
├─ expect_id()                             → 消费 ID:t1，剩余: [;]
└─ return make_select_node(star, table)    返回完整 AST

最终产出的 AST：

       select_stmt
       /    |    \
   target  from   where
     |      |       |
    [*]   [t1]   (null)

每一步函数调用都对应文法的一条产生式，调用栈的展开和收缩精确反映了 AST 的构建过程。这就是递归下降之所以”递归”的原因。

关键特征：

  1. 函数即规则：每个文法规则对应一个解析函数，结构直观
  2. 前瞻驱动：通过 next_token() 窥视下一个 token 来决定走哪条分支（这正是 LL(k) 的特征）
  3. 手写 = 完全可控：递归下降往往手写而非由工具生成，因此错误消息可以做得非常友好

递归下降的经典难题：左递归

递归下降最棘手的问题是左递归。考虑以下产生式：

expr → expr + term | term

如果直接翻译成代码：

ASTNode* parse_expr() {
    ASTNode* left = parse_expr();   // 无限递归！第一件事就是调用自己
    ...
}

程序会立刻陷入无限递归。要解决这个问题，需要手动将左递归改写为右递归或迭代形式：

// 消除左递归后的等价写法
ASTNode* parse_expr() {
    ASTNode* left = parse_term();
    while (next_token() == PLUS) {
        consume(PLUS);
        ASTNode* right = parse_term();
        left = make_binary_op(left, right);
    }
    return left;
}

注意，改写后的 AST 结构和解析逻辑已经发生了改变——你需要额外处理结合性等语义问题。而 LALR(1) 天然支持左递归，无需任何改写。

LALR(1) vs 手写递归下降：两种路线的权衡

虽然主流数据库几乎都使用 LALR(1)，但并非没有例外。一些新项目（如 ClickHouse）选择了手写递归下降。两种方案的取舍值得探讨：

方面LALR(1) / bison手写递归下降
开发效率修改 .y 文件即可，自动生成代码需要手写大量 boilerplate
正确性保证bison 自动检测冲突，杜绝语法歧义需要大量测试覆盖来保证
可维护性语法声明即文档，规则一目了然代码即语法，难以直观理解文法
错误消息较差（bison 自动生成 “syntax error”）可定制，友好度更高
解析速度表驱动，略微慢于手写通常更快（尤其在 JIT 场景）
语法扩展性每次修改需检查冲突灵活添加，但容易引入隐蔽歧义

对于 PostgreSQL 社区来说，切换到手写解析器的成本极高：

  • gram.y 有超过 15000 行代码
  • 230+ 个 SQL 关键字
  • 数百条语法规则
  • 解析器与语义分析（analyze.c）紧密耦合

这笔技术债务太重，而 LALR(1) 目前工作正常——更重要的是，它在可维护性和正确性方面的优势恰好与 PostgreSQL 社区「稳定压倒一切」的理念一致。

LALR(1) 的局限性与 PostgreSQL 的应对

1. Lookahead 不足导致的冲突

LALR(1) 只有一个 token 的前瞻。当语法需要多个 token 才能消除歧义时，会出现冲突。例如：

-- PostgreSQL 中的典型歧义场景
SELECT a FROM t WHERE a IN (SELECT ...);  -- IN 后跟子查询
SELECT a FROM t WHERE a IN (1, 2, 3);    -- IN 后跟值列表

PostgreSQL 的应对策略：在 bison 语法中使用 %nonassoc、%prec 等指示符手动指定优先级，或者将歧义推迟到语义分析阶段解决。

2. 错误消息质量

LALR(1) 自动生成的错误消息通常是 “syntax error at or near ‘xxx’“，这对用户并不友好。PostgreSQL 在这方面做了大量工作：

/* src/backend/parser/gram.y 中的错误处理 */
insert_target_list:
    insert_target_list ',' insert_target_el
    | insert_target_el
    | /* empty */
;

/* 手动添加详尽的错误恢复规则 */
| insert_target_list ','     /* 允许 trailing comma，但发出警告 */

通过精心设计的错误恢复规则（error productions），PostgreSQL 可以在大多数常见错误场景中给出更有意义的提示。

3. 语法扩展的保守性

每次向 gram.y 添加新规则，都需要确保不会引入 shift/reduce 或 reduce/reduce 冲突。这导致 PostgreSQL 社区对语法扩展持保守态度——新增一个 SQL 语法特性，往往需要反复验证 LALR(1) 兼容性。

参考