SQL 解析与抽象语法树

数据库接收到的输入是一串文本，执行器需要的是结构化的执行计划。两者之间隔着若干阶段：把字符切成记号、按文法组装成树、把树中的名称绑定到具体对象、再对树做等价变换，以缩小后续搜索的空间。这些阶段可以独立测试与替换，也是各类 SQL 诊断信息的来源。

词法分析

词法分析器按确定的规则把字符流切分为记号。SQL 的记号大致分为几类：

• 关键字：SELECT、FROM、WHERE 之类，大小写通常不敏感
• 标识符：表名、列名、别名，被引号包裹时可保留大小写与特殊字符
• 字面量：数字、字符串、日期时间、布尔值
• 运算符与标点：比较符、算术符、逗号、括号、分号
• 参数占位符：位置式问号或命名参数

切分过程需要处理注释、字符串转义与运算符的二义性（例如减号与负号、星号与通配符）。多数实现只把位置信息附着到记号上，记录偏移量与行列号，供后续报错时给出准确位置。

-- 输入
SELECT u.name, COUNT(*) AS n
FROM users AS u
WHERE u.created_at > '2026-01-01'
GROUP BY u.name;

-- 记号序列（示意）
-- 关键字 SELECT / 标识符 u / 点 / 标识符 name / 逗号
-- 函数名 COUNT / 左括号 / 星号 / 右括号 / 关键字 AS / 标识符 n ...

语法分析

语法分析按上下文无关文法判断记号序列是否合法，并产出语法树。常见实现路径有两类：

• 递归下降：为每条产生式写一个函数，结构容易阅读，也便于给出针对性的错误信息；需要改写文法或引入额外状态以处理左递归。
• 表驱动的 LR 类分析：由生成工具根据文法输出状态机与动作表，冲突需要人工消解。

SQL 文法存在一些不适配自顶向下分析的地方，例如投影列表的可选性与逗号分隔结构，以及表达式中的运算符优先级。因此多数生产实现会为表达式单独写一层优先级爬升的解析逻辑，或使用带优先级表的算符优先分析。

抽象语法树的节点类型

抽象语法树只保留语义相关的结构，括号与逗号这类纯语法记号不再出现。常见节点如下：

树的形状决定了后续遍历方式。改写阶段通常以「模式匹配加替换」的方式在树上操作，例如把谓词下推到子查询中，或把 IN 子查询转换为半连接。

语义分析与查询重写

语义分析

语法正确的语句仍可能引用不存在的表或列，或出现类型不匹配。语义分析从外到内逐层建立作用域：先收集当前查询块的来源表及其别名，再把投影与条件中的列引用绑定到具体对象，同时处理歧义（例如多个来源含有同名列时的解析顺序）。

这一阶段的输出通常是一棵带有类型与对象标识的树。绑定失败时的报错质量，取决于解析结果是否保留了列引用在原文中的位置信息。

查询重写

查询重写是对语法树做保持语义的等价变换，目的是让后续的计划枚举空间更小，或让代价估计更贴近实际。常见变换包括：

• 谓词下推：把过滤条件尽量靠近数据来源
• 常量折叠：在编译期计算纯常量表达式
• 子查询展开：把相关子查询改写为连接或半连接
• 视图展开：把视图引用替换为其定义体
• 外连接消除：当过滤条件使外连接退化为内连接时

等价性检查需要格外注意空值与重复行的语义，因此变换通常带有前置条件，只有条件成立时才应用。

参数占位符与预编译

带有占位符的语句可以把处理分成两步：先解析并生成可复用的结构，再把参数值填入执行。占位符在语法树中以参数节点表示，语义分析阶段只检查参数个数与可推导的类型，具体值在执行时提供。

-- 占位符形式，解析结果可被多次复用
SELECT id, total FROM orders WHERE user_id = ? AND status = ?;

这种分离让同一语句的解析结果被多次执行复用，也减少了把值拼接进文本时出现的注入风险。需要说明的是，预编译并不意味着每次执行都沿用同一计划：参数敏感的计划选择在部分实现中存在，某些实现会在多次执行后按实际参数分布重新选择计划。协议层如何传递预处理语句，可参见 MySQL 与 PostgreSQL 通信协议。

错误恢复

单条语句出错时，解析器通常放弃当前位置并跳到语句分隔符之后继续，以便一次交互中报告多处错误。恢复策略的差异会影响报错数量与准确性：简单地跳过分号可能掩盖后续错误，也可能把由前一个错误引起的连锁错误一并报出；基于同步记号集的恢复则能更快回到合法状态，代价是需要维护各状态下的同步集合。

另一种做法是在检测到错误时向上回溯若干层，尝试用替代产生式继续解析，这在允许语法错误自动纠正的实现中更常见。

小结

SQL 的处理是一条从文本到结构的流水线：词法切分得到记号，语法分析得到语法树，语义分析把名称与类型绑定上去，重写在不改变语义的前提下调整树的形状。占位符把结构与值分离，使解析结果可复用；错误恢复则决定解析器在遇到非法输入时能否继续给出有意义的信息。