元数据卡
- 前置知识：第3章（CFG/PDA）、第5章（词法分析）
- 预计时间：55 分钟
- 核心难度：进阶
- 阅读模式：高度专注（建议 55 分钟+）
- 完成标志：能写递归下降解析器，能解释 LL 与 LR 的区别，能手动构建表达式 AST
第六层的高塔内摆满了各种工具：有的像自顶向下的漏斗，有的像自底向上的起重机。你要用它们把词法分析送来的 token 流搭成树——不是装饰用的树，而是全体编译流程的骨架，抽象语法树（AST）。
你的进度
上一章你把源代码变成了 token 序列——现在你有一串 IF, LPAREN, ID, ...。但 token 序列就像一堆木材，还没搭成房子。你需要用文法规则重建出代码的层次结构。
你的任务
这一章你完成编译器前端最核心的部分——语法分析（Parsing）。你学会写递归下降解析器（手写派），了解 LL 与 LR 两类自动解析算法的区别，然后理解抽象语法树（AST）是如何从解析过程中产生的。目标是：给你一个 token 流，你能写出代码来把它变成一棵树。
破局 · 溯源
你手上有一串 token：ID(=x) ASSIGN NUM(5) SEMI。你本能地知道这对应一句赋值语句 x = 5;。但你要把这个"本能"变成数学规则和程序。
递归下降解析（自顶向下）
递归下降是最容易手写的解析器。它为每个非终结符写一个函数，函数体按产生式展开，遇到终结符就检查当前 token，遇到非终结符就调用对应的解析函数。你从起始符号的函数开始，一路递归展开下去。
下面是用 C 实现一个简化表达式解析器的核心部分（只支持加减和数字）：
typedef struct {
Token tokens[1024];
int pos;
} Parser;
Token peek(Parser *p) {
return p->tokens[p->pos];
}
Token advance(Parser *p) {
return p->tokens[p->pos++];
}
// 文法：E -> E + T | T
// 消除左递归后：E -> T { + T }
// T -> num
void parse_E(Parser *p) {
parse_T(p);
while (peek(p).type == TOKEN_PLUS) {
advance(p); // 消费 '+'
parse_T(p);
// 在这里可以构造加法 AST 节点
}
}
void parse_T(Parser *p) {
if (peek(p).type == TOKEN_NUM) {
advance(p); // 消费数字
// 在这里构造数字节点
} else {
// 语法错误
error("expected number");
}
}这个模式清晰、直观、可调试。每个函数对应一个文法非终结符，递归调用反映嵌套结构。因为文法已经消除了左递归，所以不会出现无限递归。
你注意到最关键的一点：解析器不仅要判断输入是否合法，还要构造语法树。在 parse_E 里面，遇到 + 时，你拿之前已经构造好的左子表达式节点和即将构造的右子表达式节点，新建一个"加法节点"。
AST（抽象语法树）与 CST（具体语法树）的区别
CFG 推导出的完整树包含了所有产生式的中间步骤，包括括号等"语法糖"。AST 则只保留对语义有意义的节点：
输入：1 + 2 * 3
CST（完整推导树）：
E
/|\
E + T
| /|\
T T * F
| | |
F F num(3)
| |
num(1) num(2)
AST（只保留语义结构）：
+
/ \
1 *
/ \
2 3AST 消除了括号（因为括号信息编码在树结构中了），消除了中间的非终结符（E、T、F），只留下运算符和操作数。AST 的节点类型通常是一个枚举联合体（union + tag）：
typedef enum { NODE_NUM, NODE_BINOP } NodeType;
typedef struct Node {
NodeType type;
union {
int num_val; // NODE_NUM
struct { // NODE_BINOP
struct Node *left;
struct Node *right;
int op; // PLUS, MINUS, MULT, DIV
} binop;
} data;
} Node;LL 解析 vs LR 解析
| 特性 | LL (自顶向下) | LR (自底向上) |
|---|---|---|
| 视角 | 从起始符号推导到输入 | 从输入缩减到起始符号 |
| 实现方式 | 递归下降 + 预测 | Shift-Reduce + 状态栈 |
| 文法限制 | 不能有左递归，需消除公因子 | 更宽松，可处理更多文法 |
| 手写难度 | 低 | 高（需要分析表） |
| 工具 | 手写为主 | Yacc/Bison（LALR(1)） |
| 错误恢复 | 好（可插入 close-brace 等） | 差（收到错误时已读入了较多内容） |
绝大多数手写解析器是 LL 风格的递归下降。Yacc/Bison 是 LR 解析器的自动生成工具。LL 对程序员更友好，LR 对语言设计者更友好（更少文法限制）。现代语言设计倾向于 LL——Go、Rust、Swift 都用手写递归下降解析器。
第一层：够用——用递归下降解析器解析表达式
追踪一下 1 + 2 + 3 的解析过程：
parse_E():
调用 parse_T(): 消费数字 1
看到 '+', 消费它
调用 parse_T(): 消费数字 2
看到 '+', 消费它
调用 parse_T(): 消费数字 3
没有更多 '+'了，返回构造出的 AST：
+
/ \
+ 3
/ \
1 2（加法左结合的自然结果。如果你是右结合——比如指数运算——AST 的顺序会反过来。）
第二层：深入——嵌入式动作与归约
在 Yacc/Bison 中，你不需要手写递归。你写文法规则和每条规则对应的动作（C 代码）：
expr: expr '+' term { $$ = make_binop($1, PLUS, $3); }
| term { $$ = $1; }
;
term: term '*' factor { $$ = make_binop($1, MULT, $3); }
| factor { $$ = $1; }
;
factor: '(' expr ')' { $$ = $2; }
| NUMBER { $$ = make_num($1); }
;Bison 从这些规则中生成 LR 解析表和 AST 构建代码。你的工作就是定义规则并提供节点构造函数。底层的"Shift 移入 token 到栈"和"Reduce 归约为非终结符"——这些 Bison 替我你做了。
常见陷阱
陷阱1：左递归导致递归下降解析器崩溃。 如果文法是 E -> E + T | T，递归下降的 parse_E 函数第一行就会调用自己——无限递归。必须消除左递归。
陷阱2：在 AST 中丢失 token 位置信息。 当你构造 AST 节点时，记得附带源代码位置（行号、列号）。没有位置信息，解析器生成的错误报告会说"这里错了"但不会说"在 23 行第 5 列错了"——这对程序员来说几乎不可用。
陷阱3：混淆括号在 AST 中的表示。 AST 中不需要专门的"括号节点"——括号信息被编码为树深度。1 + (2 * 3) 和 (1 + 2) * 3 的 AST 长得完全不同，这正是括号的效果。如果你在 AST 里放了括号节点，就说明你做错了。
通关挑战
热身（5分钟）： 对表达式
a + b * c - d画出 AST。先按标准优先级（乘优先于加减，加减左结合）。然后在文法中改一下优先级（让加法优先于乘法），再画一次 AST。挑战（30分钟）： 用 C 或 Java 实现一个完整的递归下降解析器，支持：加减乘除、括号、数字、单字母变量。文法采用三层优先级（加法层、乘法层、基础层）。验证输入
(a + b) * c + d的 AST 输出是正确的。观察： 打开 Rust 或 Go 编译器的源码，找到 parser.rs 或 parser.go，看看它们的递归下降解析函数对照 CFG 的结构。注意它们如何处理错误恢复（在遇到语法错误时跳转到下一个分号继续分析）。
旅人笔记
语法分析将 token 流重建为抽象语法树；递归下降（LL 风格）是最易手写的解析方法；AST 消除了语法表层，只保留语义骨架。
下一站预告
AST 告诉了你代码的形式结构——但形式正确不等于有意义。"hello" + 42 在语法分析后生成一棵合法的 AST，但语义上不合规。下一章，你在 AST 上做语义分析，让它真正被理解并转化为中间代码。