第 17 章：编译表达式（Compiling Expressions）

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

在我们人生旅程的中途，我发现自己置身于一片幽暗森林，正直的道路已经迷失。

Dante Alighieri，《神曲：地狱篇》

本章令人兴奋，原因有三：它补完 VM 的执行管线，使源代码能从扫描一路流到执行；我们将写出真正把源代码转为低层二进制指令的编译器；还将实现 Vaughan Pratt 的自顶向下运算符优先级解析（top-down operator precedence parsing）。Pratt 解析优雅地处理前缀、后缀、中缀乃至 mixfix 表达式，以及优先级和结合性。

Pratt 解析在工业界更像口耳相传的传统：许多编译器书偏重生成式解析器，学术界也常忽视它；但手写解析器常见的生产编译器中，许多开发者都从旧编译器前端或同事那里学到了它。

17.1 单遍编译（Single-Pass Compilation）

编译器大致做两件事：解析源代码以理解含义，再生成等价的低层指令。许多实现把它分两遍：解析器生成 AST，代码生成器遍历 AST 输出目标代码。成熟的优化编译器还有更多 pass，甚至如何排列优化 pass 都介于研究课题与黑魔法之间。

clox 采用旧式单遍编译，把两步合并。早期这样做是因为计算机内存不足以保存整份 AST；这里则因为它让 C 编译器更简单。单遍编译要求语言不需要大量上下文来理解当前语法；小而动态的 Lox 很适合这种模式。

因此 compiler.c 同时有熟悉的解析功能（读 token、验证 token 类型）与代码生成功能（输出字节码、将常量写入目标 chunk）。本章先建立两端，再由 Pratt 解析把它们连接起来。

以前 interpret() 执行手写 chunk；现在创建一个空 chunk 交给编译器。编译出错则丢弃它，成功才交给 VM，执行后释放：

// vm.c
InterpretResult interpret(const char* source) {
  Chunk chunk;
  initChunk(&chunk);

  if (!compile(source, &chunk)) {
    freeChunk(&chunk);
    return INTERPRET_COMPILE_ERROR;
  }

  vm.chunk = &chunk;
  vm.ip = vm.chunk->code;
  InterpretResult result = run();

  freeChunk(&chunk);
  return result;
}

对应的编译器接口接收输出位置并报告成功与否：

// compiler.h
#include "vm.h"

bool compile(const char* source, Chunk* chunk);

compile() 先初始化扫描器，预读一个 token，再只解析一条表达式并确保已经到 EOF：

bool compile(const char* source, Chunk* chunk) {
  initScanner(source);
  compilingChunk = chunk;
  parser.hadError = false;
  parser.panicMode = false;

  advance();
  expression();
  consume(TOKEN_EOF, "Expect end of expression.");
  endCompiler();
  return !parser.hadError;
}

本章暂不处理语句，故只接受单个表达式。Pratt 算法依赖递归和一张逐渐增列的大表，最适合从外围基础设施向核心推进。

17.2 解析 Token（Parsing Tokens）

编译器用一对 token 保存一格前瞻：current 是刚从扫描器取得的 token，previous 是已消费、供语义函数读取词素的 token：

typedef struct {
  Token current;
  Token previous;
  bool hadError;
  bool panicMode;
} Parser;

Parser parser;

advance() 取得下一个非错误 token。扫描器不直接报告词法错误，而是返回 TOKEN_ERROR，因此此处循环报告并跳过它们：

static void advance() {
  parser.previous = parser.current;

  for (;;) {
    parser.current = scanToken();
    if (parser.current.type != TOKEN_ERROR) break;
    errorAtCurrent(parser.current.start);
  }
}

consume() 是大多数语法验证的基础：若当前 token 类型符合预期，就前进；否则报告错误：

static void consume(TokenType type, const char* message) {
  if (parser.current.type == type) {
    advance();
    return;
  }
  errorAtCurrent(message);
}

17.2.1 处理语法错误（Handling syntax errors）

诊断函数根据 token 选择显示位置：EOF 显示 at end，扫描器错误 token 不重复显示其消息，其他 token 则显示其词素：

static void errorAt(Token* token, const char* message) {
  if (parser.panicMode) return;
  parser.panicMode = true;

  fprintf(stderr, "[line %d] Error", token->line);
  if (token->type == TOKEN_EOF) {
    fprintf(stderr, " at end");
  } else if (token->type != TOKEN_ERROR) {
    fprintf(stderr, " at '%.*s'", token->length, token->start);
  }
  fprintf(stderr, ": %s\n", message);
  parser.hadError = true;
}

static void errorAtCurrent(const char* message) {
  errorAt(&parser.current, message);
}

static void error(const char* message) {
  errorAt(&parser.previous, message);
}

hadError 决定 compile() 的返回值。panicMode 抑制同一个根因导致的连锁错误：C 没有像 jlox 那样用于展开解析栈的异常，setjmp()/longjmp() 又容易破坏内存与不变量，所以先继续解析、但不再显示附带错误。后续加入语句后，会在语句边界同步并清除 panic mode。

17.3 发射字节码（Emitting Bytecode）

编译器向 compile() 传入的 chunk 写字节。暂时将其保存在模块变量中，再用 currentChunk() 封装访问；以后编译函数时，“当前 chunk”会变复杂，这个包装可避免重写调用方：

Chunk* compilingChunk;

static Chunk* currentChunk() {
  return compilingChunk;
}

static void emitByte(uint8_t byte) {
  writeChunk(currentChunk(), byte, parser.previous.line);
}

static void emitBytes(uint8_t byte1, uint8_t byte2) {
  emitByte(byte1);
  emitByte(byte2);
}

字节既可能是 opcode，也可能是操作数；行号取自 previous，供运行时错误定位。脚本完成时暂用 OP_RETURN 输出表达式结果：

static void emitReturn() {
  emitByte(OP_RETURN);
}

static void endCompiler() {
  emitReturn();
}

常量先进入 chunk 的常量表，随后发射 OP_CONSTANT 和一字节索引。单字节索引限制每个 chunk 只能有 256 个常量：

static uint8_t makeConstant(Value value) {
  int constant = addConstant(currentChunk(), value);
  if (constant > UINT8_MAX) {
    error("Too many constants in one chunk.");
    return 0;
  }
  return (uint8_t)constant;
}

static void emitConstant(Value value) {
  emitBytes(OP_CONSTANT, makeConstant(value));
}

真实实现应增加两字节索引的 OP_CONSTANT_16 等指令，但本书为聚焦关键机制而省略。

17.4 解析前缀表达式（Parsing Prefix Expressions）

前缀表达式可从第一个 token 判断类型。本章先支持数字、分组、单目负号和四则运算。不同 token 对应的编译函数，最终放进按 TokenType 索引的函数指针表中。

17.4.1 Token 的解析函数（Parsers for tokens）

数字 token 已被消费并保存在 previous，strtod() 将其词素转换成 double，再写入常量表：

static void number() {
  double value = strtod(parser.previous.start, NULL);
  emitConstant(value);
}

这里 strtod() 可直接从原始源字符串开始转换，因为数值字面量后面的字符不属于数字，它自然停止。词素到运行时值的转换被延迟到编译阶段，保持扫描器无需了解 Value。

17.4.2 用圆括号分组（Parentheses for grouping）

( 已被消费，分组函数递归编译内部表达式并要求配对右括号：

static void grouping() {
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after expression.");
}

分组只有语法作用，让低优先级表达式出现在高优先级位置；它没有独立运行时语义，不发射任何字节码，内部 expression() 完成全部工作。

17.4.3 单目取负（Unary negation）

单目 - 也以前缀 token 开始。运行时必须先计算操作数、再取负，因此 OP_NEGATE 在操作数字节码之后发射：

static void unary() {
  TokenType operatorType = parser.previous.type;

  // 只编译优先级至少为 unary 的操作数。
  parsePrecedence(PREC_UNARY);

  switch (operatorType) {
    case TOKEN_MINUS: emitByte(OP_NEGATE); break;
    default: return; // 不可达。
  }
}

若简单调用 expression()，-a.b + c 会错误地把整个 a.b + c 当作负号操作数。parsePrecedence(PREC_UNARY) 只允许不低于单目优先级的表达式，故正确编译 -a.b 并在 + 停止。多行单目表达式中，当前简化实现会把运行时错误关联到操作数行而非 - 行；更严谨的实现可在递归前保存运算符行号。

优先级由低到高排列：

typedef enum {
  PREC_NONE,
  PREC_ASSIGNMENT, // =
  PREC_OR,         // or
  PREC_AND,        // and
  PREC_EQUALITY,   // == !=
  PREC_COMPARISON, // < > <= >=
  PREC_TERM,       // + -
  PREC_FACTOR,     // * /
  PREC_UNARY,      // ! -
  PREC_CALL,       // . ()
  PREC_PRIMARY
} Precedence;

17.5 解析中缀表达式（Parsing Infix Expressions）

中缀表达式不同：只有先解析完左操作数、再遇到中间运算符时，才知道自己正处在一个二元表达式中。以 1 + 2 为例：顶层解析先将 1 编译为常量；此时下一个 token 是 +，解析器据此将已经完成的 1 视作左操作数，并继续处理右侧。

所有算术中缀运算共用 binary()：左操作数已编译，其值在运行时会留在栈中；函数编译右操作数，最后发射操作码：

static void binary() {
  TokenType operatorType = parser.previous.type;
  ParseRule* rule = getRule(operatorType);

  // +1 使同级运算符左结合。
  parsePrecedence((Precedence)(rule->precedence + 1));

  switch (operatorType) {
    case TOKEN_PLUS:  emitByte(OP_ADD); break;
    case TOKEN_MINUS: emitByte(OP_SUBTRACT); break;
    case TOKEN_STAR:  emitByte(OP_MULTIPLY); break;
    case TOKEN_SLASH: emitByte(OP_DIVIDE); break;
    default: return;
  }
}

2 * 3 + 4 中，解析 * 的右侧时要只吃 3 而不吃 + 4，因为加法优先级较低。右操作数使用“当前操作符优先级加一”，使 1 + 2 + 3 + 4 解析为 ((1 + 2) + 3) + 4，即左结合。若操作符是右结合的赋值，右侧应使用相同优先级，得到 a = (b = (c = d))。

17.6 Pratt 解析器（A Pratt Parser）

Pratt 表的每一行描述某种 token：它能启动什么前缀表达式、能连接什么中缀表达式，以及作为中缀操作符的优先级：

typedef void (*ParseFn)();

typedef struct {
  ParseFn prefix;
  ParseFn infix;
  Precedence precedence;
} ParseRule;

函数指针语法难读，故用 typedef 隐藏。表以 C99 指定初始化器按 token 枚举值对齐：

ParseRule rules[] = {
  [TOKEN_LEFT_PAREN]    = {grouping, NULL,   PREC_NONE},
  [TOKEN_RIGHT_PAREN]   = {NULL,     NULL,   PREC_NONE},
  [TOKEN_LEFT_BRACE]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_RIGHT_BRACE]   = {NULL,     NULL,   PREC_NONE},
  [TOKEN_COMMA]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_DOT]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_MINUS]         = {unary,    binary, PREC_TERM},
  [TOKEN_PLUS]          = {NULL,     binary, PREC_TERM},
  [TOKEN_SEMICOLON]     = {NULL,     NULL,   PREC_NONE},
  [TOKEN_SLASH]         = {NULL,     binary, PREC_FACTOR},
  [TOKEN_STAR]          = {NULL,     binary, PREC_FACTOR},
  [TOKEN_BANG]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_BANG_EQUAL]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_EQUAL]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_EQUAL_EQUAL]   = {NULL,     NULL,   PREC_NONE},
  [TOKEN_GREATER]       = {NULL,     NULL,   PREC_NONE},
  [TOKEN_GREATER_EQUAL] = {NULL,     NULL,   PREC_NONE},
  [TOKEN_LESS]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_LESS_EQUAL]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_IDENTIFIER]    = {NULL,     NULL,   PREC_NONE},
  [TOKEN_STRING]        = {NULL,     NULL,   PREC_NONE},
  [TOKEN_NUMBER]        = {number,   NULL,   PREC_NONE},
  [TOKEN_AND]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_CLASS]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_ELSE]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_FALSE]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_FOR]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_FUN]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_IF]            = {NULL,     NULL,   PREC_NONE},
  [TOKEN_NIL]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_OR]            = {NULL,     NULL,   PREC_NONE},
  [TOKEN_PRINT]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_RETURN]        = {NULL,     NULL,   PREC_NONE},
  [TOKEN_SUPER]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_THIS]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_TRUE]          = {NULL,     NULL,   PREC_NONE},
  [TOKEN_VAR]           = {NULL,     NULL,   PREC_NONE},
  [TOKEN_WHILE]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_ERROR]         = {NULL,     NULL,   PREC_NONE},
  [TOKEN_EOF]           = {NULL,     NULL,   PREC_NONE},
};

static ParseRule* getRule(TokenType type) {
  return &rules[type];
}

未填充的单元格表示该 token 当前不能出现在对应位置，或该语言特性尚未加入。表也清楚展示哪些 token 已被语法占用、哪些仍可扩展。

17.6.1 按优先级解析（Parsing with precedence）

核心算法极小：先读取一个 token 并调用它的前缀函数；随后只要当前 token 是优先级不低于阈值的中缀运算符，就消费它并调用中缀函数：

static void parsePrecedence(Precedence precedence) {
  advance();
  ParseFn prefixRule = getRule(parser.previous.type)->prefix;
  if (prefixRule == NULL) {
    error("Expect expression.");
    return;
  }

  prefixRule();

  while (precedence <= getRule(parser.current.type)->precedence) {
    advance();
    ParseFn infixRule = getRule(parser.previous.type)->infix;
    infixRule();
  }
}

static void expression() {
  parsePrecedence(PREC_ASSIGNMENT);
}

第一个 token 按定义总是某个前缀表达式的一部分。前缀函数完成后，已编译表达式可能成为下一个中缀函数的左操作数。循环不断吸收允许的中缀运算符与其操作数，直到遇到非中缀 token 或优先级过低的 token。

后面加入赋值时会调整少量代码，但 parsePrecedence() 的主体已覆盖本书后续所有表达式编译需求。

17.7 转储 Chunk（Dumping Chunks）

为调试生成的字节码，加入只供开发者使用的开关：

// common.h
#define DEBUG_PRINT_CODE

编译结束时仅在没有语法错误时反汇编 chunk。错误后仍会生成一些不会执行的破损代码，打印它只会误导调试：

// compiler.c
#ifdef DEBUG_PRINT_CODE
#include "debug.h"
#endif

static void endCompiler() {
  emitReturn();

#ifdef DEBUG_PRINT_CODE
  if (!parser.hadError) {
    disassembleChunk(currentChunk(), "code");
  }
#endif
}

至此解释器已真正包含扫描、解析、编译为字节码与执行四个阶段。虽然眼下只是一个重度工程化的算术计算器，语言其余功能所需的基础已经就位。

挑战（Challenges）

1. 跟踪解析器如何处理 (-1 + 2) * 3 - -4：列出 parsePrecedence() 与表中解析函数的调用顺序、调用关系和参数。
2. TOKEN_MINUS 同时有前缀函数和中缀函数。完整 Lox 中还有哪些 token 能同时出现在前缀与中缀位置？C 或其他语言中又有哪些？
3. C 的条件运算符 ?: 是有多个操作数的 mixfix 表达式。为它接入解析器即可，无需生成字节码：应在表中怎样注册，又如何解析各操作数？

设计笔记：它终究只是解析（Design Note: It's Just Parsing）

作者提出一个可能惹恼编译器爱好者的主张：解析并不那么重要。解析理论、parser generator、LALR、组合子解析、packrat 解析和复杂度分析都很有价值；若实现语言，确实应保证解析器不会在诡异边界输入上跑七千年。但若目标是把语言交付给用户，过度追逐最新的前端技术，往往不会为用户增加价值。

“手里只有锤子，看什么都像钉子”的倾向在语言工具中尤其常见：编译器开发者很容易为每个问题创造新小语言；Yacc 一类“用编译器写编译器”的工具又是这种递归冲动最可爱的例子。它们不是错，只是不应替代产品判断。

若只需完成一个解析器，选择一种常规技术然后继续前进就好：递归下降、Pratt 解析、ANTLR 或 Bison 都可以。省下不反复重写解析代码的时间，应该优先投入到高质量编译错误处理与报告中。对用户而言，清晰、有位置、可恢复的错误信息通常比前端内部采用何种炫目算法更有价值。