第2章 词法分析（正则表达式的力量） Lexical Analysis

一、导读

1.1 本章学习目标

理解词法分析在编译流程中的位置、输入输出及其与语法分析的协作方式

掌握正则表达式（Regular Expression）的语法、运算优先级及其描述词法模式的能力

理解有限自动机（Finite Automaton）的定义、分类及状态转移图的读法

掌握从正则表达式到 NFA、再到 DFA 的转换算法（Thompson 构造法、子集构造法）

了解 DFA 最小化算法（Hopcroft 算法或填表法）的原理与意义

学会使用 Lex/Flex 等词法分析器生成工具编写规则文件并生成 C 代码

理解词法分析中的实际工程问题：最长匹配原则、输入缓冲区管理、关键字识别策略

1.2 为什么本章如此重要

词法分析是编译器与源代码接触的第一道关口。它决定了编译器如何"阅读"程序——正如人类阅读自然语言时首先将字母组合成单词，编译器首先需要将字符流分割为有意义的词法单元（Token）。词法分析的正确性直接影响后续所有阶段的工作。

从理论角度看，词法分析建立在正则语言和有限自动机的坚实数学基础之上。正则表达式是描述模式的形式化工具，有限自动机是执行模式匹配的抽象计算模型，二者通过 Kleene 定理建立了等价性。这种"描述"与"执行"的对应关系贯穿整个编译原理：正则表达式描述词法规则，有限自动机执行词法识别；上下文无关文法描述语法规则，下推自动机执行语法识别。

从工程角度看，词法分析是最早被自动化的编译阶段。Lex 工具的出现使得开发者只需编写正则表达式规则，即可自动生成高效的词法分析代码。这种"声明式"的编程范式——描述"是什么"而非"怎么做"——是现代软件工程中代码生成和领域特定语言（DSL）设计的先驱。

1.3 核心问题引导

为什么词法分析不能简单地用字符串匹配来实现？需要考虑哪些复杂情况？

正则表达式的表达能力是否有边界？有哪些语言模式是正则表达式无法描述的？

NFA 和 DFA 的本质区别是什么？为什么需要将 NFA 转换为 DFA？

子集构造法为什么可能导致状态数指数级增长？在实践中如何应对？

为什么大多数编程语言选择"最长匹配"而非"最先匹配"作为词法分析的策略？

关键字（如 if、while）应该由词法分析器识别还是由语法分析器识别？各自的优缺点是什么？

如何处理词法分析中的错误？例如源代码中出现了非法字符时应该怎么办？

二、核心概念详解

2.1 正则表达式与正则语言（约 700 字）

正则表达式（Regular Expression, RE）是一种用于描述字符串集合（即语言）的代数表示法。它由一组基本运算递归定义：空集、空串、字符、并（| 或 +）、连接（拼接）和闭包（*）。在此基础上，还衍生出可选（?）、正闭包（+）、字符类（[a-z]）等便捷记法。

例如，C 语言中标识符的正则表达式可以写为 [a-zA-Z_][a-zA-Z0-9_]*，它精确地描述了"以字母或下划线开头，后跟零个或多个字母、数字或下划线"的模式。整数的正则表达式可以写为 [0-9]+，浮点数则更为复杂：[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?。

正则表达式的理论意义在于，它精确地刻画了正则语言（Regular Language）这一类形式语言。根据 Kleene 定理，一个语言是正则语言，当且仅当它可以被正则表达式描述，当且仅当它可以被有限自动机识别。这个等价关系是词法分析的理论基石。

然而，正则表达式的表达能力是有限的。它无法描述需要"计数"或"嵌套"的模式。例如，平衡括号的集合 {^n }^n | n >= 0} 不是正则语言，因为有限自动机没有栈来记录括号的嵌套深度。这类模式需要上下文无关文法来描述，这正是下一章的主题。

在实际的编译器实现中，词法分析器还需要处理一些正则表达式理论之外的工程问题。例如，C 语言中关键字和标识符的词法规则相同（都是字母开头的字母数字序列），区分关键字的方法通常是：先将所有匹配识别为标识符，然后在符号表中查找是否为关键字。这种"先匹配后查表"的策略是词法分析中的常见做法。

2.2 有限自动机：从 NFA 到 DFA（约 800 字）

有限自动机（Finite Automaton, FA）是一种抽象计算模型，由有限个状态、状态间的转移函数、起始状态和接受状态集合组成。根据转移函数的确定性，有限自动机分为两类。

确定有限自动机（Deterministic Finite Automaton, DFA）的特点是：每个状态对每个输入字符恰好有一条转移。这意味着在任何时刻，自动机的下一个状态是唯一确定的。DFA 可以用一个二维表格（状态转移表）完整表示，识别一个长度为 n 的字符串需要恰好 n 步转移，时间复杂度为 O(n)。

非确定有限自动机（Nondeterministic Finite Automaton, NFA）允许：一个状态对同一字符可以有多条转移（多值性），也可以有不需要消耗输入字符的 epsilon 转移（空转移）。NFA 的"非确定性"意味着在识别过程中可能存在多条路径，只要其中至少一条到达接受状态，该字符串就被接受。

NFA 更容易从正则表达式构造（使用 Thompson 构造法），但直接模拟 NFA 的执行需要跟踪所有可能的状态集合，效率较低。因此，实际词法分析器通常使用 DFA。将 NFA 转换为 DFA 的算法称为子集构造法（Subset Construction）或幂集构造：DFA 的每个状态对应 NFA 的一个状态子集，DFA 的转移函数通过对 NFA 状态子集求 epsilon 闭包和字符转移来计算。

子集构造法的一个潜在问题是状态数可能指数级增长：NFA 的 n 个状态可能产生 2^n 个 DFA 状态。但在实际的正则表达式中，这种情况很少出现。此外，可以通过 DFA 最小化算法将 DFA 的状态数压缩到最少，同时保持识别能力不变。最小化 DFA 的核心思想是合并"等价状态"——即对所有后续输入都产生相同接受/拒绝结果的状态。

2.3 Lex 工具与词法分析器生成（约 600 字）

Lex 是 Unix 系统上经典的词法分析器生成工具，由 Mike Lesk 和 Eric Schmidt 于 1975 年开发。它的开源替代品 Flex（Fast Lexical Analyzer Generator）在保持兼容性的同时大幅提升了生成代码的效率。

Lex 的输入是一个规则文件，由三部分组成：定义部分（Definitions）、规则部分（Rules）和用户代码部分（User Code）。规则部分是最核心的，每条规则由一个正则表达式和对应的动作（C 代码）组成，格式为 {正则表达式} {动作代码}。当 Lex 生成的词法分析器在输入中匹配到某个正则表达式时，就执行对应的动作代码。

Lex 工具内部的工作流程完美体现了本章的理论知识：首先将所有规则中的正则表达式合并为一个大的 NFA，然后通过子集构造法转换为 DFA，再进行最小化，最终生成一张高效的状态转移表和一段驱动该表的 C 代码。开发者只需关心"识别什么模式后做什么动作"，完全不需要手工编写状态转移逻辑。

在编译器项目中，Lex 规则文件的典型结构是：为每种 Token 类型（关键字、标识符、数字、运算符、分隔符等）编写一条规则，动作为返回对应的 Token 类型编码。对于空白字符和注释，动作通常为"忽略并继续扫描"。Lex 默认采用最长匹配原则：在所有能匹配的规则中，选择匹配最长输入的那条；如果有多条规则匹配相同长度，选择文件中先出现的那条。

2.4 输入缓冲区管理与前瞻（约 500 字）

词法分析器需要从文件或其他输入源读取字符流。直接逐字符读取效率极低，因为每次 I/O 操作的开销远大于字符处理本身。因此，实际的词法分析器使用输入缓冲区（Input Buffer）批量读取字符，减少 I/O 次数。

输入缓冲区管理面临一个经典问题：如何判断当前 Token 是否已经完整读取？例如，看到字符 > 时，需要看下一个字符才能判断它是"大于号"还是"大于等于号"；看到 = 时，需要看后续字符才能区分它是"赋值号"还是"等于号"或"箭头"。这种需要查看后续字符才能做出决定的需求称为前瞻（Lookahead）。

双缓冲区技术是解决这个问题的经典方案：使用两个大小相等的缓冲区交替填充，当一个缓冲区耗尽时，自动加载下一个缓冲区的内容。这样，绝大多数情况下 Token 的边界都在单个缓冲区内部，只有极少数跨越缓冲区边界的 Token 需要特殊处理。这种设计在保证正确性的同时，将 I/O 开销降到了最低。

三、深入分析与讨论

3.1 Thompson 构造法详解（约 500 字）

Thompson 构造法是将正则表达式转换为 NFA 的经典算法，由 Ken Thompson 在 1968 年提出（他也是 Unix 的联合创始人之一）。该算法采用递归策略：对正则表达式的每种运算定义对应的 NFA 片段，然后按照表达式的结构组合这些片段。

具体规则如下：对于单个字符 a，构造一个两状态 NFA，从起始状态经字符 a 转移到接受状态。对于并运算 r|s，新建一个起始状态，通过 epsilon 转移分别连接到 r 和 s 的 NFA 的起始状态，r 和 s 的接受状态通过 epsilon 转移连接到一个新的接受状态。对于连接运算 rs，将 r 的接受状态与 s 的起始状态合并（或通过 epsilon 转移连接）。对于闭包运算 r*，新建起始状态和接受状态，通过 epsilon 转移实现零次或多次重复。

Thompson 构造法保证生成的 NFA 状态数与正则表达式的长度成线性关系，这是它的重要优势。但生成的 NFA 包含大量 epsilon 转移，需要通过子集构造法转换为 DFA 后才能高效执行。

3.2 词法错误处理策略（约 400 字）

当词法分析器遇到无法匹配的字符序列时，需要进行错误处理。常见的策略有三种：恐慌模式（Panic Mode），丢弃无法识别的字符直到遇到可识别的字符；短语层次恢复（Phrase-level Recovery），在错误位置插入或删除少量字符以恢复词法分析；以及将非法字符作为特殊 Token 传递给语法分析器，由后者报告错误。

现代编译器通常采用第三种策略的变体：为每个无法匹配的字符生成一个错误 Token，同时尽可能继续扫描后续内容，以便在一次编译中发现尽可能多的错误。这种"尽力而为"的错误处理策略显著提升了开发者的调试体验。

四、实践案例

4.1 案例一：用 Flex 实现 C 语言子集的词法分析器（约 400 字）

以下是一个用 Flex 编写的简单词法分析器规则文件的核心部分，它能识别 C 语言子集中的主要 Token 类型：

规则部分包括：为关键字（if、else、while、return、int）编写独立规则，返回对应的 Token 编码；为标识符编写规则 [a-zA-Z_][a-zA-Z0-9_]*，在符号表中查找是否为关键字，若不是则返回 IDENTIFIER；为整数常量编写规则 [0-9]+，返回 INTEGER；为运算符（+、-、*、/、=、==、!=、<、>、<=、>=）分别编写规则；为分隔符（;、,、{、}、(、)）编写规则；为空白和换行编写忽略规则。

通过这个案例，可以直观地理解 Lex/Flex 的工作方式：每条规则的正则表达式定义了匹配模式，动作代码定义了匹配后的处理逻辑。Flex 工具自动将这些规则合并为一张高效的 DFA 状态转移表，生成的 C 代码中的 yylex() 函数每次调用返回下一个 Token。

4.2 案例二：手动实现词法分析器的状态机方法（约 400 字）

虽然 Lex/Flex 等工具可以自动生成词法分析器，但理解手工实现的方法同样重要。手工实现的核心是将正则表达式对应的 DFA 用 switch-case 或状态转移表编码为程序。

以识别 C 语言整数和浮点数为例：起始状态读取数字进入"数字"状态；在"数字"状态读取数字保持在"数字"状态，读取小数点进入"小数"状态；在"小数"状态读取数字保持在"小数"状态，读取 e 或 E 进入"指数"状态；在"指数"状态读取 + 或 - 进入"指数符号"状态，读取数字进入"指数数字"状态。每个接受状态对应一种 Token 类型（整数或浮点数）。

这种手工实现方式虽然繁琐，但它让你完全掌控词法分析器的行为，在需要特殊处理（如上下文相关的词法分析，如 C++ 的模板参数中的 >> 歧义）时非常有用。

五、常见误区与注意事项

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

正则表达式无法描述需要匹配嵌套结构的模式。例如，C 语言中的注释 /* ... */ 虽然可以用正则表达式近似描述（/\*[^*]*\*+([^/*][^*]*\*+)*\*/），但表达式复杂且不易理解。对于更复杂的嵌套结构（如字符串中的转义引号），正则表达式的描述能力更加捉襟见肘。此时应考虑使用状态机或扩展正则表达式。

5.2 误区二：DFA 状态数总是可控的

子集构造法在最坏情况下会产生指数级的 DFA 状态数。虽然实际的正则表达式很少触发这种情况，但在编写 Lex 规则时仍需注意：避免使用过于复杂的正则表达式，尤其是包含大量交替和闭包嵌套的模式。Flex 提供了 --debug 选项帮助诊断状态数过多的问题。

5.3 误区三：词法分析可以完全独立于语法分析

某些语言的词法规则与语法上下文相关。例如，C++ 中 >> 可能是右移运算符，也可能是两个模板参数的闭合括号（vector<vector<int>>）；Fortran 中空格是否忽略取决于语法上下文。这类问题需要在词法分析和语法分析之间建立通信机制，增加了编译器的复杂度。

5.4 注意事项：字符编码的影响

现代编译器需要处理 UTF-8、UTF-16 等多种字符编码。UTF-8 是变长编码，一个字符可能占 1-4 个字节，这给词法分析器的字符读取带来了额外的复杂性。设计词法分析器时，需要确保缓冲区管理正确处理多字节字符的边界情况。

六、本章小结

本章系统讲解了词法分析的理论与实践。正则表达式为描述词法模式提供了简洁而精确的形式化工具，有限自动机（NFA 和 DFA）为模式匹配提供了高效的执行机制。Thompson 构造法将正则表达式转换为 NFA，子集构造法将 NFA 转换为 DFA，DFA 最小化进一步压缩状态数。Lex/Flex 等工具将这些理论自动化，使开发者只需声明规则即可生成高效的词法分析代码。词法分析的核心挑战包括最长匹配原则的实现、输入缓冲区的高效管理、错误恢复策略以及与语法分析的协作。掌握这些知识，为后续学习语法分析奠定了坚实的基础。

七、思考题与练习

写出以下词法模式的正则表达式：C 语言风格的十六进制整数、带可选正负号的浮点数、双引号字符串（支持 \" 和 \\ 转义）。

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

证明：语言 {a^n b^n | n >= 0} 不是正则语言（提示：使用泵引理）。

用 Flex 编写一个词法分析器，能够识别简化的 JSON 值（数字、字符串、布尔值、null、数组、对象的基本 Token）。

手工实现一个状态机，能够识别 C 语言中的整数常量（包括十进制、八进制、十六进制和各自的 long/unsigned 后缀）。

分析 Flex 生成的 C 代码，说明其状态转移表的结构和 yylex() 函数的执行流程。

讨论：为什么大多数编程语言不将注释的识别放在词法分析器中，而是作为特殊规则处理？

调研并比较 Lex、Flex、ANTLR 的 Lexer 模式和 RE2 的设计差异，说明它们各自适用的场景。