第 6 章：解析表达式（Parsing Expressions）

原文：Robert Nystrom, Crafting Interpreters, Chapter 6。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

语言不是一种基因编码，而是一种逻辑编码。

Stephen R. Anderson

扫描器已将源文本转为记号；解析器的工作是识别这些记号的结构并构建 AST。本章实现表达式解析器。选择的技术是递归下降（recursive descent）：一组相互递归的函数直接映射文法规则。它简单、灵活、错误消息友好，非常适合手写 Lox 解析器。

在上一章，文法像一场从规则出发、生成记号串的游戏；解析则反过来：给定一串记号，找出哪些产生式能够生成它。除了判断输入是否有效，解析器还必须记录每个记号在语言结构中扮演的角色，这正是歧义会造成实际问题的原因。

6.1 歧义与解析游戏（Ambiguity and the Parsing Game）

考虑：

6 / 3 - 1

它可能表示 (6 / 3) - 1，也可能表示 6 / (3 - 1)。两种树都符合“二元表达式由表达式、运算符、表达式组成”的朴素规则，却结果不同。这样的文法是歧义的（ambiguous）。

编程语言通常以两项规则消除歧义：优先级（precedence）决定不同运算符谁先结合，结合性（associativity）决定同优先级运算符的分组方向。Lox 中乘除高于加减，而减法、除法均左结合，因此上式唯一解析为 (6 / 3) - 1。赋值则是右结合的：a = b = c 表示 a = (b = c)。

层级（由低到高）	运算符	结合性
相等	==、!=	左
比较	>、>=、<、<=	左
加减	-、+	左
乘除	/、*	左
一元	!、-	右

少数语言还规定某些运算符彼此没有相对优先级，混用时必须显式加括号；也有非结合运算符，连续使用即为语法错误。Lox 不采用这些规则。我们把原先混在一起的 expression 规则按优先级分层：每条规则匹配本层或更高优先级的表达式；expression 保留为最低层的入口，以便以后只改它就能加入赋值和逻辑运算符。

最直接的二元规则还包含左递归：

factor -> factor ( "/" | "*" ) unary
        | unary ;

递归下降函数若先调用自身，会无限递归而永远不消费输入。因此需要把文法改写成等价、适合自顶向下解析的形式。

6.2 递归下降解析（Recursive Descent Parsing）

解析技术的名字常由 L、R 组合而成，如 LL、LR 和 LALR；还有解析器组合子、Earley、调度场和 packrat 等方法。这里选择递归下降：不需要 Yacc、Bison 或 ANTLR 一类生成器，只用直接书写的代码。它既快速稳健，也足以支持复杂错误处理；GCC、V8、Roslyn 等生产级实现都采用了它。

递归下降是自顶向下（top-down）解析：从最外层 expression 进入，逐步下降至嵌套子表达式和语法树叶子。所谓“下降”指沿文法向内走；这和“高/低优先级”的方向恰好相反，因为低优先级表达式可能包含更高优先级的子表达式。

把表达式按优先级拆成多个层级。最底层先处理原子表达式，越往上优先级越低：

expression     -> equality ;
equality       -> comparison ( ( "!=" | "==" ) comparison )* ;
comparison     -> term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           -> factor ( ( "-" | "+" ) factor )* ;
factor         -> unary ( ( "/" | "*" ) unary )* ;
unary          -> ( "!" | "-" ) unary | primary ;
primary        -> "true" | "false" | "nil" | NUMBER | STRING
                | "(" expression ")" ;

每一层只解析自己负责的运算符，并向下一层取得操作数。例如 term 先解析一个 factor，随后在遇到 + 或 - 时不断读取右侧 factor，从左到右构造二元树。这既编码了优先级，也自然实现左结合。

递归下降是把文法逐字翻译为命令式代码：终结符对应“匹配并消费一个记号”，非终结符对应调用该规则的方法，| 对应 if 或 switch，*、+ 对应循环，? 对应条件分支。规则直接或间接引用自身时，代码便产生递归调用。左递归不适用，是因为方法会在尚未消费任何记号前立即再次调用自己，最终栈溢出。

6.2.1 Parser 类（The Parser Class）

解析器保存记号列表与指向下一个未消费记号的游标：

package com.craftinginterpreters.lox;

import java.util.List;

import static com.craftinginterpreters.lox.TokenType.*;

class Parser {
  private final List<Token> tokens;
  private int current = 0;

  Parser(List<Token> tokens) {
    this.tokens = tokens;
  }

  Expr parse() {
    try {
      return expression();
    } catch (ParseError error) {
      return null;
    }
  }
}

parse() 是入口，目前只解析一条表达式；语句和声明会在后续章节加入。辅助方法负责读取、查看和验证记号：

private boolean match(TokenType... types) {
  for (TokenType type : types) {
    if (check(type)) {
      advance();
      return true;
    }
  }
  return false;
}

private boolean check(TokenType type) {
  if (isAtEnd()) return false;
  return peek().type == type;
}

private Token advance() {
  if (!isAtEnd()) current++;
  return previous();
}

private boolean isAtEnd() {
  return peek().type == EOF;
}

private Token peek() {
  return tokens.get(current);
}

private Token previous() {
  return tokens.get(current - 1);
}

match() 是最常用操作：当前记号属于任一给定类型时就消费并返回 true。check() 只查看而不消费，advance() 则安全前进。保持这些操作小而一致，能大幅降低解析器的越界错误。

6.2.2 解析每一层表达式

入口只是向优先级最高的顶层规则转发：

private Expr expression() {
  return equality();
}

相等性、比较、加减与乘除的结构相同。以 term 为例：

private Expr term() {
  Expr expr = factor();

  while (match(MINUS, PLUS)) {
    Token operator = previous();
    Expr right = factor();
    expr = new Expr.Binary(expr, operator, right);
  }

  return expr;
}

第一次 factor() 产生左操作数；循环每次读取运算符与右操作数，并将旧树作为新 Binary 的左子树。因此 a - b - c 构造为 ((a - b) - c)。

其他层只替换运算符集合和下一层函数：

private Expr equality() {
  Expr expr = comparison();
  while (match(BANG_EQUAL, EQUAL_EQUAL)) {
    Token operator = previous();
    Expr right = comparison();
    expr = new Expr.Binary(expr, operator, right);
  }
  return expr;
}

private Expr comparison() {
  Expr expr = term();
  while (match(GREATER, GREATER_EQUAL, LESS, LESS_EQUAL)) {
    Token operator = previous();
    Expr right = term();
    expr = new Expr.Binary(expr, operator, right);
  }
  return expr;
}

private Expr factor() {
  Expr expr = unary();
  while (match(SLASH, STAR)) {
    Token operator = previous();
    Expr right = unary();
    expr = new Expr.Binary(expr, operator, right);
  }
  return expr;
}

一元表达式右结合：!!true 应为 !(!true)，故匹配前缀运算符后递归调用自身：

private Expr unary() {
  if (match(BANG, MINUS)) {
    Token operator = previous();
    Expr right = unary();
    return new Expr.Unary(operator, right);
  }

  return primary();
}

primary() 处理不能继续按运算符拆分的基础形式：

private Expr primary() {
  if (match(FALSE)) return new Expr.Literal(false);
  if (match(TRUE)) return new Expr.Literal(true);
  if (match(NIL)) return new Expr.Literal(null);

  if (match(NUMBER, STRING)) {
    return new Expr.Literal(previous().literal);
  }

  if (match(LEFT_PAREN)) {
    Expr expr = expression();
    consume(RIGHT_PAREN, "Expect ')' after expression.");
    return new Expr.Grouping(expr);
  }

  throw error(peek(), "Expect expression.");
}

分组的关键是调用完整 expression()，让括号内部可以拥有任意最低优先级表达式；再使用 consume() 要求右括号存在。

6.3 语法错误（Syntax Errors）

解析器有两项职责：对有效记号序列生成语法树；对无效序列发现并报告错误。第二项同样重要。编辑器会在用户仍在输入时反复解析不完整代码，语法错误信息因而是语言用户界面的一部分。解析器无法读懂用户本意，但至少必须发现错误，并且不能崩溃或陷入死循环。

一个称职的解析器还应当足够快、尽量报告互相独立的错误，并避免一个根本错误引发大量幽灵般的级联错误。后两项目标存在张力：恢复得太激进会漏报真实错误，恢复得太保守则会误报。发现错误后继续寻找后续错误的过程称为错误恢复（error recovery）。

解析错误不应让 Java 异常堆栈淹没用户。consume() 在期望记号缺失时报告错误并抛出内部控制流异常：

private Token consume(TokenType type, String message) {
  if (check(type)) return advance();
  throw error(peek(), message);
}

private ParseError error(Token token, String message) {
  Lox.error(token, message);
  return new ParseError();
}

private static class ParseError extends RuntimeException {}

为使错误能精确描述 EOF 与某个记号之前的位置，扩充 Lox.error()：

static void error(Token token, String message) {
  if (token.type == TokenType.EOF) {
    report(token.line, " at end", message);
  } else {
    report(token.line, " at '" + token.lexeme + "'", message);
  }
}

ParseError 不是业务错误对象，而是从多层递归中快速跳出的信号。它不需要消息或堆栈；错误已经报告，parse() 捕获它并返回 null。

6.3.1 恐慌模式恢复（Panic Mode Error Recovery）

真实程序经常有多个错误。发现第一个错误后若继续按原规则解析，常会把后续正确记号误作错误的一部分，产生大量级联诊断。恐慌模式（panic mode）恢复会丢弃输入，直到找到一个看起来可安全重新开始的边界。

传统同步点位于语句之间：分号之后很可能结束了一条语句，而 class、fun、var、for、if、while、print、return 等关键字很可能开始下一条语句。本章尚没有语句，故不会实际调用同步；但先准备好机制。

6.3.2 进入恐慌模式（Entering Panic Mode）

当括号表达式缺少右括号时，consume() 报告错误。error() 返回而不直接抛出 ParseError，让调用点决定是否需要展开调用栈；某些错误（例如函数实参过多）可以报告后继续解析，不必同步。此处的错误会由 primary() 抛出，以便退出不再可信的嵌套规则。

6.3.3 同步递归下降解析器（Synchronizing a Recursive Descent Parser）

递归下降的解析状态存放在 Java 调用栈中，而非某个显式字段。抛出 ParseError 能清除当前嵌套规则的调用帧；未来在语句边界捕获它后，再丢弃记号至同步点。它可能跳过另一个真实错误，但可避免将首个错误的副作用误报为一长串新错误。

synchronize() 先至少消费一个记号，然后跳到分号，或者跳到很可能开启新语句的关键字：

private void synchronize() {
  advance();

  while (!isAtEnd()) {
    if (previous().type == SEMICOLON) return;

    switch (peek().type) {
      case CLASS:
      case FUN:
      case VAR:
      case FOR:
      case IF:
      case WHILE:
      case PRINT:
      case RETURN:
        return;
    }

    advance();
  }
}

这种恢复不能保证找到最佳位置，却能抑制错误洪水并让用户一次看见更多独立问题。同步点是语言设计的一部分：带显式终止符和明显声明关键字的文法，恢复通常更容易。

6.4 接入解析器（Wiring Up the Parser）

现在把解析器放入 Lox.run()：

private static void run(String source) {
  Scanner scanner = new Scanner(source);
  List<Token> tokens = scanner.scanTokens();

  Parser parser = new Parser(tokens);
  Expr expression = parser.parse();

  if (hadError) return;

  System.out.println(new AstPrinter().print(expression));
}

扫描器负责字符到记号，解析器负责记号到 AST，打印器让我们观察 AST。运行：

1 + 2 * (3 - 4) / 5

将输出前缀树：

(+ 1 (/ (* 2 (group (- 3 4))) 5))

树的形状证明优先级与分组已正确编码。下一章将不再打印 AST，而是为每类表达式实现求值。

挑战（Challenges）

1. 在 AstPrinter 中输出与解析器读取的 Lox 源码等价的中缀形式。怎样恰当地添加括号？
2. 加入逗号表达式。它和 C 一样具有最低优先级、左结合；运行时先求值并丢弃左操作数，再求值并返回右操作数。写出文法并实现解析，注意函数调用的参数列表不应把逗号当作该运算符。
3. 加入 C 风格条件（三元）运算符 ?:。? 与 : 之间允许什么优先级的表达式？整个运算符应左结合还是右结合？
4. 为每种二元运算符补充错误产生式：检测表达式开头出现的二元运算符，报告错误，但仍以相应优先级解析并丢弃其右操作数。

设计笔记：逻辑与历史（Logic Versus History）

假设要给 Lox 加入按位 &、|，它们应放在何处？C 及其后继通常把它们放在 == 之下，这常被认为是失误：flags & FLAG_MASK == SOME_FLAG 实际按错误方式分组，必须写成 (flags & FLAG_MASK) == SOME_FLAG。从逻辑上说，把按位运算放得更高能减少括号，并让规则更容易推断。

从逻辑角度看，运算符优先级和结合性只是语法树形状的规则；完全可以设计成不同样子。但现实语言并不在真空中诞生。今天 C 风格的优先级表大量沿袭历史习惯，随后语言为熟悉感继续继承它。

例如按数学直觉，比较运算符和相等运算符的优先级也许可重新设计；&&、||、位运算与赋值的相对位置也有许多可能。然而程序员已经内化现有规则，工具、教材和既有代码也依赖它们。语言设计不仅追求内在一致性，还要尊重使用者的经验与生态成本。

这并不意味着历史永远正确。若旧约定制造普遍错误，或新语言有充分不同的模型，应认真评估改变它的价值。关键是意识到：语法的“自然”感往往不是逻辑必然，而是长期使用形成的习惯。语言设计没有完美答案，只有在内在一致性、学习成本与新语言提供的新价值之间作出的取舍。