从零编写现代编译器 04 - 表达式解析与错误恢复

第 03 篇给了编译器完整的词法分析器和源码位置。解析器已经能识别函数定义和 return 语句，但 return 后面那个表达式还只能接受单个整数字面量。return 1 + 2 * 3; 在当前解析器面前会直接报错——它不知道运算符是什么，更不知道 * 应该比 + 先结合。这一篇要解决这个问题：用 Pratt 解析实现一个完整的表达式解析器，正确处理优先级和结合性，并在遇到语法错误时恢复到可继续解析的状态。

优先级表

表达式里运算符的优先级决定了 AST 的形状。1 + 2 * 3 应该解析为 1 + (2 * 3) 而不是 (1 + 2) * 3。Sprout 语言的优先级从低到高：

优先级	运算符	结合性	说明
1	||	左结合	逻辑或，短路
2	&&	左结合	逻辑与，短路
3	== !=	左结合	相等比较
4	< > <= >=	左结合	大小比较
5	+ -	左结合	加减
6	* /	左结合	乘除
7	一元 - !	前缀	取负、逻辑非

所有二元运算符都是左结合。a + b + c 解析为 (a + b) + c，a || b || c 解析为 (a || b) || c。右结合运算符（比如赋值 =）在 Sprout 里通过语句语法处理，不进入表达式优先级表。

优先级设计和 C、Rust、Java 的算术与逻辑部分基本一致。不同之处在于 C 的位运算和三元运算符在 Sprout 的当前阶段不存在，所以优先级表更短。短是好事——调试优先级错误时，层级越少越容易定位。

这张表直接映射成 Pratt 解析器的绑定力（binding power）数字。

Pratt 解析的核心思路

递归下降解析器处理运算符优先级的经典方式是为每个优先级写一个函数：parse_or 调用 parse_and，parse_and 调用 parse_equality，一直到 parse_unary。这种方式正确，但六七层嵌套函数对应六七个优先级级别，加一个优先级就加一层函数。

Pratt 解析（也叫 top-down operator precedence parsing，由 Vaughan Pratt 在 1973 年提出）用一种更紧凑的思路取代了这种级联：给每个运算符一个数字——绑定力（binding power），然后用一个通用函数 parse_expr(min_bp) 递归处理所有优先级。增加新运算符只需要在绑定力表里加一行，不需要动函数结构。

核心规则只有一条：当下一个运算符的绑定力大于 min_bp 时，它属于当前子表达式；否则，当前子表达式结束，把控制权还给上层调用。

绑定力越高的运算符越"贪心"，会先把两边的操作数抓住，形成更深层的子树。* 的左绑定力（11）高于 + 的左绑定力（9），所以在解析 1 + 2 * 3 时，* 会先把 2 和 3 抓走，+ 只能拿到 1 和 (2 * 3) 这个整体。

绑定力的数值编码

左结合的二元运算符用一对绑定力表示：左绑定力和右绑定力。左绑定力决定该运算符能否从上层"抢走"左操作数；右绑定力传入递归调用，决定右操作数延伸到哪里。

左结合运算符的右绑定力 = 左绑定力 + 1。这保证同优先级的运算符左边先结合。比如 + 的左绑定力是 9，右绑定力是 10；遇到 a + b + c 时，解析完 a + b 后，第二个 + 的左绑定力（9）不大于当前 min_bp（10），所以 b 不会被第二个 + 抢走，a + b 先形成子树。

fn infix_binding_power(op: &TokenKind) -> Option<(u8, u8)> {
    match op {
        TokenKind::OrOr    => Some((1, 2)),
        TokenKind::AndAnd  => Some((3, 4)),
        TokenKind::EqEq | TokenKind::BangEq => Some((5, 6)),
        TokenKind::Lt | TokenKind::Gt
        | TokenKind::LtEq | TokenKind::GtEq => Some((7, 8)),
        TokenKind::Plus | TokenKind::Minus  => Some((9, 10)),
        TokenKind::Star | TokenKind::Slash  => Some((11, 12)),
        _ => None,
    }
}

前缀运算符只有右绑定力，没有左绑定力——它们不消耗左边的操作数。一元 - 和 ! 的右绑定力设为 13，高于所有二元运算符，这样 -a + b 永远解析为 (-a) + b，而不是 -(a + b)。双重前缀 --a 也能正确解析为 -(-a)，因为外层 - 递归调用 parse_expr(13) 时，内层 - 仍然作为前缀被正确识别。

fn prefix_binding_power(op: &TokenKind) -> Option<u8> {
    match op {
        TokenKind::Minus | TokenKind::Bang => Some(13),
        _ => None,
    }
}

parse_expr 实现

有了绑定力表，整个表达式解析器只需要一个函数：

fn parse_expr(&mut self, min_bp: u8) -> Expr {
    // 1. 解析前缀部分（原子或一元运算符）
    let mut lhs = match self.peek() {
        TokenKind::Int(n) => {
            let span = self.advance().span;
            Expr::Literal { value: n, span }
        }
        TokenKind::True | TokenKind::False => {
            let tok = self.advance();
            Expr::BoolLit { value: tok.kind == TokenKind::True, span: tok.span }
        }
        TokenKind::Ident(name) => {
            let span = self.advance().span;
            Expr::Var { name, span }
        }
        TokenKind::LParen => {
            self.advance(); // 消耗 '('
            let inner = self.parse_expr(0); // 从零开始，重置优先级
            self.expect(TokenKind::RParen);
            inner
        }
        op if prefix_binding_power(&op).is_some() => {
            let bp = prefix_binding_power(&op).unwrap();
            let op_span = self.advance().span;
            let operand = self.parse_expr(bp);
            Expr::Unary { op, operand: Box::new(operand), span: op_span }
        }
        _ => {
            return self.error_expr("expected expression");
        }
    };

    // 2. 循环处理中缀运算符
    loop {
        let op = self.peek();
        let (l_bp, r_bp) = match infix_binding_power(&op) {
            Some(bp) => bp,
            None => break, // 不是中缀运算符，表达式结束
        };
        if l_bp < min_bp {
            break; // 运算符绑定力不够，交还给上层
        }
        self.advance(); // 消耗运算符
        let rhs = self.parse_expr(r_bp);
        lhs = Expr::Binary {
            op,
            lhs: Box::new(lhs),
            rhs: Box::new(rhs),
            span: lhs.span().merge(rhs.span()),
        };
    }

    lhs
}

入口调用 parse_expr(0)，min_bp 为零表示接受任何运算符。

两段代码，两个职责。第一段处理前缀：字面量、变量、括号表达式和一元运算符。第二段是一个循环，不断尝试把当前 lhs 和下一个中缀运算符结合，直到运算符的绑定力不足以继续。

逐步跟踪 1 + 2 * 3

手动跑一遍 parse_expr(0) 处理输入 1 + 2 * 3。

第一步，min_bp = 0。前缀阶段读到 1，lhs = Literal(1)。

第二步，进入循环。下一个 token 是 +，左绑定力 9，大于 min_bp（0），进入。消耗 +，递归调用 parse_expr(10)（右绑定力 10）。

第三步，递归内部 min_bp = 10。前缀阶段读到 2，lhs = Literal(2)。进入循环，下一个 token 是 *，左绑定力 11，大于 min_bp（10），进入。消耗 *，递归调用 parse_expr(12)。

第四步，递归内部 min_bp = 12。前缀阶段读到 3，lhs = Literal(3)。进入循环，没有更多 token（或者下一个 token 是 ;，不是中缀运算符），break。返回 Literal(3)。

第五步，回到第三步的循环。rhs = Literal(3)，构造 Binary(*, Literal(2), Literal(3))。循环继续，没有更多运算符（; 不是中缀运算符），break。返回 Binary(*, 2, 3)。

第六步，回到第二步的循环。rhs = Binary(*, 2, 3)，构造 Binary(+, Literal(1), Binary(*, 2, 3))。循环继续，没有更多运算符，break。返回最终 AST。

结果：

  +
 / \
1   *
   / \
  2   3

* 的绑定力比 + 高，它在更深的递归层级抓住了 2 和 3，+ 只能等 * 完成后拿到整个子树。整个过程没有专门为 + 或 * 写的解析函数——同一个 parse_expr 通过不同的 min_bp 参数自动处理了优先级差异。这就是 Pratt 解析的简洁之处。

如果把输入换成 1 * 2 + 3，跟踪过程会有所不同。* 先抓住 1 和 2（因为 + 的左绑定力 9 低于当前 min_bp 12），然后回到外层，+ 拿到 Binary(*, 1, 2) 和 3。最终树的根是 +，左子树是 *。无论运算符出现的顺序如何，绑定力决定了树的形状。

括号表达式

(expr) 在前缀阶段处理。遇到 ( 时消耗它，然后调用 parse_expr(0)——min_bp 回到零，意味着括号内部的优先级完全重置。解析完内部表达式后，expect(TokenKind::RParen) 确认闭合。

(1 + 2) * 3 的解析过程：外层读到 (，递归进入 parse_expr(0) 解析 1 + 2，返回 Binary(+, 1, 2)。回到外层，下一个运算符是 *，正常处理。最终树的根是 *，左子树是 +。括号本身不出现在 AST 里——它的作用已经通过树的形状体现了。

布尔表达式的优先级

a && b || c 应该解析为 (a && b) || c，因为 && 的绑定力（3/4）高于 ||（1/2）。

同理，a || b && c 解析为 a || (b && c)。混合使用时，&& 总是先结合。如果意图不同，必须加括号。

a == b && c < d 解析为 (a == b) && (c < d)，因为 == 和 < 的绑定力都高于 &&。这和大多数语言的行为一致。

比较链的限制

写 a < b 完全合法，结果类型是 bool。但如果写 a < b < c，Pratt 解析器会把它解析为 (a < b) < c——左结合。这在语法层面是合法的 AST。

问题出在类型检查：a < b 的结果是 bool，然后 bool < c 要求 bool 和 i64（假设 c 是整数）做比较，这是类型错误。Sprout 不支持 bool 和 i64 之间的比较运算。

Python 和数学里的链式比较 a < b < c 表示 a < b and b < c，但 Sprout 不做这种语法糖。解析器忠实地按左结合规则构造 AST，类型检查阶段负责拦截语义问题。这种职责划分使得每一层的逻辑更简单、更容易测试。

这个错误不在解析阶段拦截——解析器只负责按绑定力构造 AST。第 06 篇的类型检查器会在遍历 AST 时报告：

error[E0201]: operator `<` requires operands of type `i64`,
              found `bool` and `i64`
  --> test.spr:3:10

表达式中的错误恢复

解析器应该在遇到第一个语法错误后继续工作，而不是直接退出。一个 50 行的文件里可能有三处语法错误，程序员希望一次编译就看到全部，而不是每次只修一个。

核心策略是：遇到无法解析的位置时，生成一个 Expr::Error 节点（附带源码范围），然后跳到下一个同步点继续解析。

fn error_expr(&mut self, message: &str) -> Expr {
    let span = self.current_span();
    self.report_error(message, span);
    self.synchronize();
    Expr::Error { span }
}

Expr::Error 是 AST 的正式成员，后续的名称解析和类型检查遇到它时直接跳过，不产生连锁错误。

同步策略

同步的目标是找到一个"大概率是新语句开头"的位置。对于 Sprout，同步点是分号 ; 和右花括号 }。

fn synchronize(&mut self) {
    loop {
        match self.peek() {
            TokenKind::Semi => {
                self.advance(); // 消耗分号，准备解析下一条语句
                return;
            }
            TokenKind::RBrace | TokenKind::Eof => {
                return; // 不消耗，让上层处理
            }
            _ => {
                self.advance(); // 跳过无关 token
            }
        }
    }
}

碰到 ; 就消耗它并返回——调用者可以开始解析下一条语句。碰到 } 不消耗——让包裹函数体的解析逻辑来处理闭合。碰到 Eof 也停下，避免无限循环。

考虑以下输入：

fn main() -> i64 {
    let x: i64 = 1 + ;
    let y: i64 = 2;
    return x + y;
}

解析 1 + ; 时，parse_expr 在处理 + 的右操作数时遇到 ;——这不是合法的表达式开头。解析器生成 Expr::Error，报告错误，跳过 token 直到找到 ;（已经在当前位置），消耗它。然后上层继续解析 let y: i64 = 2;，这条语句正常通过。最终输出：

error[E0100]: expected expression, found `;`
  --> test.spr:2:20

warning: expression contains errors, skipping type check for `x`

两条诊断，但第二条语句和 return 都正常解析。程序员看到错误位置，修复 1 + 后面的缺失操作数即可。

如果没有同步机制，解析器可能会把 ; 误认为某个运算符的一部分，或者在缺失的操作数位置开始把 let 当表达式解析，产生一连串毫无意义的错误信息。一个错误变成十个错误，信噪比急剧下降。

同步机制的选择不是唯一的。有些编译器选择在关键字（let、fn、if、while、return）处同步，因为这些关键字几乎总是语句的开头。Sprout 现阶段用分号和右花括号已经足够，后续引入更多语句类型后可以扩展同步点集合。关键原则是：同步点越可靠，恢复后产生虚假错误的概率越低。

错误输出格式

编译器的错误输出采用固定格式，和第 03 篇的词法错误格式一致：

error[ENNNN]: 消息
  --> 文件名:行:列

错误码用 E 前缀加四位数字。表达式相关的错误码从 E0100 开始：

• E0100：期望表达式，实际遇到其他 token
• E0101：未闭合的括号
• E0102：期望运算符或语句结束符

每个错误携带 Span（文件偏移范围），由 --emit=diagnostics 或未来的 LSP 对接使用。错误码的编号空间按编译阶段划分：词法错误用 E00xx，表达式和语句解析用 E01xx，类型检查用 E02xx。这样看到错误码就知道问题出在哪个阶段。

从前置提交到本篇目标

前置：第 03 篇的词法分析器已经能产出完整 token 流，包括运算符 +、-、*、/、<、>、<=、>=、==、!=、&&、||、! 以及括号和标识符。

本篇目标：sproutc --emit=ast programs/expr.spr 能输出正确的 AST 树，运算符优先级和结合性与优先级表一致。故意包含语法错误的文件不会让编译器崩溃，错误消息指向正确的源码位置，且一个错误不会引发后续的级联报告。

最小输入 programs/expr.spr：

fn main() -> i64 {
    return 1 + 2 * 3;
}

预期 AST 输出（简化）：

Function main() -> i64
  Body:
    Return
      Binary(+)
        Literal(1)
        Binary(*)
          Literal(2)
          Literal(3)

练习

推演题：手动跟踪 parse_expr(0) 处理 -a + b * c。画出每次递归调用时的 min_bp 值和返回的子树。最终 AST 应该是什么形状？

代码修改：扩展解析器支持函数调用表达式 f(a, b)。思路如下。

当前缀阶段解析出一个标识符后，检查下一个 token 是否是 (。如果是，进入函数调用解析：消耗 (，循环解析逗号分隔的参数列表（每个参数是一个 parse_expr(0)），最后 expect(TokenKind::RParen)。

TokenKind::Ident(name) => {
    let span = self.advance().span;
    if self.peek() == TokenKind::LParen {
        self.advance(); // 消耗 '('
        let mut args = Vec::new();
        if self.peek() != TokenKind::RParen {
            args.push(self.parse_expr(0));
            while self.peek() == TokenKind::Comma {
                self.advance();
                args.push(self.parse_expr(0));
            }
        }
        self.expect(TokenKind::RParen);
        Expr::Call { name, args, span }
    } else {
        Expr::Var { name, span }
    }
}

注意 parse_expr(0) 传入 0，使得参数内部可以包含任意运算符。f(a + b, c * d) 能正确解析。空参数列表 f() 也能处理——循环不执行，直接遇到 )。

验证方法：解析 f(1 + 2, g(3)) 并检查 AST 是否正确嵌套了两层调用。

---

上一篇：03 - 语句解析：let、赋值和分号
下一篇：05 - 名字、作用域与可变变量