第2章扫描词法（Scanning: Text to Tokens）

一、导读

词法分析（Lexical Analysis）是语言处理的第一步，负责将源代码的字符流转换为有意义的词法单元（Token）。本章介绍如何手动实现一个扫描器（Scanner），将 Lox 语言的源代码分解为关键字、标识符、数字、字符串和运算符等 Token。

学习目标：掌握词法分析的基本原理，理解 Token 的结构设计，学会手动实现扫描器，能够处理注释、空白字符、关键字识别等实际问题。

重要性：词法分析是编译流水线的第一道工序，它的质量直接影响后续语法分析的效率和正确性。即使你使用生成器工具（如 Lex、Flex）来生成扫描器，理解其底层原理也有助于你调试和优化词法分析过程，并在出现问题时快速定位根因。

核心问题：如何将一段无结构的字符流转换为有结构的 Token 序列？如何处理多字符 Token（如 ==、!=）？如何区分关键字和标识符？如何处理字符串中的转义字符？如何处理注释和空白字符？

二、核心概念详解

2.1 Token 的数据结构

Token 是词法分析的输出单元，通常包含以下信息：类型（TokenType）、词素文本（Lexeme）、字面量值（Literal）和位置信息（行号、列号）。类型标识了 Token 的类别，如 NUMBER、STRING、IDENTIFIER、PLUS 等。词素是源代码中对应的原始文本。字面量值用于存储数字的实际数值或字符串的实际内容。位置信息用于在发生语法错误时报告准确的错误位置。

java

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;
  }
}

2.2 扫描器的基本工作流程

扫描器维护两个指针（或索引）在源代码中移动：start 指向当前 Token 的起始位置，current 指向当前正在检查的字符。扫描器逐个读取字符，根据当前字符的状态决定如何组合成 Token。当遇到一个完整的 Token 时，将 start 到 current 之间的文本提取为一个 Token 对象，然后将 start 移动到 current 的位置继续扫描。这个过程持续到所有源代码被处理完毕。

2.3 关键字与标识符的区分

Lox 语言的关键字是预定义的保留字，如 if、else、while、for、fun、return、var、class、print、true、false、nil、and、or 等。扫描器首先将字母开头的字母数字序列识别为标识符，然后通过查表（通常使用 HashMap）来判断该标识符是否为关键字。这种先识别为通用标识符再查表确认的方式，比逐一匹配关键字更加高效和易于维护。

2.4 数字和字符串的解析规则

数字可以包含小数点，扫描器需要正确处理整数和小数的格式。具体做法是先扫描整数部分，如果遇到小数点后跟数字，则继续扫描小数部分。字符串由双引号包围，扫描器在遇到开头引号后，持续读取字符直到遇到结尾引号。需要注意处理 unterminated string（未终止的字符串）错误，以及跨行字符串的情况。字符串的字面量值通常去掉引号后存储。

2.5 单字符与双字符运算符

Lox 语言中的运算符有单字符的（如 +、-、*、/、<、>）和双字符的（如 ==、!=、<=、>=）。扫描器在遇到可能构成双字符运算符的字符时，需要前瞻（lookahead）一个字符来确认。例如，遇到 ! 时需要检查下一个字符是否为 =，如果是则生成 BANG_EQUAL Token，否则生成 BANG Token。这种前瞻机制是处理多字符 Token 的关键技术。

2.6 注释与行号跟踪

扫描器还需要处理注释和行号跟踪。Lox 支持单行注释（以 // 开头到行尾）和多行注释（以 /* 开头到 */ 结尾）。扫描器在遇到注释起始符号后，跳过所有字符直到注释结束。在扫描过程中，每遇到一个换行符，行号计数器加一。行号信息被记录在每个 Token 中，用于后续的语法错误和运行时错误报告。准确的行号跟踪对于提供良好的错误信息至关重要。

三、深入分析

2.1 状态机模型与词法分析

词法分析本质上是一个有限状态机（Finite State Machine）的执行过程。每个字符的读入都可能导致状态的转移。例如，在扫描标识符时，初始状态读取到字母后进入"标识符中"状态，在该状态下读取到字母或数字则保持在"标识符中"状态，读取到其他字符则回到初始状态并输出标识符 Token。理解状态机模型有助于你设计更复杂的词法规则，如处理多行注释、heredoc 字符串等。

2.2 词法分析的错误处理

扫描器在词法分析阶段需要检测并报告多种错误。常见的词法错误包括：未终止的字符串（缺少结尾引号）、非法字符（源代码中出现了语言不支持的字符）、数字格式错误（如 123.456.789）等。良好的错误处理应该报告错误的行号和具体的错误信息，同时尽量恢复扫描以发现更多的错误，而不是遇到第一个错误就停止。

2.3 词法分析器的生成工具

虽然本书采用手动实现扫描器的方式，但在实际工程中，词法分析器生成工具（如 Lex、Flex、ANTLR）被广泛使用。这些工具接受正则表达式定义的文法规则，自动生成高效的扫描器代码。手动实现的优势在于完全可控、易于调试、没有额外依赖；生成工具的优势在于开发效率高、经过充分测试、性能优化好。选择哪种方式取决于项目的具体需求。

2.4 词法分析与 IDE 的集成

现代 IDE 和编辑器（如 VS Code、IntelliJ IDEA）需要实时进行词法分析以提供语法高亮、自动补全和错误提示等功能。与编译器的一次性扫描不同，IDE 需要增量式词法分析，只重新扫描被修改的部分。这要求扫描器支持状态保存和恢复，能够在任意位置开始扫描并正确识别 Token。此外，IDE 还需要处理不完整的代码（如未闭合的字符串或括号），这比处理完整的源代码更加复杂。TextMate 语法和 Tree-sitter 是目前主流的增量式语法分析方案。

2.5 词法分析的测试策略

测试扫描器是确保词法分析正确性的关键环节。常见的测试策略包括：为每种 Token 类型编写独立的测试用例；测试边界情况（如文件末尾、空输入、连续空白）；测试错误情况（如非法字符、未终止的字符串）；使用属性测试（Property-Based Testing）随机生成输入并验证扫描器的行为。良好的测试覆盖率是扫描器可靠性的保障。在实际项目中，通常使用快照测试（Snapshot Testing）来验证扫描器的输出是否与预期一致。

四、实践案例

4.1 案例一：扫描 Lox 表达式

考虑以下 Lox 源代码：

lox

var result = (10 + 20) * 3;

扫描器将产生以下 Token 序列：

VAR      var
IDENTIFIER result
EQUAL    =
LEFT_PAREN (
NUMBER   10
PLUS     +
NUMBER   20
RIGHT_PAREN )
STAR     *
NUMBER   3
SEMICOLON ;
EOF

每个 Token 都携带了类型、词素和行号信息，为后续的语法分析提供了结构化的输入。

4.2 案例二：处理复杂字符串

考虑包含特殊字符的字符串：

lox

var greeting = "Hello, World!\nWelcome to Lox.";

扫描器在遇到第一个引号后进入字符串扫描模式，逐个读取字符直到遇到结尾引号。生成的 STRING Token 的词素为完整的带引号字符串，而字面量值为去掉引号后的实际内容。如果字符串中包含换行符而未使用转义序列，扫描器需要报告错误并记录行号的变化。

五、常见误区

5.1 误区一：词法分析可以用正则表达式完全解决

虽然大部分词法规则可以用正则表达式描述，但某些复杂的词法模式（如嵌套注释、上下文相关的词法分析）超出了正则表达式的表达能力。此时需要借助状态机或更复杂的机制来处理。

5.2 误区二：Token 只需要存储类型信息

实际上，Token 还需要存储词素文本、字面量值和位置信息。词素用于语法分析阶段的匹配，字面量值用于后续的语义处理，位置信息用于错误报告。缺少任何一项信息都会给后续阶段带来困难。

5.3 误区三：空白字符可以完全忽略

虽然大部分空白字符（空格、制表符）仅用于分隔 Token，但换行符在某些语言中具有语法意义（如 Python 的缩进规则、Go 的自动分号插入）。即使在 Lox 中，换行符也用于行号跟踪，这对错误报告至关重要。

5.4 误区四：扫描器不需要处理错误

扫描器是第一个接触源代码的组件，它应该尽可能早地发现并报告错误。如果扫描器忽略了非法字符或格式错误，这些错误会传递到后续阶段，导致更难定位的混乱错误信息。早期发现错误能提供更精确的错误位置和更清晰的错误描述。

六、本章小结

本章讲解了如何实现 Lox 语言的扫描器。扫描器通过逐个读取字符，根据语法规则将字符组合成 Token，为后续的语法分析提供结构化的输入。Token 包含类型、词素、字面量值和行号等信息。扫描器需要正确处理关键字识别、数字和字符串解析、单双字符运算符区分以及错误报告等问题。词法分析本质上是一个有限状态机的执行过程，理解状态机模型有助于设计更复杂的词法规则。理解扫描器的工作原理，是实现任何语言处理系统的基础。

七、扩展知识：词法分析的工程实践

在实际工程中，词法分析器需要考虑更多的问题。Unicode 支持是现代扫描器的基本要求，标识符可能包含非 ASCII 字符（如中文变量名），字符串可能包含各种 Unicode 转义序列。编码检测（UTF-8、UTF-16、BOM 处理）也是扫描器需要面对的实际问题。此外，预处理指令（如 C 的 #include、#define）在词法分析之前进行处理，增加了词法分析的复杂性。对于增量编译场景，扫描器还需要支持局部重新扫描，只更新修改部分对应的 Token 序列。

八、思考题

请设计一个扫描器来处理 C 语言风格的多行注释 /* ... */，说明你需要维护哪些状态信息。

如果 Lox 语言要支持八进制（0o 前缀）和十六进制（0x 前缀）的数字字面量，扫描器需要做哪些修改？

为什么大多数语言将 == 作为相等比较运算符而不是赋值运算符？从词法分析的角度分析这种设计的优势。

请描述如何处理 Python 中的缩进敏感词法分析（indentation-sensitive lexing），这与 Lox 的词法分析有何不同？

设计一个词法错误的恢复策略：当扫描器遇到非法字符时，如何跳过错误并继续扫描以发现更多错误？

如何实现一个支持 Unicode 标识符的扫描器？请说明 UTF-8 编码下多字节字符的识别方法。

第2章 扫描词法（Scanning: Text to Tokens）