第 4 章：扫描（Scanning）

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

大口去吃。凡是值得做的事，都值得做过头。

Robert A. Heinlein，《Time Enough for Love》

每个编译器或解释器的第一步都是扫描（scanning）。扫描器把原始源代码看作字符序列，分组成一串称为记号（token）的块；它们是构成语言文法的有意义“单词”和“标点”。

扫描也叫 lexing，后者是 lexical analysis（词法分析）的简称。早期内存稀缺时，“scanner”有时特指从磁盘读取、缓冲字符的代码，而 lexing 才是使用这些字符的后续阶段。如今把源文件读进内存微不足道，两词基本可互换。

扫描很适合作为起点：代码并不困难，几乎只是一个自我感觉良好的 switch 语句。它能让我们在进入更有趣的主题前热身。本章结束时，会有一个完整而快速的扫描器：接收任意 Lox 源码字符串，产生下一章解析器要消费的记号。

4.1 解释器框架（The Interpreter Framework）

开始扫描前，先勾勒 Java 版解释器 jlox 的基本形状。所有内容从一个 Java 类开始：

package com.craftinginterpreters.lox;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;

public class Lox {
  static boolean hadError = false;

  public static void main(String[] args) throws IOException {
    if (args.length > 1) {
      System.out.println("Usage: jlox [script]");
      System.exit(64);
    } else if (args.length == 1) {
      runFile(args[0]);
    } else {
      runPrompt();
    }
  }
}

Lox 是脚本语言，直接从源代码执行。jlox 支持两种方式：命令行给出文件路径时读取并执行文件；没有参数时进入交互式提示符，一次输入并执行一行代码。

参数错误使用退出码 64，这是 POSIX sysexits.h 中 EX_USAGE 的惯例。书中不强调跨平台命令行框架；重点是给用户一个清楚的脚本与 REPL 入口。

private static void runFile(String path) throws IOException {
  byte[] bytes = Files.readAllBytes(Paths.get(path));
  run(new String(bytes, Charset.defaultCharset()));

  if (hadError) System.exit(65);
}

private static void runPrompt() throws IOException {
  InputStreamReader input = new InputStreamReader(System.in);
  BufferedReader reader = new BufferedReader(input);

  for (;;) {
    System.out.print("> ");
    String line = reader.readLine();
    if (line == null) break;
    run(line);
    hadError = false;
  }
}

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

  // 目前只显示扫描结果；后续章节会把记号交给解析器。
  for (Token token : tokens) {
    System.out.println(token);
  }
}

交互提示符通常也称 REPL，意思是 Read、Evaluate、Print、Loop：读取输入、求值、打印结果、再循环。readLine() 在终端遇到 EOF（通常按 Ctrl-D）时返回 null，于是退出循环。

REPL 的“Print”暂时只是扫描阶段打印 token，后续会改为显示执行结果。每次输入后清除 hadError，否则上一行的错误会阻止下一行正确代码运行；文件执行则保留错误状态，并用退出码 65 表示数据格式错误。

4.1.1 错误处理（Error Handling）

可用语言的错误处理至关重要。用户代码正常时，用户想的是自己的程序；通常只有出错时才会注意到语言实现。因此实现必须提供理解问题并回到正确方向所需的信息，错误处理应从一开始贯穿整个解释器。

static void error(int line, String message) {
  report(line, "", message);
}

private static void report(int line, String where, String message) {
  System.err.println(
      "[line " + line + "] Error" + where + ": " + message);
  hadError = true;
}

至少必须指出错误所在行。更好的诊断会给出起止列，甚至展示问题行与插入符号；但这些字符串处理代码很多、对本书核心不够有趣，因此 jlox 暂只显示行号。自己的解释器应当做得更好。

把报告代码放在 Lox 中也体现一个工程原则：产生错误与呈现错误要分离。扫描器、解析器等前端阶段负责检测错误，不应知道错误最终显示到 stderr、IDE 面板还是日志文件。完整实现可通过 ErrorReporter 接口替换不同报告策略；本书的最小实现没有引入该抽象。

扫描阶段尚不能精确知道某些错误的位置，后续解析阶段会把 token 前后文传给 report()，从而将错误显示为 at 'token' 一类信息。无论在哪个阶段，报告后都设置全局错误标记，以阻止执行语义可能已不可信的程序。

4.2 词素与记号（Lexemes and Tokens）

考虑：

var language = "lox";

var 三个字符共同有含义，而从 language 中任取 g-u-a 则没有。词法分析的工作，是把字符分成仍有意义的最小序列，每个序列称为词素（lexeme）。上例的词素是 var、language、=、"lox" 与 ;。

词素只是源代码的原始子串。扫描时还能获得其他有用信息；把词素与这些信息捆在一起，才得到记号。

4.2.1 记号类型（Token Type）

解析器不只要知道看见了某个标识符，还要知道它是否为保留字，以及究竟是哪一个关键字。例如它需要能表达“如果下一个记号是 while，则……”的逻辑。让解析器每次比较原始字符串既慢又丑，因此扫描器为每个记号赋予类型。

package com.craftinginterpreters.lox;

enum TokenType {
  // 单字符记号。
  LEFT_PAREN, RIGHT_PAREN, LEFT_BRACE, RIGHT_BRACE,
  COMMA, DOT, MINUS, PLUS, SEMICOLON, SLASH, STAR,

  // 一个或两个字符的记号。
  BANG, BANG_EQUAL, EQUAL, EQUAL_EQUAL,
  GREATER, GREATER_EQUAL, LESS, LESS_EQUAL,

  // 字面量。
  IDENTIFIER, STRING, NUMBER,

  // 关键字。
  AND, CLASS, ELSE, FALSE, FUN, FOR, IF, NIL, OR,
  PRINT, RETURN, SUPER, THIS, TRUE, VAR, WHILE,

  EOF
}

4.2.2 字面量值（Literal Value）

记号还可能保存字面量实际值。"hi" 的词素包含引号，运行时却只需要字符串 hi；数字 123 的词素是文本，解释器需要数值 123.0。这里用 Java 的 Object 暂存各种值，代价是失去静态类型保证，但在 Lox 动态类型值模型出现前很实用。

package com.craftinginterpreters.lox;

class Token {
  final TokenType type;
  final String lexeme;
  final Object literal;
  final int line;

  Token(TokenType type, String lexeme, Object literal, int line) {
    this.type = type;
    this.lexeme = lexeme;
    this.literal = literal;
    this.line = line;
  }

  public String toString() {
    return type + " " + lexeme + " " + literal;
  }
}

4.2.3 位置信息（Location Information）

每个记号还保存行号，供错误报告定位。完整生产级扫描器通常还保留列号、起止偏移量等信息；本书取足够但简单的设计。

4.3 正规语言与正则表达式（Regular Languages and Expressions）

扫描器的任务属于对正规语言（regular language）的识别。此类语言可由正规表达式描述，也能由有限状态机识别；扫描时只需有限状态，不必保存任意深度的嵌套结构。括号配对等需要栈的结构不属于这一阶段，留给解析器处理。

形式语言理论为正规语言、正则表达式和有限自动机之间的等价提供严格基础；但这里无需先钻进理论。手写 scanner 的控制流本身就是一个小型自动机：读取字符、在有限几个状态之间转移，并决定何时发出 token。

很多扫描器由 Lex、Flex 等工具从正则规则生成。本书手写扫描器，因为它短小、易懂，而且能让每处行为都清晰可见。

4.4 Scanner 类（The Scanner Class）

扫描器保存源文本、当前词素开头、当前读取位置、行号与输出列表：

package com.craftinginterpreters.lox;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

class Scanner {
  private final String source;
  private final List<Token> tokens = new ArrayList<>();
  private static final Map<String, TokenType> keywords;

  private int start = 0;
  private int current = 0;
  private int line = 1;

  Scanner(String source) {
    this.source = source;
  }

  List<Token> scanTokens() {
    while (!isAtEnd()) {
      start = current;
      scanToken();
    }

    tokens.add(new Token(EOF, "", null, line));
    return tokens;
  }

  private boolean isAtEnd() {
    return current >= source.length();
  }
}

静态导入只是让 LEFT_PAREN 之类枚举成员不必反复写成 TokenType.LEFT_PAREN；若更偏好显式限定名，也完全可以省略它。

start 指向当前词素第一个字符，current 指向即将读取的字符。每轮扫描前把 start 设为 current，然后识别一个词素。最后添加一个空文本的 EOF 记号，解析器借此知道输入结束。

4.5 识别词素（Recognizing Lexemes）

扫描一个词素先消费一个字符，再按它分派：

private void scanToken() {
  char c = advance();
  switch (c) {
    case '(': addToken(LEFT_PAREN); break;
    case ')': addToken(RIGHT_PAREN); break;
    case '{': addToken(LEFT_BRACE); break;
    case '}': addToken(RIGHT_BRACE); break;
    case ',': addToken(COMMA); break;
    case '.': addToken(DOT); break;
    case '-': addToken(MINUS); break;
    case '+': addToken(PLUS); break;
    case ';': addToken(SEMICOLON); break;
    case '*': addToken(STAR); break;
    // 其余分支在下面补齐。
  }
}

private char advance() {
  return source.charAt(current++);
}

private void addToken(TokenType type) {
  addToken(type, null);
}

private void addToken(TokenType type, Object literal) {
  String text = source.substring(start, current);
  tokens.add(new Token(type, text, literal, line));
}

advance() 消费并返回下一个输入字符；addToken() 则是输出端操作，取得当前词素文本并创建记号。

4.5.1 词法错误（Lexical Errors）

Lox 不使用 @#^ 之类字符，不能静默丢弃它们，而应报告错误：

default:
  Lox.error(line, "Unexpected character.");
  break;

错误字符已经被 advance() 消费，这很重要，否则会陷入无限循环。报告后仍继续扫描，尽可能一次发现更多错误；hadError 已被设置，因此不会执行任何有错误的代码。

这种“霰弹枪式”恢复并不总可靠：后续字符可能被误解，导致级联错误。不过对扫描器而言，跳过一个无法识别的字符是简单且合理的继续策略。

4.5.2 运算符（Operators）

! 可能是单字符运算符，也可能与紧随其后的 = 合成 !=；=, <, > 同样如此。需要条件消费下一个字符：

case '!': addToken(match('=') ? BANG_EQUAL : BANG); break;
case '=': addToken(match('=') ? EQUAL_EQUAL : EQUAL); break;
case '<': addToken(match('=') ? LESS_EQUAL : LESS); break;
case '>': addToken(match('=') ? GREATER_EQUAL : GREATER); break;

private boolean match(char expected) {
  if (isAtEnd()) return false;
  if (source.charAt(current) != expected) return false;
  current++;
  return true;
}

match() 是条件版 advance()：仅当当前字符匹配时才消费它。这样 != 被识别为一个词素，而不是两个独立运算符。

4.6 更长的词素（Longer Lexemes）

/ 既可能是除法，也可能是行注释开头：

case '/':
  if (match('/')) {
    // 注释持续到行末。
    while (peek() != '\n' && !isAtEnd()) advance();
  } else {
    addToken(SLASH);
  }
  break;

private char peek() {
  if (isAtEnd()) return '\0';
  return source.charAt(current);
}

peek() 不消费字符，是一次向前看（lookahead）。本章的词法规则只需看一两个字符；所需前瞻越小，扫描器通常越快。注释虽是词素却没有语言意义，因此到行尾不调用 addToken()，下轮扫描重置 start 后它就消失。

把注释在扫描阶段消掉而非交给解析器，能使后续所有阶段都不必考虑它们；空白也有同样好处。

空白也应跳过，换行还要更新行号：

case ' ':
case '\r':
case '\t':
  break;
case '\n':
  line++;
  break;

4.6.1 字符串字面量（String Literals）

字符串总以 " 开始，读取到闭合引号或输入结束：

case '"': string(); break;

private void string() {
  while (peek() != '"' && !isAtEnd()) {
    if (peek() == '\n') line++;
    advance();
  }

  if (isAtEnd()) {
    Lox.error(line, "Unterminated string.");
    return;
  }

  advance(); // 闭合引号。
  String value = source.substring(start + 1, current - 1);
  addToken(STRING, value);
}

Lox 有意支持多行字符串，因此字符串内遇到换行也增加行号。生成记号时去掉两侧引号，得到解释器后续真正使用的字符串值。若支持 \n 等转义序列，也应在此处解码。

4.6.2 数字字面量（Number Literals）

运行时所有 Lox 数字都是浮点数，但字面量可写成整数或小数：一串数字，后面可跟 . 和至少一个数字。-123 不是一个数字字面量，而是把一元 - 应用于 123 的表达式。

不允许 .1234 与 1234.。前者易于加入，但为保持简单省略；后者若将来支持 123.sqrt() 一类数字方法会带来歧义。

default:
  if (isDigit(c)) {
    number();
  } else if (isAlpha(c)) {
    identifier();
  } else {
    Lox.error(line, "Unexpected character.");
  }
  break;

private void number() {
  while (isDigit(peek())) advance();

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

  addToken(NUMBER, Double.parseDouble(source.substring(start, current)));
}

private char peekNext() {
  if (current + 1 >= source.length()) return '\0';
  return source.charAt(current + 1);
}

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

小数点只在后面确实有数字时才属于数字，故 1.foo 会正确扫描为数字、点、标识符。

4.7 保留字与标识符（Reserved Words and Identifiers）

标识符以字母或下划线开头，后续还可包含数字。这里的“字母”有意只限 ASCII；支持 Unicode 标识符需要解决大量看似无害的规范化与安全问题。

扫描器采用最大匹配原则：只要后续字符仍能构成标识符，就继续读取。因此 orchid 不会先被切成关键字 or 和标识符 chid；扫描完整词素后才查关键字表。这种“尽可能长地吃字符”的规则是多数 scanner 的常用策略。

private void identifier() {
  while (isAlphaNumeric(peek())) advance();

  String text = source.substring(start, current);
  TokenType type = keywords.get(text);
  if (type == null) type = IDENTIFIER;
  addToken(type);
}

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

private boolean isAlphaNumeric(char c) {
  return isAlpha(c) || isDigit(c);
}

完整匹配词素后，再通过哈希表把保留字映射为相应类型；没有匹配项就是普通 IDENTIFIER：

static {
  keywords = new HashMap<>();
  keywords.put("and", AND);
  keywords.put("class", CLASS);
  keywords.put("else", ELSE);
  keywords.put("false", FALSE);
  keywords.put("for", FOR);
  keywords.put("fun", FUN);
  keywords.put("if", IF);
  keywords.put("nil", NIL);
  keywords.put("or", OR);
  keywords.put("print", PRINT);
  keywords.put("return", RETURN);
  keywords.put("super", SUPER);
  keywords.put("this", THIS);
  keywords.put("true", TRUE);
  keywords.put("var", VAR);
  keywords.put("while", WHILE);
}

至此扫描器完成。它会把 Lox 源代码转为包含类型、原始词素、可选字面量值和行号的记号序列。下一章将从这些扁平记号构建嵌套的语法结构。

挑战（Challenges）

1. Lox 不支持块注释。加入类似 /* ... */ 的块注释，并处理嵌套注释的取舍。
2. 增加逗号运算符，让 a, b 先求值 a 再求值 b，其值为 b。它应具有什么优先级？
3. 支持科学记数法，如 1.2e-3。
4. 允许标识符使用 Unicode 字母。应如何定义“字母”？Unicode 规范化会造成哪些问题？

设计笔记：隐式分号（Implicit Semicolons）

Lox 要求显式分号，许多语言则尝试在换行处自动插入分号。这样输入更少，却会把原本简单的换行变成有语义的符号，扫描器或解析器必须猜测一行是否结束语句。

一些规则看似简单，例如在标识符、字面量、右括号或右花括号后遇到换行时插入分号；但很快会遇到二义性。函数调用、二元运算符、链式方法调用和多行表达式都可能令“看起来像行末”的位置实际仍属于同一语句。JavaScript、Go、Ruby、Python 等语言各自都有规则、约定或显式续行机制来处理这些情况。

例如 return\nvalue; 在 JavaScript 中可能被理解为无值返回，a\n.b() 又常希望继续作为属性访问。语言若允许隐式分号，必须把“哪些 token 可以结束语句”和“哪些 token 必须继续表达式”的规则做得足够可预测，并让格式化与错误报告遵守同一套规则。

隐式分号不只是语法糖，它会影响错误消息、格式化工具和程序员对换行的直觉。Lox 选择显式分号，是为了使本书的语法和实现保持清晰；若你设计自己的语言，应把减少符号输入的收益与隐式规则带来的惊喜仔细权衡。