词法分析与语法分析
词法分析器把源文本分成记号，语法分析器把记号组织成后续编译阶段使用的结构。12 + 3 * 4 先生成五个保持原顺序的记号，再被解析为 12 + (3 * 4)，结果是 24；若只从左到右计算，则得到 60。
词法分析负责切分和分类，语法分析负责层级。乘法优先不是把 * 记号提前，而是由解析调用的组织方式决定。
词法和语法分析如何工作
词法分析从左到右扫描。数字开始一个数值词素，相邻数字继续加入它，因此 12 是一个 NUMBER(12)，不是两个数字记号。+、*、(、) 各自形成记号。空白只推进扫描位置，不产生记号。@ 等未知字符没有可接受的类别，会使词法分析停止。
语法分析读取记号种类，不处理空格或原字符偏移。本课有三条递归下降规则：primary() 接受 NUMBER 或括号表达式；term() 处理 STAR 循环；expr() 处理 PLUS 循环。term 必须先完成自己负责的乘法，才能返回正在等待的 expr，优先级由此产生。
数字生成 AST 叶子。消耗运算符时不立即创建父节点，而是保留左子树和运算符，等待子调用解析右侧，再将两边归约为 Mul 或 Add。括号控制解析调用，结果树已记录其作用，因此不成为本课的 AST 节点。
词法与语法分析逐步演示
默认源文本为 12 + 3 * 4。
- 扫描 1，再把相邻的 2 加入同一范围，生成
NUMBER(12)。 - 跳过第一个空格，不在记号带上留占位。
- 生成
PLUS(+)，跳过第二个空格，生成NUMBER(3)。 - 第三个空格后生成
STAR(*)，第四个空格后生成NUMBER(4)。共有五个记号，另有 EOF 标记。 - 此时 PLUS 仍在 STAR 前，记号顺序尚未决定分组，因为还没有层级。
expr()调用term()，后者调用primary()，消耗 NUMBER(12) 并创建叶子 12。- term 看到 PLUS 而非 STAR，返回 12。外层 expr 消耗 PLUS，保留
left = 12，再调用 term 解析右操作数。 - 右侧 term 消耗 NUMBER(3)，看到 STAR，保留
left = 3，再调用 primary 取得 NUMBER(4)。 - term 将
3 * 4归约为 Mul；该子树返回后，等待中的 expr 才把12 + Mul归约为 Add 根。 - 全部记号已消耗，求值为
12 + (3 * 4) = 24。
记号带始终不重排。调用面板显示 expr 等待 term 完成 STAR，AST 父节点依归约顺序出现：先 Mul，后 Add。
控制流怎样变成树层级
语法规定 PLUS 的每个操作数都由 term 处理，而 term 先完成乘法，最终树为 Add(12, Mul(3, 4))。若把 PLUS、STAR 放进同一个从左到右循环，同一记号带会得到 Mul(Add(12, 3), 4)，结果为 60。改变的是解析控制流，不是运算符。
AST 保存分组决定，后续生成、优化和求值无需重新查询记号优先级。(12 + 3) * 4 也用同一套规则：primary 在括号中再次调用 expr，内层 Add 先完成，外层 term 再生成 Mul，此时 60 才是正确结果。
时间与空间复杂度
设源字符数 c、记号数 t、最大括号嵌套深度 d。
| 阶段 | 时间 | 辅助空间 | 原因 |
|---|---|---|---|
| 词法分析 | O(c) | O(t) | 每字符扫描一次，保存记号 |
| 语法分析 | O(t) | O(t) | 每记号消耗一次，AST 节点数 O(t) |
| 解析调用栈 | 包含在上项 | O(d + 1) | 嵌套括号增加递归层，基础规则占常数帧 |
这是当前确定性小语法的上界，不保证任意语法或解析策略都是线性。
边界情况
- 空输入或只有空白：词法分析得到空记号带，语法分析在需要 primary 时遇到 EOF，拒绝。
12+3*4与带空格版本有相同记号与树，空白由词法阶段处理。12 + @ 4在词法阶段停止，不创造 @ 记号，也不开始解析。12 + * 4词法合法、语法非法，primary 需要数字或左括号，却遇到 STAR。(12 + 3 * 4已形成内部子树，但take("RPAREN")在 EOF 处失败。
常见错误
- 每个数字字符发一个 NUMBER，把 12 拆开后留下没有运算符连接的第二个操作数。
- 认为能分词就语法正确。
12 + * 4的记号完整，但不满足语法。 - 读到运算符立即创建父节点。右子树还没有解析完，必须等待。
- 将加法、乘法写进同一解析循环，默认结果就从 24 变成 60。
- 说 AST 创造优先级。解析控制流选择分组，AST 记录结果。
- 在本课 AST 中保留括号节点。括号效果已由树层级表达。
模型范围与扩展
本课接受非负整数、加法、乘法和一层括号。省略标识符、一元运算、减除法、字符串、注释、源码位置、类型检查、错误恢复；实际解析器常会报告多个诊断，而非首次错误就停止。
同样结构可用于查询语言、配置表达式、模板和 DSL，以及编译器、检查工具。新增同优先级运算符通常扩展现有循环，新增优先级通常增加规则和调用边界，因此各规则应有明确职责。