词法分析基础：正则表达式、有限自动机与词法单元
词法分析是编译器的第一个阶段，它负责将源代码的字符序列转换为有意义的词法单元（）流。如果把编译器比作一个翻译官，词法分析器就是那个最先阅读原文、把单词和标点切分出来的初级读者。本章将深入剖析词法分析的理论基石——正则表达式与有限自动机，并讲解如何将这些理论落地为手写词法分析器的工程实践。我们将从词法单元的定义出发，逐步构建从模式匹配到自动机状态迁移的完整知识体系。
上图展示了词法分析的核心链路：正则表达式作为模式描述语言，通过 Thompson 构造法转换为非确定有限自动机（NFA），再通过子集构造法转换为确定有限自动机（DFA），最终由 DFA 驱动识别出词法单元。这张图是本章内容的总纲，后续所有讨论都将围绕这条链路展开。
词法单元的定义与分类
核心原理： 的二元组结构
词法单元（）是词法分析器输出的基本单位，在编译原理中通常定义为二元组 (类别, 属性值)。类别（ Type）是一个抽象符号，表示该词法单元属于哪一类语法元素；属性值（Attribute Value）则携带该词法单元的具体信息。例如，对于 C 语言中的 int count = 42;，词法分析器会输出以下 流：
<关键字, "int">
<标识符, "count">
<赋值运算符, "=">
<整型字面量, 42>
<分号, ";">这里的关键字、标识符、运算符、字面量和分隔符就是 的类别，而引号中的内容或数值就是属性值。属性值可以是字符串、整数、浮点数，甚至是指向符号表条目的指针。
的分类体系
不同语言的 分类略有差异，但大体可以归纳为以下几类：
| 类别 | 示例 | 属性值 | 典型处理方式 |
|---|---|---|---|
| 关键字 | if, else, while, return | 关键字编号 | 预定义表，查表匹配 |
| 标识符 | 变量名、函数名、类型名 | 指向符号表的指针 | 查符号表，无则插入 |
| 字面量 | 整数、浮点数、字符串、字符 | 数值或字符串内容 | 按进制/转义规则解析 |
| 运算符 | + - * / == != <= >= | 运算符编号 | 最长匹配原则 |
| 分隔符 | ( ) { } [ ] ; , | 分隔符编号 | 单字符匹配 |
| 注释 | // 或 /* */ | 无（丢弃） | 识别后跳过 |
值得注意的是，关键字和标识符在词法上具有相同的模式（都是字母开头的字母数字串），因此词法分析器通常先按标识符模式识别，再查关键字表确认是否为保留字。这种"先识别后查表"的策略是工程中的常见做法。
正则表达式：词法模式的描述语言
核心原理：从字符到模式的抽象
正则表达式（Regular Expression, RE）是一种用于描述词法规则的代数表示法。它由基本符号和运算符组成，能够精确地定义一组字符串集合。在词法分析中，每个 类别都对应一个正则表达式。例如：
- 标识符：
[a-zA-Z_][a-zA-Z0-9_]* - 整数：
[0-9]+ - 浮点数：
[0-9]+\.[0-9]+ - 关系运算符：
<= | >= | == | != | < | >
正则表达式支持三种基本运算：选择（|）、连接（隐式）和闭包（*）。此外还有扩展运算符如 +（正闭包）、?（可选）、[a-z]（字符类）等。这些运算符的组合能力使得正则表达式能够简洁地描述复杂的词法模式。
判断方法：正则表达式的优先级规则
在构造正则表达式时，必须遵循运算符的优先级顺序：闭包 > 连接 > 选择。例如，表达式 ab|c* 应理解为 (ab)|(c*)，而不是 a(b|c)*。这种优先级规则与算术表达式中的"先乘除后加减"类似，是正确解析正则表达式的基础。
>> 既可能是右移运算符，也可能是两个 > 比较运算符。词法分析器必须采用"最长匹配"原则来解决这种歧义，即优先匹配更长的模式。
有限自动机：从正则到状态迁移
核心原理：NFA 与 DFA 的对比
有限自动机（Finite Automaton, FA）是正则表达式的等价计算模型。它分为两类：非确定有限自动机（NFA）和确定有限自动机（DFA）。NFA 允许一个状态在同一个输入符号上有多个转移边，且允许 ε（空串）转移；DFA 则要求每个状态在每个输入符号上至多有一个转移边，且不允许 ε 转移。
| 特性 | NFA | DFA |
|---|---|---|
| 状态转移 | 一个状态可有多条同符号边 | 每个符号至多一条边 |
| ε 转移 | 允许 | 不允许 |
| 实现难度 | 简单，但需回溯 | 复杂，但线性时间 |
| 空间占用 | 状态数少 | 状态数可能指数级增长 |
| 执行效率 | 可能指数级 | O(n)，n 为输入长度 |
在实际的词法分析器中，我们通常使用 DFA 进行匹配，因为 DFA 的匹配过程是确定性的，不需要回溯，时间复杂度为 O(n)。而 NFA 则作为中间产物，由正则表达式通过 Thompson 构造法生成，再通过子集构造法转换为 DFA。
操作流程：从 RE 到 DFA 的转换步骤
- 解析正则表达式：将正则表达式解析为抽象语法树（AST）。
- Thompson 构造法：从 AST 构建 NFA，每个运算符对应一组状态和转移。
- 子集构造法：将 NFA 转换为 DFA，DFA 的每个状态对应 NFA 的一个状态子集。
- 最小化 DFA：合并等价状态，减少状态数量，优化存储和匹配效率。
以标识符模式 [a-zA-Z_][a-zA-Z0-9_]* 为例，其 NFA 包含一个起始状态、一个接受状态和若干中间状态。通过子集构造法转换后，DFA 的状态数通常与 NFA 相近，但每个状态的转移都是确定的。
手写词法分析器的基本方法
核心原理：手工编码 vs 自动生成
手写词法分析器（Hand-written Lexer）是指不依赖 Lex/Flex 等自动生成工具，直接使用编程语言编写词法分析代码。其核心思想是：将 DFA 的状态迁移逻辑直接编码为程序的控制流。手写词法分析器通常采用以下两种方法之一：
- 状态变量法：使用一个整数变量表示当前状态，通过 switch-case 或 if-else 实现状态迁移。
- 表驱动法：将 DFA 的状态转移表存储为二维数组，通过查表驱动状态迁移。
对于小型语言或教学目的，状态变量法更为直观；对于大型语言，表驱动法更易于维护和扩展。
操作流程：手写词法分析器的实现步骤
- 定义 类型：使用枚举或常量定义所有 类别。
- 设计状态迁移图：根据正则表达式绘制 DFA 状态图。
- 实现状态迁移逻辑：编写代码模拟 DFA 的状态迁移。
- 处理最长匹配：记录最近一次接受状态的位置，在无法继续匹配时回退。
- 处理空白和注释：跳过空白字符和注释内容。
- 返回 流：将识别出的 依次返回给语法分析器。
案例拆解：实现一个简易的整数和标识符识别器
假设我们需要识别两种 ：整数（[0-9]+）和标识符（[a-zA-Z_][a-zA-Z0-9_]*）。我们可以设计如下 DFA：
- 状态 0：起始状态。若读到数字，进入状态 1；若读到字母或下划线，进入状态 2。
- 状态 1：整数状态。若继续读到数字，保持状态 1；否则接受为整数 。
- 状态 2：标识符状态。若读到字母、数字或下划线，保持状态 2；否则接受为标识符 。
对应的核心代码如下：
nextToken() {
skipWhitespace();
int state = 0;
StringBuilder lexeme = new StringBuilder();
int lastAcceptState = -1;
int lastAcceptPos = -1;
while (true) {
char c = peekChar();
switch (state) {
case 0:
if (isDigit(c)) { state = 1; lexeme.append(c); advance(); }
else if (isLetter(c) || c == '_') { state = 2; lexeme.append(c); advance(); }
else return error("非法字符");
break;
case 1:
if (isDigit(c)) { lexeme.append(c); advance(); }
else { lastAcceptState = 1; lastAcceptPos = lexeme.length(); return new (INT, lexeme.toString()); }
break;
case 2:
if (isAlnum(c) || c == '_') { lexeme.append(c); advance(); }
else { lastAcceptState = 2; lastAcceptPos = lexeme.length(); return new (ID, lexeme.toString()); }
break;
}
}
}这段代码展示了手写词法分析器的核心逻辑：状态迁移、词素累积和接受状态判断。在实际工程中，还需要处理更复杂的模式，如运算符的最长匹配、字符串转义等。
>= 时，如果只匹配到 > 就返回，会导致语法分析阶段出错。务必在每次进入接受状态时记录位置，并在无法继续匹配时回退到最近一次接受位置。
常见误区与总结复盘
误区一：混淆 NFA 与 DFA 的适用场景
初学者常误以为 NFA 比 DFA 更强大，实际上二者在表达能力上是等价的，都能识别正则语言。区别仅在于实现效率和空间占用。在词法分析中，我们总是使用 DFA 进行匹配，因为其线性时间复杂度是编译器性能的保障。
误区二：忽略关键字与标识符的冲突
关键字在词法上符合标识符的模式，因此必须在识别出标识符后查关键字表。如果先匹配关键字模式，会导致所有标识符都无法识别。正确的做法是：先按标识符模式识别，再查表确认是否为关键字。
误区三：不处理注释和空白
注释和空白虽然不产生 ，但必须被词法分析器识别并跳过。否则，注释中的内容会被误认为代码，导致编译错误。处理注释时要注意嵌套注释（如某些语言支持 /* /* */ */）和字符串中的注释符号。
总结复盘
本章从词法单元的定义出发，系统讲解了正则表达式、NFA/DFA 的理论基础，以及手写词法分析器的工程实践。核心要点可以归纳为：
- 是词法分析的输出，由类别和属性值组成。
- 正则表达式是描述词法模式的简洁语言，支持选择、连接和闭包运算。
- NFA 和 DFA 是正则表达式的等价计算模型，DFA 更适合实际匹配。
- 手写词法分析器的关键是状态迁移逻辑和最长匹配原则。
- 工程中要特别注意关键字与标识符的区分、注释和空白的处理。
掌握这些基础后，下一阶段我们将进入语法分析，探讨如何从 流构建语法树。但在此之前，请务必确保你的词法分析器能够正确、高效地输出 流——这是整个编译器的基础设施，任何微小的错误都会在后续阶段被放大。