第 16 章：按需扫描（Scanning on Demand）

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

文学是用二十六个语音符号、十个阿拉伯数字和大约八种标点符号，在水平方向上做出的独特排列。

Kurt Vonnegut，《Like Shaking Hands With God》

第二个解释器 clox 有扫描器、编译器和虚拟机三个阶段。扫描器向编译器送出 token，编译器向 VM 送出字节码 chunk。我们已经从 chunk 与 VM 开始实现，现在回到开头，构建生成 token 的扫描器；下一章会用字节码编译器把两端连接起来。

本章和 jlox 的扫描器难免有些重复，但 C 版也有几个重要差异：它按需产生 token、不为词素分配内存，并以小型字典树识别关键字。

16.1 启动解释器（Spinning Up the Interpreter）

有了前端，就能让 clox 像真正的解释器一样运行，不再手写字节码 chunk。main() 支持 REPL 和脚本文件：

// main.c
int main(int argc, const char* argv[]) {
  initVM();

  if (argc == 1) {
    repl();
  } else if (argc == 2) {
    runFile(argv[1]);
  } else {
    fprintf(stderr, "Usage: clox [path]\n");
    exit(64);
  }

  freeVM();
  return 0;
}

没有命令行参数时进入 REPL，一个参数则视为待运行脚本的路径。判断的是 argc == 1 与 argc == 2，因为 argv[0] 始终是可执行文件名。所需标准头文件为：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "common.h"

REPL 的实现保持刻意简朴：

static void repl() {
  char line[1024];
  for (;;) {
    printf("> ");
    if (!fgets(line, sizeof(line), stdin)) {
      printf("\n");
      break;
    }
    interpret(line);
  }
}

生产质量的 REPL 应处理跨行输入，也不应硬编码行长；本书只需足以驱动解释器。脚本加载则读取整个文件、解释、释放源字符串，并依错误类型返回合适进程退出码：

static void runFile(const char* path) {
  char* source = readFile(path);
  InterpretResult result = interpret(source);
  free(source);

  if (result == INTERPRET_COMPILE_ERROR) exit(65);
  if (result == INTERPRET_RUNTIME_ERROR) exit(70);
}

readFile() 动态分配源字符串，所有权交给调用者。因此 runFile() 必须在 interpret() 返回后才释放它：扫描 token 直接借用这块字符串的范围。C 要求程序员不仅显式管理内存，还要在脑中维护所有权规则；这正是其简洁模型的代价。

static char* readFile(const char* path) {
  FILE* file = fopen(path, "rb");
  if (file == NULL) {
    fprintf(stderr, "Could not open file \"%s\".\n", path);
    exit(74);
  }

  fseek(file, 0L, SEEK_END);
  size_t fileSize = ftell(file);
  rewind(file);

  char* buffer = (char*)malloc(fileSize + 1);
  if (buffer == NULL) {
    fprintf(stderr, "Not enough memory to read \"%s\".\n", path);
    exit(74);
  }

  size_t bytesRead = fread(buffer, sizeof(char), fileSize, file);
  if (bytesRead < fileSize) {
    fprintf(stderr, "Could not read file \"%s\".\n", path);
    exit(74);
  }
  buffer[bytesRead] = '\0';
  fclose(file);
  return buffer;
}

它先 fseek() 到末尾，再用 ftell() 得到文件大小，回到开头后一次性分配、读取。大小必须加一以放入结尾的 \0。打开文件、分配与读取都要检查失败；fseek()、ftell()、rewind() 也可能失败，但本书不再把这一示例扩展得更深入。

16.1.1 打开编译管线（Opening the compilation pipeline）

我们已获得 Lox 源字符串，接下来建立“扫描 -> 编译 -> 执行”的管线：

interpret() 不再接收 Chunk*，而接收源字符串：

// vm.h
InterpretResult interpret(const char* source);

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

InterpretResult interpret(const char* source) {
  compile(source);
  return INTERPRET_OK;
}

编译器模块暂时只搭起签名：

// compiler.h
#ifndef clox_compiler_h
#define clox_compiler_h

void compile(const char* source);

#endif

// compiler.c
#include <stdio.h>

#include "common.h"
#include "compiler.h"
#include "scanner.h"

void compile(const char* source) {
  initScanner(source);
}

签名会在下一章改变；当前编译的第一阶段只是初始化扫描器。

16.1.2 扫描器开始扫描（The scanner scans）

扫描器保存极少状态：当前词素起点、当前待检查字符和行号。

// scanner.c
typedef struct {
  const char* start;
  const char* current;
  int line;
} Scanner;

Scanner scanner;

void initScanner(const char* source) {
  scanner.start = source;
  scanner.current = source;
  scanner.line = 1;
}

它甚至不保存源字符串开头的额外指针：只向前扫描一次，完成即结束。和 VM 一样，使用模块级状态是为了让本书代码简短；可嵌入、多实例的实际实现应把 Scanner* 显式传递。

16.2 每次一个 Token（A Token at a Time）

jlox 一次扫描整个程序并返回 token 列表。对 C 版而言，这需要可增长容器、token 和容器自身的分配释放，既增加代码，也增加内存活动。编译器任意时刻只需一两个 token，文法只需要单 token 前瞻，因此最简单的办法是：等编译器请求时再扫描。

扫描器按值返回 token，不需要动态分配；token 在 C 栈上自由复制。先定义 token 类型与结构：

// scanner.h
typedef enum {
  // 单字符 token。
  TOKEN_LEFT_PAREN, TOKEN_RIGHT_PAREN,
  TOKEN_LEFT_BRACE, TOKEN_RIGHT_BRACE,
  TOKEN_COMMA, TOKEN_DOT, TOKEN_MINUS, TOKEN_PLUS,
  TOKEN_SEMICOLON, TOKEN_SLASH, TOKEN_STAR,
  // 一或两个字符的 token。
  TOKEN_BANG, TOKEN_BANG_EQUAL,
  TOKEN_EQUAL, TOKEN_EQUAL_EQUAL,
  TOKEN_GREATER, TOKEN_GREATER_EQUAL,
  TOKEN_LESS, TOKEN_LESS_EQUAL,
  // 字面量。
  TOKEN_IDENTIFIER, TOKEN_STRING, TOKEN_NUMBER,
  // 关键字。
  TOKEN_AND, TOKEN_CLASS, TOKEN_ELSE, TOKEN_FALSE,
  TOKEN_FOR, TOKEN_FUN, TOKEN_IF, TOKEN_NIL, TOKEN_OR,
  TOKEN_PRINT, TOKEN_RETURN, TOKEN_SUPER, TOKEN_THIS,
  TOKEN_TRUE, TOKEN_VAR, TOKEN_WHILE,
  TOKEN_ERROR, TOKEN_EOF
} TokenType;

typedef struct {
  TokenType type;
  const char* start;
  int length;
  int line;
} Token;

void initScanner(const char* source);
Token scanToken();

除 C 的枚举值位于顶层命名空间而加了 TOKEN_ 前缀外，该集合基本等同 jlox。额外的 TOKEN_ERROR 表示未闭合字符串或无法识别字符：扫描器不直接报错，而是把合成错误 token 交给编译器，使编译器能负责诊断与恢复。

词素不是一个独立字符串，而是源字符串中的起始指针加长度。这样无需管理词素内存，token 可以随意复制；前提是源字符串活得比所有 token 长，这正是前节中延迟 free(source) 的原因。

暂时用以下驱动代码观察 token：

void compile(const char* source) {
  initScanner(source);
  int line = -1;
  for (;;) {
    Token token = scanToken();
    if (token.line != line) {
      printf("%4d ", token.line);
      line = token.line;
    } else {
      printf("   | ");
    }
    printf("%2d '%.*s'\n", token.type, token.length, token.start);
    if (token.type == TOKEN_EOF) break;
  }
}

%.*s 的 * 表示精度由参数提供，故能只打印 token.start 开始的 token.length 个字符；词素是源字符串内的范围，末尾没有自己的 \0。例如 print 1 + 2; 会打印逐个 token，最后在第二行得到空词素的 EOF token。

16.2.1 扫描 token（Scanning tokens）

核心入口每次返回下一个 token：

Token scanToken() {
  skipWhitespace();
  scanner.start = scanner.current;

  if (isAtEnd()) return makeToken(TOKEN_EOF);

  char c = advance();
  if (isAlpha(c)) return identifier();
  if (isDigit(c)) return number();

  // 按标点、运算符与字符串分类。
  return errorToken("Unexpected character.");
}

进入函数时必处于新 token 开始处，因此 start 先指向 current。空源末尾的 EOF 是哨兵，通知编译器停止请求。辅助函数如下：

static bool isAtEnd() {
  return *scanner.current == '\0';
}

static char advance() {
  scanner.current++;
  return scanner.current[-1];
}

static Token makeToken(TokenType type) {
  Token token;
  token.type = type;
  token.start = scanner.start;
  token.length = (int)(scanner.current - scanner.start);
  token.line = scanner.line;
  return token;
}

static Token errorToken(const char* message) {
  Token token;
  token.type = TOKEN_ERROR;
  token.start = message;
  token.length = (int)strlen(message);
  token.line = scanner.line;
  return token;
}

errorToken() 的“词素”指向错误消息而非用户源代码。调用点只传 C 字符串字面量，它们在整个程序运行期间都有效。

16.3 Lox 的词法语法（A Lexical Grammar for Lox）

先识别单字符 token：

switch (c) {
  case '(': return makeToken(TOKEN_LEFT_PAREN);
  case ')': return makeToken(TOKEN_RIGHT_PAREN);
  case '{': return makeToken(TOKEN_LEFT_BRACE);
  case '}': return makeToken(TOKEN_RIGHT_BRACE);
  case ';': return makeToken(TOKEN_SEMICOLON);
  case ',': return makeToken(TOKEN_COMMA);
  case '.': return makeToken(TOKEN_DOT);
  case '-': return makeToken(TOKEN_MINUS);
  case '+': return makeToken(TOKEN_PLUS);
  case '/': return makeToken(TOKEN_SLASH);
  case '*': return makeToken(TOKEN_STAR);
}

一或两个字符的运算符要条件性读取第二个字符：

static bool match(char expected) {
  if (isAtEnd()) return false;
  if (*scanner.current != expected) return false;
  scanner.current++;
  return true;
}

case '!': return makeToken(match('=') ? TOKEN_BANG_EQUAL : TOKEN_BANG);
case '=': return makeToken(match('=') ? TOKEN_EQUAL_EQUAL : TOKEN_EQUAL);
case '<': return makeToken(match('=') ? TOKEN_LESS_EQUAL : TOKEN_LESS);
case '>': return makeToken(match('=') ? TOKEN_GREATER_EQUAL : TOKEN_GREATER);

如果未匹配，match() 不消耗字符，使其仍属于下一个 token。

16.3.1 空白（Whitespace）

空格、制表符、回车、换行都不进入词素。把它们放进 skipWhitespace()，可使主扫描函数返回时稳定地处于下一个有意义字符：

static char peek() {
  return *scanner.current;
}

static void skipWhitespace() {
  for (;;) {
    char c = peek();
    switch (c) {
      case ' ':
      case '\r':
      case '\t':
        advance();
        break;
      case '\n':
        scanner.line++;
        advance();
        break;
      default:
        return;
    }
  }
}

peek() 只查看而不消耗，因此这个小扫描器不会意外跳过非空白字符。

16.3.2 注释（Comments）

注释并非严格意义的空白，但对 Lox 可与空白一样跳过。// 一直延续到行尾：

static char peekNext() {
  if (isAtEnd()) return '\0';
  return scanner.current[1];
}

case '/':
  if (peekNext() == '/') {
    while (peek() != '\n' && !isAtEnd()) advance();
  } else {
    return;
  }
  break;

若第二个字符不是 /，不能消耗第一个 /，因为它本身是 TOKEN_SLASH。注释扫描不消费换行，让外层循环统一递增行号。

16.3.3 字面量 token（Literal tokens）

字符串从双引号开始，支持多行：

case '"': return string();

static Token string() {
  while (peek() != '"' && !isAtEnd()) {
    if (peek() == '\n') scanner.line++;
    advance();
  }

  if (isAtEnd()) return errorToken("Unterminated string.");
  advance(); // 结尾引号。
  return makeToken(TOKEN_STRING);
}

与 jlox 最大的不同是它不在扫描阶段把词素转换为运行时值。C 中为 token 携带字符串或 double 值会需要联合、类型标签和字符串内存管理；clox 保持 token 只表示源代码，在编译器正要把值放入常量表时才转换。少许扫描与转换的重复不处于性能敏感路径，换来更简单的扫描器。

数字先消耗整数部分，只有点号后确实有数字时才吸收小数部分：

static bool isDigit(char c) {
  return c >= '0' && c <= '9';
}

static Token number() {
  while (isDigit(peek())) advance();

  if (peek() == '.' && isDigit(peekNext())) {
    advance();
    while (isDigit(peek())) advance();
  }
  return makeToken(TOKEN_NUMBER);
}

故 123.45 是数字，123. 则是数字 123 与点号两个 token。

16.4 标识符和关键字（Identifiers and Keywords）

最后是用户定义与保留的名称。标识符以 ASCII 字母或下划线开头，之后可包含数字：

static bool isAlpha(char c) {
  return (c >= 'a' && c <= 'z') ||
         (c >= 'A' && c <= 'Z') || c == '_';
}

static Token identifier() {
  while (isAlpha(peek()) || isDigit(peek())) advance();
  return makeToken(identifierType());
}

scanToken() 在 advance() 后先检查 isAlpha(c)，再检查 isDigit(c)，其余字符才交给 switch。关键字识别是本章独特之处。

jlox 用 Java Map 查关键字；clox 还没有哈希表，即使有也过度了：计算哈希、定位桶、比较字符串，对大多数绝非关键字的标识符做了过多工作。若名字以 g 开头，Lox 没有任何关键字以 g 开头，只看第一个字符即可判定它不是关键字；即使是 forest，通常检查几个字符也足够排除。

16.4.1 字典树与状态机（Tries and state machines）

图展示的是字典树（trie）：一个字符串是字符节点树上的一条路径；末字符节点带特殊终结标记，因此树同时有 ban 与 banquet 时仍能区分 banque。trie 一词来自 retrieval，原意读作“tree”，但容易与 tree 混淆，今天常读作“try”。

它还是确定有限自动机（DFA，也称有限状态机）的特殊情形。DFA 有状态与转换，任一时刻只在一个状态；用于词法分析时，转换匹配字符，状态表示允许的字符集合。DFA 可以是任意图而非树，转换也可有环，因而能识别任意长度的字符串。

这种图叫语法图或铁路图。理论上可构造一个识别全部 Lox token 的大 DFA；Lex 工具正是把正则表达式描述自动转换为 DFA 并产生 C 代码。许多正则表达式引擎也以相似方式工作。这里已有合适的手写扫描器，只需为关键字实现小 trie。

最简单的映射是嵌套 switch。对于只有一个关键字的首字母，使用 checkKeyword()：

static TokenType checkKeyword(int start, int length,
                              const char* rest, TokenType type) {
  if (scanner.current - scanner.start == start + length &&
      memcmp(scanner.start + start, rest, length) == 0) {
    return type;
  }
  return TOKEN_IDENTIFIER;
}

static TokenType identifierType() {
  switch (scanner.start[0]) {
    case 'a': return checkKeyword(1, 2, "nd", TOKEN_AND);
    case 'c': return checkKeyword(1, 4, "lass", TOKEN_CLASS);
    case 'e': return checkKeyword(1, 3, "lse", TOKEN_ELSE);
    case 'i': return checkKeyword(1, 1, "f", TOKEN_IF);
    case 'n': return checkKeyword(1, 2, "il", TOKEN_NIL);
    case 'o': return checkKeyword(1, 1, "r", TOKEN_OR);
    case 'p': return checkKeyword(1, 4, "rint", TOKEN_PRINT);
    case 'r': return checkKeyword(1, 5, "eturn", TOKEN_RETURN);
    case 's': return checkKeyword(1, 4, "uper", TOKEN_SUPER);
    case 'v': return checkKeyword(1, 2, "ar", TOKEN_VAR);
    case 'w': return checkKeyword(1, 4, "hile", TOKEN_WHILE);
  }
  return TOKEN_IDENTIFIER;
}

该函数同时检查词素长度和余下字符，避免把 sup、superb 或 supar 误判为 super。f 分叉到 false、for、fun，t 分叉到 this、true：

case 'f':
  if (scanner.current - scanner.start > 1) {
    switch (scanner.start[1]) {
      case 'a': return checkKeyword(2, 3, "lse", TOKEN_FALSE);
      case 'o': return checkKeyword(2, 1, "r", TOKEN_FOR);
      case 'u': return checkKeyword(2, 1, "n", TOKEN_FUN);
    }
  }
  break;
case 't':
  if (scanner.current - scanner.start > 1) {
    switch (scanner.start[1]) {
      case 'h': return checkKeyword(2, 2, "is", TOKEN_THIS);
      case 'r': return checkKeyword(2, 2, "ue", TOKEN_TRUE);
    }
  }
  break;

短小的嵌套 switch 做的是判定关键字所需的最少工作，一旦确定不是关键字就停止。性能并不总要靠复杂数据结构、缓存层或花哨优化；很多时候，简单代码少做工作就足够了。至此扫描器完成。

挑战（Challenges）

1. 许多新语言支持字符串插值：字符串中的 ${ 与 } 包围任意表达式。例如：

   var drink = "Tea";
   var steep = 4;
   var cool = 2;
   print "${drink} will be ready in ${steep + cool} minutes.";

   它应输出 Tea will be ready in 6 minutes.。为插值定义 token 类型，并写出此字符串及 "Nested ${ interpolation?! Are you ${ mad?! } }" 应产生的 token 序列；可考察其他语言如何处理嵌套插值。

2. 一些语言既用尖括号表示泛型，又有右移运算符，早期 C++ 会把 vector<vector<string>> nestedVectors; 中的 >> 扫成一个右移 token，用户被迫在两个 > 之间加空格。较新的 C++、Java、C# 如何规定和实现这种情况？

3. 许多成熟语言具有上下文关键字：例如 C# 的 await 在 async 方法中是关键字，其他方法中可作普通标识符。列举其他例子，分析其利弊，并设计前端中实现它们的方式。