第2章 词法分析（文本到 Token）

一、导读

1.1 本章学习目标

理解词法分析在编译流程中的定位与核心职责：将字符流转换为 Token 序列

掌握正则表达式（Regular Expression）的语法及其描述词法模式的能力

理解有限自动机（Finite Automaton）的定义、分类及其与正则表达式的等价关系

掌握从正则表达式构造 NFA（Thompson 构造法）和从 NFA 构造 DFA（子集构造法）的算法

了解 DFA 最小化的原理与 Hopcroft 算法的实现

理解词法分析器的实现策略：手工编写与自动生成工具（Lex/Flex）的对比

掌握词法分析中的工程实践问题：缓冲区管理、行号追踪、错误恢复

理解词法分析的形式化基础——正则语言及其泵引理（Pumping Lemma）

1.2 为什么本章如此重要

词法分析是编译过程的入口，是编译器"理解"源代码的第一步。如果说编译器是一座翻译工厂，那么词法分析器就是工厂的原料分拣线——它将杂乱的字符流整理成一个个有意义的词法单元（Token），为后续的语法分析提供结构化的输入。词法分析的质量直接影响整个编译流程的效率和可靠性。

从理论角度来看，词法分析建立在正则语言和有限自动机的数学基础之上，这是计算机科学中最成熟、最优美的理论成果之一。正则表达式与有限自动机的等价性定理，将模式描述（正则表达式）与模式识别（有限自动机）完美地统一起来，为词法分析器的自动生成提供了坚实的理论保证。这一理论框架不仅在编译器设计中至关重要，还在文本处理、网络协议解析、搜索引擎、生物信息学等众多领域发挥着核心作用。

从工程实践角度来看，词法分析器的实现技术直接影响编译器的性能。词法分析器需要处理源文件中的每一个字符，其执行效率是编译器整体性能的关键因素之一。现代词法分析器通过 DFA 模拟实现线性时间复杂度的模式匹配，配合高效的缓冲区管理策略，能够以极高的速度处理大规模的源代码文件。此外，Lex/Flex 等扫描器生成工具的使用，使得开发者能够以声明式的方式定义词法规则，极大地简化了词法分析器的开发工作。

1.3 核心问题引导

为什么词法分析可以用正则表达式来描述，而不需要更强大的形式化工具？

NFA 和 DFA 的本质区别是什么？为什么实际实现中要使用 DFA 而非 NFA？

从正则表达式到可执行的词法分析器，中间经历了哪些转换步骤？

如何处理词法分析中的歧义性——当一个字符串可以匹配多条规则时怎么办？

为什么某些编程语言的词法结构无法用正则表达式描述？请举例说明。

扫描器生成工具（如 Flex）生成的代码与手工编写的词法分析器相比，各有什么优劣？

词法分析器如何处理输入缓冲区？当 Token 跨越缓冲区边界时怎么办？

二、核心概念详解

2.1 正则表达式与词法模式描述

正则表达式（Regular Expression）是一种用于描述字符串模式的数学表示法，它通过有限的运算符组合来定义无限的语言集合。在词法分析中，正则表达式被用来精确地定义编程语言中各种词法元素的格式规则。

正则表达式的基本运算包括：连接（Concatenation），将两个模式依次匹配，如 ab 匹配字符 a 后跟字符 b；选择（Alternation），用 | 运算符表示匹配两个模式之一，如 a|b 匹配 a 或 b；闭包（Kleene Closure），用 * 运算符表示匹配零次或多次，如 a* 匹配空串、a、aa、aaa 等。在此基础上，还有正闭包 +（一次或多次）、可选 ?（零次或一次）、字符类 [abc]（匹配集合中的任意一个字符）和范围 [a-z]（匹配范围内的任意字符）等扩展运算符。

以 C 语言的标识符规则为例，其正则表达式可以写为 [a-zA-Z_][a-zA-Z0-9_]*，表示以字母或下划线开头，后跟零个或多个字母、数字或下划线。整数常量的正则表达式为 [0-9]+|0[xX][0-9a-fA-F]+，分别匹配十进制和十六进制整数。这些规则简洁而精确地定义了词法元素的格式，是词法分析器自动生成的基础。

正则表达式的形式化语义基于字母表（Alphabet）和字符串（String）的概念。字母表是有限的符号集合，字符串是字母表符号的有限序列，语言是字符串的集合。正则表达式通过递归定义精确地刻画了一类特殊的形式语言——正则语言（Regular Language），这类语言恰好是有限自动机所能识别的语言类。

2.2 有限自动机：从 NFA 到 DFA

有限自动机（Finite Automaton）是一种抽象的计算模型，它由有限数量的状态（State）、状态之间的转移（Transition）、一个起始状态（Start State）和一组接受状态（Accept State）组成。有限自动机从起始状态出发，根据输入字符沿着转移函数改变状态，最终如果停在某个接受状态，则判定输入字符串被接受（匹配）。

非确定有限自动机（NFA）允许在同一个状态下对同一个输入字符有多个可能的转移目标，甚至允许 epsilon 转移（不消耗输入字符的状态转移）。这种"非确定性"使得 NFA 在构造上非常灵活——Thompson 构造法可以从任意正则表达式在线性时间内构造出对应的 NFA，每个子表达式对应一个小的 NFA 片段，通过 epsilon 转移将它们组合起来。然而，NFA 的模拟执行需要同时跟踪多个可能的状态路径，效率较低。

确定有限自动机（DFA）对 NFA 施加了确定性约束：每个状态对每个输入字符最多只有一个转移。这意味着 DFA 的执行路径是唯一确定的，可以在 O(n) 时间内完成长度为 n 的字符串的模式匹配，且不需要回溯。子集构造法（Subset Construction）可以将任意 NFA 转换为等价的 DFA——DFA 的每个状态对应 NFA 的状态集合，通过计算 epsilon 闭包和状态转移来逐步构建 DFA 的状态空间。

然而，子集构造法可能导致状态数量的指数级膨胀——一个具有 n 个状态的 NFA 可能产生多达 2^n 个状态的 DFA。在实际的词法分析器中，这种状态爆炸问题需要通过 DFA 最小化来缓解。

2.3 DFA 最小化与 Hopcroft 算法

DFA 最小化的目标是在保持识别语言不变的前提下，找到状态数量最少的等价 DFA。最小化的 DFA 不仅是最高效的词法分析器实现，也是唯一的（在同构意义下），这意味着对于同一个词法规则集，最小化 DFA 给出了最优的自动机实现。

DFA 最小化的核心思想是状态等价类的划分。两个状态是等价的，当且仅当从它们出发，对任何输入字符串的接受/拒绝判定完全相同。最小化算法从最粗的划分开始——将所有接受状态分为一组，所有非接受状态分为另一组——然后不断细化划分，直到划分不再变化。具体来说，如果两个状态在某个输入字符上的转移分别到达不同组的成员，则它们必须被分到不同的组。

Hopcroft 算法是目前已知最高效的 DFA 最小化算法之一，其时间复杂度为 O(n log n)，其中 n 是 DFA 的状态数。该算法通过维护一个待处理的工作列表来高效地执行划分细化操作。在实际的编译器实现中，由于词法规则产生的 DFA 通常不会太大（几百到几千个状态），最小化的计算开销是可以接受的。

最小化后的 DFA 可以直接被编译为词法分析器的核心代码——通常是一个二维数组（状态转移表），行代表状态，列代表输入字符，数组元素代表下一个状态。词法分析器的执行循环就是不断查表并更新当前状态，直到到达接受状态或发现无法匹配的输入。

2.4 扫描器生成工具：Lex 与 Flex

Lex 是最早的扫描器生成工具之一，由 Mike Lesk 和 Eric Schmidt 于 1975 年在贝尔实验室开发。Flex（Fast Lexical Analyzer Generator）是 Lex 的开源替代品，由 Vern Paxson 开发，在保持接口兼容的同时大幅提升了生成代码的执行速度。

使用 Lex/Flex 开发词法分析器的流程非常直观：开发者在 .lex 或 .flex 文件中编写三部分的规则定义——声明段（定义正则表达式的缩写名和 C 代码片段）、规则段（正则表达式-动作对，每个规则指定当匹配到某个模式时应执行的动作）和用户代码段（辅助函数和 main 函数）。Flex 工具读取规则文件后，自动生成一个 C 语言的词法分析器，其中包含基于 DFA 的高效模式匹配逻辑。

Flex 生成的词法分析器采用表驱动（Table-Driven）的执行方式：核心是一个状态转移表和一个输入缓冲区管理模块。分析器的主循环不断从输入缓冲区读取字符，根据当前状态和输入字符查表确定下一个状态，当到达接受状态时执行对应的动作代码。这种设计将模式匹配的逻辑完全数据化，使得同一个分析器引擎可以处理任意词法规则集。

在现代编译器开发中，除了传统的 Lex/Flex，还有许多更先进的扫描器生成工具。ANTLR 的词法分析器生成器支持 Unicode、语法谓词和词法语义动作；RE2C 生成高度优化的内联 C 代码，避免了查表的开销；Ragel 支持更丰富的状态机操作。选择哪种工具取决于项目需求、性能要求和开发者的偏好。

2.5 词法分析的工程实现细节

在实际的编译器实现中，词法分析器面临诸多工程挑战，这些细节往往决定了词法分析器的鲁棒性和性能。

输入缓冲区管理是一个关键问题。源文件通常远大于可用内存，词法分析器不能一次性将整个文件读入内存。常见的解决方案是使用双缓冲区策略：维护两个大小相等的缓冲区，当一个缓冲区的内容被消耗殆尽时，异步地将文件的下一块读入另一个缓冲区。这样可以在任何时候都保证至少有一个半缓冲区的数据可用，足以容纳任何可能的 Token。缓冲区的大小通常选择为磁盘块大小的整数倍（如 4KB 或 8KB），以优化 I/O 效率。

最长匹配原则（Longest Match）是词法分析中的核心消歧规则。当输入字符串的前缀可以匹配多条规则时，词法分析器选择能够匹配最长输入前缀的那条规则。例如，在 C 语言中，>= 应该被识别为一个关系运算符 Token，而不是两个 Token（> 和 =）。如果多条规则匹配相同长度的输入，则选择规则文件中先出现的那条（优先级规则）。

错误处理是词法分析器必须面对的现实问题。当输入字符无法匹配任何规则时，词法分析器需要报告词法错误并进行恢复。常见的恢复策略包括：跳过无法识别的字符并继续分析，或跳过无法识别的字符直到下一个空白符。在错误恢复过程中，词法分析器应尽量提供有意义的错误信息，包括错误位置的行号和列号。

三、深入分析与讨论

3.1 正则语言的局限性与词法分析的边界

正则语言虽然是描述词法模式的有力工具，但它并非万能的。正则语言无法描述需要"计数"或"嵌套匹配"的模式——这正是上下文无关语言的特征。一个经典的例子是 C 语言中嵌套注释的处理：如果注释可以嵌套（如 Pascal 的 (* ... (* ... *) ... *)），则无法用正则表达式精确描述注释的边界，因为正则表达式无法计数嵌套的层数。

另一个典型案例是 C++ 的模板语法。在 C++ 中，>> 可能是右移运算符，也可能是两个模板参数列表的闭合括号（如 vector<vector<int>>）。区分这两种含义需要知道当前的模板嵌套深度，这超出了正则表达式的描述能力。因此，C++ 编译器通常在词法分析器中嵌入额外的状态变量来跟踪模板上下文，这实际上是将词法分析器提升为一个带有有限记忆的扩展自动机。

在实际工程中，大多数编程语言的词法结构确实可以用正则语言来描述，因为语言设计者会有意避免需要上下文敏感词法分析的特性。然而，某些语言（如 C++、Perl）的词法规则极为复杂，需要在词法分析器中引入上下文相关的逻辑。在这种情况下，词法分析和语法分析的界限变得模糊，可能需要使用更高级的技术来处理。

3.2 Unicode 与现代词法分析的挑战

随着软件国际化的发展，现代编译器需要支持 Unicode 字符集，这给词法分析带来了显著的挑战。传统的词法分析器假设输入是 ASCII 字符（7 位），每个字符对应自动机的一个转移。然而，Unicode 拥有超过 100 万个码位，如果为每个 Unicode 字符都设置一个转移列，状态转移表将变得极其庞大，完全不可行。

解决方案是使用字符等价类（Character Equivalence Class）技术。将 Unicode 码位按照它们在词法规则中的行为分组——如果两个字符在所有正则表达式中的匹配行为完全相同，则它们属于同一个等价类。例如，对于 C 语言的标识符规则，所有字母字符（无论拉丁、希腊、西里尔还是中日韩）的行为可能相同，所有数字字符的行为可能相同。这样，转移表的列数从超过 100 万减少到几百甚至几十个等价类。

UTF-8 编码的处理也是一个实际问题。UTF-8 是变长编码，一个 Unicode 字符可能占用 1 到 4 个字节。词法分析器需要正确处理多字节序列，确保不会在字符的中间截断。通常的做法是在读取缓冲区时将 UTF-8 字节流解码为 Unicode 码位序列，然后再进行词法分析。某些高性能编译器（如 Rust 的编译器）选择在字节级别直接操作 UTF-8，避免了显式的解码开销。

四、实践案例

4.1 使用 Flex 实现 C 语言子集的词法分析器

以下是一个使用 Flex 实现简化 C 语言词法分析器的示例。该词法分析器能够识别关键字（int、if、else、while、return）、标识符、整数常量、运算符和分隔符。

规则文件的核心部分如下：关键字规则使用精确匹配并返回对应的 Token 类型码；标识符规则使用正则表达式 [a-zA-Z_][a-zA-Z0-9_]* 匹配，并通过查表区分关键字和普通标识符；整数常量规则匹配 [0-9]+，将字符串转换为数值存入 Token 的属性字段；空白符和注释规则匹配后不返回 Token，仅消耗输入；无法匹配的字符触发错误报告。

在实际使用中，Flex 会根据规则文件自动生成 lex.yy.c 源文件，其中包含 DFA 状态转移表和词法分析函数 yylex()。编译链接后即可得到一个可执行的词法分析器，它从标准输入读取字符流，向标准输出打印识别到的 Token 序列。通过测试不同的输入程序，可以验证词法分析器对各类词法元素的正确识别能力。

4.2 词法分析器中的行号追踪与错误定位

在实际的编译器中，错误消息必须包含准确的源文件位置信息（文件名、行号、列号），否则用户无法定位和修复错误。行号追踪是词法分析器的基本职责之一。

实现行号追踪的常见方法是在词法分析器中维护一个行号计数器。每当匹配到换行符（\n）时，行号加一。在 Flex 中，可以通过在规则中匹配 \n 并执行 yylineno++ 来实现。对于 Token 的位置信息，通常在 Token 的数据结构中记录起始行号、起始列号、结束行号和结束列号，这些信息在语法分析和语义分析阶段用于生成精确的错误消息。

列号的追踪相对复杂，因为需要考虑制表符（Tab）的宽度问题。通常的做法是将 Tab 视为固定宽度（如 8 个字符位置），或者根据实际的终端设置动态计算。此外，Unicode 中的零宽字符、组合字符和双向文本（BiDi）也会给列号计算带来挑战。在工程实现中，通常采用"逻辑列号"（字符计数）而非"视觉列号"（显示宽度），以简化实现并保持一致性。

五、常见误区与注意事项

5.1 误区一：正则表达式可以描述任何词法模式

正则表达式只能描述正则语言，无法处理需要嵌套匹配或计数的模式。例如，平衡括号、嵌套注释等结构需要上下文无关文法来描述。在词法分析中遇到这类情况时，需要在词法分析器中引入额外的状态跟踪机制，或将这部分工作推迟到语法分析阶段。

5.2 误区二：NFA 比 DFA 更慢，所以 NFA 没有实用价值

虽然 NFA 的直接模拟执行确实比 DFA 慢，但 NFA 在构造上具有显著优势——Thompson 构造法从正则表达式到 NFA 是线性时间的，而从正则表达式直接构造 DFA 可能需要指数时间。因此，NFA 是正则表达式到 DFA 转换过程中不可或缺的中间步骤。此外，某些运行时模式匹配引擎（如 PCRE）直接使用 NFA 模拟，因为它们需要支持反向引用等超出正则语言的特性。

5.3 误区三：词法分析器应该尽可能多地识别语义信息

词法分析器的职责是识别词法单元，不应承担过多的语义分析任务。例如，词法分析器可以识别一个整数常量，但不应检查该整数是否超出了类型范围——这是语义分析的职责。过度膨胀的词法分析器会增加复杂度、降低可维护性，并模糊各编译阶段的职责边界。

5.4 注意事项：最长匹配与优先级规则

当多条规则可以匹配同一输入时，词法分析器遵循两条消歧规则：首先选择匹配最长输入的规则（最长匹配原则），如果多条规则匹配相同长度，则选择规则文件中先定义的规则（优先级规则）。正确理解并应用这两条规则，是编写正确词法规则的关键。

5.5 注意事项：关键字的识别策略

关键字的识别有两种常见策略：一是在词法规则中为每个关键字单独定义规则（如 "int" { return INT; }），二是将所有标识符统一匹配，然后在动作代码中查关键字表判断是否为关键字。前者规则清晰但规则数量多，后者规则简洁但需要额外的查表操作。大多数实际编译器采用第二种策略，因为关键字表可以方便地维护和扩展。

六、本章小结

本章系统讲解了词法分析的理论与实现方法。正则表达式提供了描述词法模式的简洁语法，能够精确定义标识符、关键字、数字、字符串等各类词法元素的格式。有限自动机为模式匹配提供了高效的执行机制，从 NFA 到 DFA 的转换保证了确定性的线性时间匹配，DFA 最小化则确保了最优的状态空间。通过使用 Lex/Flex 等扫描器生成工具，开发者只需以声明式的方式编写词法规则，工具自动生成高效的词法分析器代码。在工程实践中，输入缓冲区管理、最长匹配原则、行号追踪和错误恢复等细节同样不可忽视，它们共同决定了一个词法分析器的鲁棒性和实用性。词法分析作为编译过程的第一步，为后续的语法分析提供了结构化的 Token 输入，是整个编译流程的基石。

七、思考题与练习

为以下词法元素编写正则表达式：(a) 浮点数常量（支持科学计数法），(b) C 语言风格的字符常量（包括转义序列），(c) 双字符运算符（如 ==、!=、<=、>=、&&、||）。

手动构造正则表达式 (a|b)*abb 的 NFA（使用 Thompson 构造法），然后使用子集构造法将其转换为 DFA，最后最小化 DFA。

分析为什么正则表达式无法描述"平衡括号"语言，并使用泵引理（Pumping Lemma）给出形式化证明。

实现一个支持行号和列号追踪的词法分析器，能够处理多行字符串字面量和嵌套注释。

调研 RE2C 工具的工作原理，与 Flex 进行对比分析，讨论各自的优缺点和适用场景。

设计一个词法分析器来处理 Python 的缩进敏感语法——如何生成 INDENT 和 DEDENT Token？需要维护哪些额外的状态信息？

分析 UTF-8 编码对词法分析器状态转移表大小的影响，并设计一种基于字符等价类的优化方案。

使用 Flex 实现一个完整的 JSON 词法分析器，能够识别所有 JSON 规范中定义的 Token 类型。