数据库解析器：理论基础与设计全景

引子：为什么数据库需要”解析器”？

用户写下的一句 SELECT * FROM users WHERE age > 18;，对数据库而言不过是一串字符。数据库既不会”读懂”英文，也不理解 SELECT 的含义——它需要先把字符串翻译成结构化的内部表示，才能继续做优化和执行。

这个”翻译”工作由**解析器（Parser）**完成。它处在数据库最前端的入口，是整个系统的”语法大脑”：

┌─────────────────────────────────────────────────────────┐
│                  一条 SQL 的旅程                          │
│                                                         │
│   "SELECT * FROM t1"  (字符串)                          │
│          │                                              │
│          ▼  ① 词法分析 Lexer                             │
│   [SELECT] [*] [FROM] [ID:t1]  (Token 流)               │
│          │                                              │
│          ▼  ② 语法分析 Parser                            │
│      语法树 / AST  (结构化的树)                          │
│          │                                              │
│          ▼  ③ 语义分析 Semantic                          │
│   绑定表/列、类型检查、名称解析                           │
│          │                                              │
│          ▼                                             │
│   查询树 → 优化器 → 执行器                               │
└─────────────────────────────────────────────────────────┘

本篇不堆砌晦涩术语，而是顺着”要造一个解析器，你得懂什么”这条主线，把所需的理论基础与工程知识串成一张知识地图。读完后，你应当能看懂 PostgreSQL 的 gram.y、SQLite 的 parse.y、或任何一份 SQL 文法文件在干什么。

一、形式语言与文法：解析器的”语言规则”

解析器的本质是用一套形式化的规则去判断”这个字符串是不是合法句子，并找出它的结构”。这套规则，就是形式文法（Formal Grammar）。

1.1 乔姆斯基谱系

语言学家乔姆斯基把形式语言按”表达能力”分成四层，恰好对应解析的难易程度：

类型	名称	表达能力	典型例子	用什么解析
Type 3	正则语言	最弱	邮箱、标识符、数字	正则引擎 / 有限自动机
Type 2	上下文无关语言（CFG）	中等	SQL 语法、表达式	LALR(1) / LL / 递归下降
Type 1	上下文有关语言	强	部分语义约束（如”先声明后使用”）	需配合语义分析
Type 0	递归可枚举	最强	任意可计算	图灵机

关键洞察：SQL 的词法属于 Type 3（正则），语法属于 Type 2（CFG）。这就是为什么词法分析器可以用正则引擎、语法分析器需要更强大的算法——它们处理的”语言层级”根本不同。

1.2 上下文无关文法（CFG）的四元组

一份 CFG 可以严格写成 G = (V, Σ, P, S)：

V：非终结符（Nonterminal），表示”语法范畴”，如 <select_stmt>、<expr>。它们会被继续展开。
Σ：终结符（Terminal），即词法分析产出的 Token，如 SELECT、*、ID、NUMBER。它们是树的叶子，不可再分。
P：产生式（Production），形如 A → α 的”改写规则”。
S：开始符号（Start symbol），整句话的起点，如 <program>。

用一段 SQL 文法片段举例：

select_stmt : SELECT target_list FROM table_ref
            | SELECT target_list FROM table_ref WHERE expr
target_list : '*'
            | column_list
column_list : column_ref
            | column_list ',' column_ref

这里 select_stmt、target_list 是非终结符；SELECT、FROM、*、, 是终结符（Token）；select_stmt 是开始符号。

1.3 推导与语法树

从开始符号出发，不断用产生式”替换”非终结符，直到全变成终结符，这个过程叫推导（Derivation）。推导留下的结构就是语法树（Parse Tree）：

            select_stmt
            /     |    \
      SELECT  target_list  FROM ...
                |
             column_list
             /    |    \
       column_list ',' column_ref
            |
        column_ref (t1)

歧义（Ambiguity）是指同一个句子能推导出两棵不同的语法树。例如 1 + 2 * 3 既可以先算 + 也可以先算 *——文法必须靠”优先级/结合性”规定唯一结构，否则解析器会报错。SQL 里大量运算符优先级（AND 低于 OR、乘高于加）就是这个原因存在的。

二、词法分析：把字符流切成”单词”

解析器不直接吃字符，而是先由**词法分析器（Lexer / Scanner）**把字符流切成 Token 流。

2.1 原理：正则 → NFA → DFA → Lexer

词法规则本质都是正则表达式（Type 3）。工程上编译器这样把它变成高效程序：

每个正则规则 → 一个 NFA（非确定有限自动机）
多个 NFA 合并 → 一个大的 NFA
NFA 子集构造 → DFA（确定有限自动机）
DFA 最小化 → 一张状态转移表，逐字符查表即可

这就是为什么 Flex、re2c 这类工具生成的词法分析器跑得极快：它最终只是一张查表的状态机。

2.2 Token 有哪些种类

对数据库而言，常见 Token 类别：

关键字（Keyword）：SELECT、FROM、WHERE、JOIN……
标识符（Identifier）：表名、列名、别名，如 users、age
运算符与标点：=, <, >, +, *, (, ,
字面量（Literal）：数字 18、字符串 'alice'、布尔 TRUE
注释与空白：通常词法阶段直接丢弃

2.3 SQL 词法里的”坑”

SQL 的词法比想象中刁钻，这也是为什么不能简单地”手写一个 split”：

大小写不敏感：select、SELECT、SeLeCt 都是同一个关键字。
保留字 vs 非保留字：ORDER 是保留字，但用户偏要把表命名为 order？需要靠引号 "order" 来消除歧义——这是词法/语法协同处理的难题。
字符串与转义：'O''Brien' 里的 '' 表示一个单引号，词法器要正确拼成 O'Brien。
多字符运算符：<=, <>, !=, :: 必须作为一个整体识别，不能拆成两个 < 和 =。

一个具体例子：SELECT 1+2 经过词法分析得到：

[SELECT] [NUMBER:1] [+] [NUMBER:2]

注意：词法阶段只负责”切词和分类”，它不知道 1+2 是表达式——那是语法分析的职责。

三、语法分析：把”单词”串成”句子结构”

语法分析器（Parser）读入 Token 流，依据文法判断句子是否合法，并构建出结构。这是解析器的核心，也是理论最丰厚的部分。两大流派：

3.1 自顶向下：LL(k) 与递归下降

思路是从”开始符号”出发，自顶向下地尝试匹配输入，像在猜”这句话应该是哪种句型”。LL(k) 表示：从左到右扫描（Left-to-right）、做最左推导（Leftmost derivation）、向前看 k 个 Token。

手写递归下降就是为每条非终结符写一个函数：

// 伪代码：递归下降解析一个 SELECT 语句
ASTNode* parse_select_stmt() {
    expect(SELECT);
    ASTNode* targets = parse_target_list();  // 调自己处理 target_list
    expect(FROM);
    char* table = expect_id();
    return make_select(targets, table);
}

致命问题——左递归：

expr : expr '+' term    // 左递归！
     | term

手写递归下降遇到 expr 会立刻又调用 expr，无限递归栈溢出。解决办法是”左递归消除”，但消除后会改变结合性、让文法变丑。对于表达式列表极长的 SQL，这非常痛苦。

3.2 自底向上：LR 家族

另一流派是自底向上（Bottom-up）：从 Token 开始，不断地把”已匹配的片段”**归约（Reduce）**成非终结符，像在玩”消消乐”，直到归约出开始符号。

LR 表示从左到右扫描、做最右推导的逆过程（Rightmost derivation in reverse）。演进出四个档次：

算法	全称	特点
LR(0)	—	不看向前看符号，太弱，几乎不能用
SLR(1)	Simple LR	用 FOLLOW 集做简单决策，偶有冲突
LR(1)	Canonical LR	状态精确但状态数爆炸
LALR(1)	Look-Ahead LR	合并相同”核心”的 LR(1) 状态，状态数与 SLR 相当，能力强

LALR(1) 维护两张表来驱动解析：

ACTION 表：当前状态和当前 Token 下，该”移进（Shift）“还是”归约（Reduce）”
GOTO 表：归约后跳到哪个状态

移进-归约冲突 / 归约-归约冲突：当表里有格子同时有两个动作，就说明文法有歧义或需要用优先级消歧。这正是写 SQL 文法时最花精力的地方。

3.3 为什么 SQL 几乎都选 LALR(1)？

回看 3.1 的左递归问题：SQL 是关键字驱动且充满左递归的语言——

表达式 a + b + c + ... 天然用左递归文法写得最自然；
SELECT 列表、FROM 多表连接、嵌套子查询，都是”一串同构元素”；
关键字（SELECT/FROM/WHERE）提供了极强的向前看信号，让 LALR(1) 的 1 个 Token 前瞻足以消解绝大多数歧义。

所以 MySQL（bison）、SQLite（Lemon）、CockroachDB / TiDB（goyacc）、DuckDB（fork libpg_query）、PostgreSQL（bison + gram.y）全部选择了 LALR(1) 家族。关于这段历史与取舍，可参见博客《为什么是 LALR(1)？》。

3.4 走读：`SELECT * FROM t1` 在解析栈里发生了什么

用 LALR(1) 自底向上视角，简化演示（栈里是”状态|符号”）：

输入剩余: SELECT * FROM t1 $
栈:                动作
─────────────────────────────────────
[ ]                 Shift SELECT  →
[0|SELECT]          Reduce: 进入 select 起始
[0|SELECT][s1]      Shift *       →
...                 Shift FROM    →
...                 Shift ID(t1)  →
[ ... | FROM | t1 ] Reduce: table_ref → table
[ ... | FROM | table ] Reduce: select_stmt 完成 ✓

直观感受：解析器一边”吃”Token 入栈，一边在合适时机把栈顶一段”折叠”成更高层的语法结构，最终折叠成一棵完整的查询树。

四、从语法树到 AST：语义动作

语法分析产出的语法树会把每个非终结符、每个标点都画出来，非常臃肿。工程上我们通常构建更精简的 抽象语法树（AST，Abstract Syntax Tree）——只保留”有意义的骨架”：

语法树（啰嗦）               AST（精简）
select_stmt                  SelectStmt
├ SELECT                     ├ target: Star
├ target_list                └ from: Table(t1)
│ └ '*'
├ FROM
└ table_ref
  └ ID(t1)

在 yacc/bison 里，用语义动作在归约时刻构造 AST：

select_stmt
  : SELECT target_list FROM table_ref
    { $$ = make_select($2, $4); }   /* $$ 是结果，$2/$4 是子节点 */
;

$$ 代表本条规则归约后产生的属性（这里是 AST 节点），$1、$2… 分别是各位置的子节点。这就是”语法驱动翻译”——解析和建树是同一遍完成的。

五、语义分析：解析之后还要”理解”

语法正确 ≠ 语义正确。SELECT age FROM users 语法没问题，但 users 表若不存在、或 age 不是它的列，就属于语义错误。这一步往往紧接在解析之后，由语义分析器完成，它依赖两个基础：

5.1 符号表与作用域

语义分析需要一张符号表（Symbol Table） 记录”当前可见的表、列、别名、类型”。SQL 的作用域是嵌套的：WHERE 能看到 FROM 引入的表别名，子查询又引入自己的作用域。

5.2 上下文相关：同名异义

CFG（Type 2）表达不了”标识符必须先声明后使用”这类规则——这是 Type 1 上下文有关的部分。因此解析器通常这样处理：

词法/语法阶段把 users 当成一个无意义的 ID 吞进去；
语义阶段再查符号表，判定它是”表名”还是”列名”还是”别名”；
若都查不到 → 报语义错误。

例如 SELECT a FROM t 里的 a，单独看语法完全合法，只有结合表 t 的 schema 才能确定它是列。这就是名称解析（Name Resolution），是解析器”智能”的核心来源。

5.3 类型检查

确定 age 是 INT 后，age > 18 才合法；若 age > 'abc' 则类型不匹配。类型推断与检查也在语义阶段完成，为后续优化器提供关键信息。

六、错误处理与恢复

生产级解析器不能遇到第一个错误就崩溃退出。它需要错误恢复（Error Recovery），尽量继续解析以一次报出多个错误。经典策略：

Panic Mode（恐慌模式）：一旦出错，疯狂丢弃 Token 直到遇到”同步符号”（如 ; 或 FROM），再重新开始。实现简单，最常用。
Error Productions（错误产生式）：在文法里显式写出”常见错误写法”，给出友好提示。例如 PostgreSQL 的 gram.y 中就有 error 占位符：

insert_target_list
  : insert_target_list ',' insert_target_el
  | insert_target_el
  | /* empty */
  | insert_target_list ','   /* 允许尾随逗号，但发出警告 */
    { $$ = $1; ereport(WARNING, ...) }
;

Phrase-level Recovery（短语级恢复）：局部纠正（补一个缺失的 )），更精细但更难写。

七、工程选型：工具与实践

理论落到工程，主流工具有：

工具	算法	代表用户
Flex + Bison	正则词法 + LALR(1)	PostgreSQL、MySQL
Lemon	LALR(1)，无全局变量、线程安全	SQLite
ANTLR	LL(*) 自适应自顶向下	很多新项目、语言工具
goyacc	Go 版 LALR(1)	CockroachDB、TiDB
手写递归下降	LL(k)	部分追求极致可控性的项目

SQL 解析的工程”坑”小结：

关键字冲突：新版本引入 WINDOW、LATERAL 等关键字，可能让老查询里用这些词做列名的地方突然报错——数据库因此把关键字分为”保留/非保留”。
文法冲突：每加一条规则都要用 bison -v 检查是否新增 shift/reduce 或 reduce/reduce 冲突。
性能：解析是每条 SQL 的必经之路，必须快；LALR 表驱动 + 正则 DFA 正是为此设计。
预处理：参数化查询（$1、?）要在词法阶段特殊处理，避免重复解析。

八、知识地图小结

如果要从零设计一个数据库解析器，你需要按这条链路储备知识：

① 形式语言理论
   ├ 乔姆斯基谱系（正则 / 上下文无关 / 上下文有关）
   ├ CFG 四元组（V, Σ, P, S）
   └ 推导、语法树、歧义与优先级
        │
② 词法分析
   ├ 正则表达式 → NFA → DFA
   ├ Token 分类（关键字/标识符/运算符/字面量）
   └ SQL 词法坑（大小写、引号、转义、多字符运算符）
        │
③ 语法分析（核心）
   ├ 自顶向下：LL(k)、递归下降、FIRST/FOLLOW、左递归消除
   ├ 自底向上：LR(0)/SLR/LR(1)/LALR(1)、ACTION/GOTO 表
   ├ 移进-归约、归约-归约冲突
   └ 为什么 SQL 选 LALR(1)（左递归友好 + 关键字驱动）
        │
④ 语义动作与 AST
   ├ 语法树 vs AST
   └ yacc 语义动作：$$ = f($1, $2...)
        │
⑤ 语义分析
   ├ 符号表与作用域
   ├ 名称解析（上下文相关）
   └ 类型检查
        │
⑥ 错误处理与恢复
   ├ Panic mode / Error productions / Phrase-level
   └ PostgreSQL gram.y 实战
        │
⑦ 工程工具
   └ Flex/Bison, Lemon, ANTLR, goyacc, 手写

一句话收束：解析器 = 正则词法（Type 3）+ LALR(1) 语法（Type 2）+ 语义分析（补上 Type 1 的上下文）。前两层有成熟理论与工具可”无脑”套用，真正体现数据库设计功力的是语义分析、错误恢复与那些 SQL 特有的工程权衡。

下一步可深入阅读词法分析（Flex 实战）与 LALR(1) 文法构造（bison 冲突调试）两个专题。