抽象语法树（AST）
在解析表达式、SQL 或领域特定语言（DSL）的系统中，抽象语法树（AST） 是连接解析与执行的核心表示。
解析与执行流程
处理通常遵循以下管道：
原始输入 → 词法分析器（Lexer） → 语法分析器（Parser） → AST → 中间表示 / 优化器 → 执行计划 → 执行引擎
步骤解析
- 词法分析（Lexer / Tokenization）
- 将原始文本转换为词法单元（tokens）：关键字、标识符、操作符、字面量等。
- 示例：
SELECT a, b FROM tbla WHERE a > 10;
→
["SELECT", "a", ",", "b", "FROM", "tbla", "WHERE", "a", ">", "10"]
- 语法分析（Parser）
- 消费词法单元，生成 解析树（Parse Tree），捕获精确的语法结构。
- 处理语法规则、操作符优先级和括号。
- 解析树通常冗长，会包含每一个语法元素。
- 抽象语法树（AST）
- 将解析树转换为 语义表示。
- 抽象掉语法细节（如逗号或括号）。
- 将程序组织为表达式、常量、标识符和语句等节点。
示例 AST
对于查询：
SELECT a, b FROM tbla WHERE a > 10;
AST 可能如下：
SelectStmt
├─ Columns
│ ├─ Identifier(a)
│ └─ Identifier(b)
├─ Table(tbla)
└─ Where
└─ Comparison
├─ Identifier(a)
├─ Operator(>)
└─ Constant(10)
Identifier(a)和Identifier(b)表示列引用节点。Constant(10)表示字面量节点。- AST 捕获 语义信息，而非原始语法，便于优化与代码生成。
- 中间表示 / 优化器（IR / Optimizer）
- AST 转换为 中间表示（IR），用于优化或执行计划生成。
- 常见优化：常量折叠、谓词下推、操作符重排。
- IR 表示执行就绪结构，抽象掉语言特定语法。
- 执行计划（Execution Plan）
- IR 转换为 执行引擎计划。
- 包含操作符顺序、索引选择、内存分配和调度。
- 执行引擎（Execution Engine）
- 执行计划并生成结果。
- 根据环境可能涉及多线程、I/O 调度、缓存或并行执行。
AST 的作用
-
AST 位于 管道核心，连接解析、优化和执行。
-
其设计影响：
-
遍历与转换的便利性
-
跨语言兼容性
-
性能和内存使用
-
各语言的 AST 定义不同，但核心概念一致：表示输入的 结构与语义。
性能考虑
- AST 构建复杂度高度依赖 语法规则 和 表达式深度。
- 回溯语法或深度嵌套表达式会增加解析与 AST 生成成本。
- AST 设计应在 语义清晰 与 遍历效率 之间权衡。
使用场景
- 表达式求值：用于内联计算或用户自定义函数。
- SQL 解析：形成查询优化与执行的语义层。
- DSL 处理：为解释器或编译器抽象领域特定语义。
注意：对于典型业务应用，用户很少直接操作 AST；它主要用于数据库引擎、编译器或表达式求值系统。
该 AST 模块为 IR 生成、优化和执行计划 提供基础。 不同语言和生态中 AST 的实现可能不同，但核心作用一致：将语法转换为具有语义意义、可操作的结构。