4、词法分析基础：正则表达式、有限自动机（DFA/NFA）、词法单元（）的定义与分类、词法分析器的输出格式
词法分析是编译器前端的第一阶段，其核心任务是将源代码字符流转换为有意义的词法单元（）序列。如果把编译过程比作人类阅读一篇文章，词法分析就相当于先完成“分词”——识别出哪些字符组合构成一个单词、哪些是标点、哪些是数字。本章将围绕词法分析的理论基石（正则表达式与有限自动机）、 的定义与分类、以及词法分析器的输出格式展开，帮助读者建立从“字符流”到“ 流”的完整认知链路。
4.1 正则表达式：词法规则的形式化描述
正则表达式（Regular Expression，简称 RE）是描述字符串集合的数学记号，在词法分析中用于精确刻画每一类 的字符组成模式。它由普通字符（如字母、数字）和元字符（如 *、+、?、|、()）构成，具有严格的代数性质。例如，C 语言中标识符的规则是“以字母或下划线开头，后续可以是字母、数字或下划线”，用正则表达式可写作 [a-zA-Z_][a-zA-Z0-9_]*。
4.1.1 核心原理：三种基本运算
正则表达式建立在三种基本运算之上：连接（Concatenation）、选择（Alternation）和闭包（Kleene Star）。连接表示字符依次出现，如 ab 匹配“ab”；选择用竖线 | 表示“或”，如 a|b 匹配“a”或“b”；闭包用 * 表示“零次或多次”，如 a* 匹配空串、a、aa、aaa……。由这三种运算组合，可以描述几乎所有编程语言中的词法模式。此外，+ 表示“一次或多次”，? 表示“零次或一次”，[ ] 表示字符集合，. 表示任意字符（在词法分析中通常限定为除换行符外）。
4.1.2 判断方法：从语言规则到正则表达式
将自然语言描述的词法规则转化为正则表达式，需要遵循以下步骤：
- 识别字符类别：确定该 允许出现的字符集合，例如数字
[0-9]、字母[a-zA-Z]。 - 确定结构顺序：分析字符出现的先后关系，例如“数字后跟小数点再跟数字”对应
[0-9]+"."[0-9]+。 - 处理重复与可选：判断哪些部分可以重复（
*或+），哪些部分可选（?）。 - 考虑边界情况：如整数是否允许前导零、字符串是否支持转义字符等。
示例：设计一个简单的整数常量规则——十进制整数（不允许前导零，但单独的 0 合法）：0|[1-9][0-9]*。若允许十六进制，则扩展为 0[xX][0-9a-fA-F]+。注意，多个规则之间需要定义优先级，例如关键字 if 应优先于标识符规则匹配。
4.1.3 常见误区
- 贪婪匹配陷阱：正则表达式默认是贪婪的，会尽可能多地匹配字符。在词法分析中，我们通常采用“最长匹配”策略，但需要与“优先匹配关键字”规则结合，避免将
ifx误识别为关键字if加标识符x。 - 转义字符处理：正则表达式中的元字符（如
*、+、(）若需匹配其本身，必须使用反斜杠转义，例如\*匹配星号。 - 字符集合的边界：
[a-z]包含小写字母，但不包含大写字母；[^0-9]表示非数字字符。需要仔细核对集合范围。
4.2 有限自动机：从正则到可执行代码
正则表达式虽然直观，但计算机无法直接执行它。有限自动机（Finite Automaton）是正则表达式的等价计算模型，分为非确定有限自动机（NFA）和确定有限自动机（DFA）。NFA 允许一个状态在同一个输入符号下转移到多个状态，且支持 ε-转移（不消耗输入字符的转移）；DFA 则要求每个状态在每个输入符号下最多只有一个转移目标。DFA 的匹配效率更高（O(n) 时间复杂度），但 NFA 更接近正则表达式的结构，易于从 RE 直接构造。
4.2.1 核心原理：Thompson 构造法与子集构造法
从正则表达式生成 DFA 的标准流程分为两步：Thompson 构造法将 RE 转换为等价的 NFA，其基本思想是为每种运算（连接、选择、闭包）设计固定的 NFA 片段，然后组合；子集构造法（Subset Construction）将 NFA 转换为 DFA，核心思想是将 NFA 的状态集合作为 DFA 的单个状态，通过计算 ε-闭包和转移函数逐步构建 DFA 的状态转移表。最终，DFA 可以被直接翻译为词法分析器中的状态转移代码或查表驱动代码。
4.2.2 操作流程：手工构造小型 DFA
以识别无符号整数（[0-9]+）为例，手工构造 DFA 的步骤如下：
- 定义状态：起始状态 S0，接受状态 S1。
- 从 S0 出发，读入数字 0-9，转移到 S1。
- 从 S1 出发，读入数字 0-9，仍停留在 S1。
- 其他输入（如字母、符号）在 S0 和 S1 均无转移，视为匹配结束。
实际编译器通常使用工具（如 Lex、Flex）自动完成 RE → NFA → DFA 的转换，但理解手工构造过程有助于调试自动生成的词法分析器。
| 特性 | NFA | DFA |
|---|---|---|
| 状态转移 | 一个输入可对应多个状态 | 一个输入最多对应一个状态 |
| ε-转移 | 支持 | 不支持 |
| 匹配时间复杂度 | O(n × 状态数)，可能回溯 | O(n)，线性扫描 |
| 空间占用 | 状态数较少 | 状态数可能指数级增长 |
| 构造难度 | 从 RE 直接构造，简单 | 需子集构造法，较复杂 |
| 实际应用 | 正则引擎内部表示 | 词法分析器生成器（如 Flex） |
4.2.3 案例拆解：标识符与关键字的 DFA 合并
假设语言包含关键字 if 和 while，以及标识符规则 [a-zA-Z_][a-zA-Z0-9_]*。若分别构造 DFA，则输入 if 会同时匹配关键字规则和标识符规则。解决方法是：在词法分析器中维护一个关键字哈希表，当 DFA 识别出一个标识符后，先查表判断是否为关键字。这种“DFA 识别 + 查表确认”的策略避免了为每个关键字单独构造 DFA 导致的状态爆炸。
经验提醒：在 Flex 中，关键字规则写在标识符规则之前，并利用“最长匹配”原则——当输入 ifx 时，标识符规则匹配整个 ifx，而关键字规则只匹配 if，因此最终识别为标识符。若输入恰好是 if，两个规则都匹配且长度相同，此时靠规则优先级决定。
4.3 词法单元（）的定义与分类
是词法分析器的输出基本单位，通常用一个二元组或结构体表示：(类型, 属性值)。 类型是一个枚举值，标识该词法单元的种类；属性值则保存具体的文本内容或编译所需的信息（如整数值、字符串值、变量名）。
4.3.1 核心原理： 的五大分类
编程语言的 通常分为以下五类：
- 关键字（Keyword）：语言保留字，如
if、else、while、return。它们具有固定含义，不能作为标识符使用。 - 标识符（Identifier）：用户定义的变量名、函数名、类型名等，遵循特定的命名规则。
- 字面量（Literal）：直接表示值的常量，包括整数（
42）、浮点数（3.14）、字符（'a'）、字符串（"hello"）和布尔值（true/false）。 - 运算符（Operator）：表示运算的符号，如算术运算符
+、-、*、/，关系运算符==、!=、<、>，逻辑运算符&&、||、!等。 - 分隔符（Separator）：用于分隔语法成分的符号，如分号
;、逗号,、括号()、花括号{}、方括号[]等。
4.3.2 判断方法：如何为 分类
分类的核心依据是语言的词法规范。例如，C 语言中 sizeof 是关键字，但在某些脚本语言中它可能是普通函数名。分类时需注意：
- 先识别字符模式（正则表达式），再映射到 类型。
- 关键字和标识符的字符模式相同（都是字母开头），必须通过查表区分。
- 运算符可能由多个字符组成（如
==、<=），需要采用“最长匹配”原则，避免将==拆成两个=。
4.3.3 实战场景： 属性值的存储
对于标识符，属性值通常存储其字符串名称；对于整数字面量，属性值存储其数值（而非原始文本）；对于字符串字面量，属性值存储去除引号和转义后的实际字符串内容。这种设计使得后续的语法分析和代码生成阶段无需重新解析文本。
风险提示：若 属性值直接存储原始文本，则在语义分析阶段需要反复进行字符串到数值的转换，降低编译效率。建议在词法分析阶段完成必要的转换，并将结果存入属性值。
4.4 词法分析器的输出格式
词法分析器的输出是 流，其格式设计直接影响语法分析器的接口复杂度。常见的输出格式有三种：二元组、三元组和结构化对象。
4.4.1 核心原理：三种输出格式对比
| 格式 | 表示方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| 二元组 | (类型, 属性值) | 简洁，易于实现 | 缺少位置信息，调试困难 | 教学编译器、原型验证 |
| 三元组 | (类型, 属性值, 位置) | 包含行号/列号，便于报错 | 位置信息占用额外空间 | 生产级编译器 |
| 结构化对象 | 类实例，含类型、值、行列、文件等字段 | 扩展性强，可附加注释、宏展开信息 | 内存开销较大 | 现代编译器（如 GCC、Clang） |
4.4.2 操作流程：设计 结构体
以 C 语言实现为例，一个实用的 结构体定义如下：
typedef enum {
_KEYWORD, // 关键字
_IDENTIFIER, // 标识符
_INT_LITERAL, // 整数字面量
_FLOAT_LITERAL,// 浮点字面量
_STRING_LITERAL,// 字符串字面量
_OPERATOR, // 运算符
_SEPARATOR, // 分隔符
_EOF // 文件结束
} TokenType;
typedef struct {
TokenType type; // 类型
char* lexeme; // 原始文本（词素）
int int_val; // 整数值（若为整数）
double float_val; // 浮点值（若为浮点）
char* str_val; // 字符串值（若为字符串）
int line; // 行号
int column; // 列号
} ;词法分析器的主循环通常为：读取字符 → 跳过空白和注释 → 根据当前字符选择匹配规则 → 执行 DFA 匹配 → 生成 → 返回给语法分析器。当遇到无法匹配的字符时，应报告“非法字符”错误并尝试恢复。
4.4.3 案例拆解：一个简单词法分析器的输出
假设输入源代码为 int x = 42;，词法分析器的输出应为：
{ type: KEYWORD, lexeme: "int", line: 1, col: 1 }
{ type: IDENTIFIER, lexeme: "x", line: 1, col: 5 }
{ type: OPERATOR, lexeme: "=", line: 1, col: 7 }
{ type: INT_LITERAL, lexeme: "42", int_val: 42, line: 1, col: 9 }
{ type: SEPARATOR, lexeme: ";", line: 1, col: 11 }
{ type: EOF, lexeme: "", line: 1, col: 12 }注意，int 被识别为关键字而非标识符，因为它在关键字表中；42 的 int_val 字段被填充为数值 42，后续语法分析器可直接使用该值。
4.4.4 常见误区与总结
- 忽略空白与注释：空白字符（空格、制表符、换行）和注释通常被词法分析器丢弃，但必须正确识别注释边界（如
//和/* */），否则会导致后续 错位。 - 错误恢复策略：当遇到非法字符时，简单的做法是跳过该字符并继续；更稳健的做法是记录错误位置并尝试从下一个合法字符重新开始匹配。
- 流与语法分析器的交互：词法分析器通常作为语法分析器的子程序被调用（即“语法分析器驱动”模式），每次请求时返回下一个 ；也可以一次性生成全部 存入数组。
总结复盘：词法分析的核心在于“用正则描述规则，用自动机实现匹配，用 承载信息”。掌握从 RE → NFA → DFA 的转换逻辑，理解 分类的边界条件，并设计合理的输出格式，是构建高质量词法分析器的关键。建议读者动手实现一个支持整数、标识符、运算符和分隔符的最小词法分析器，通过实际调试加深对最长匹配和关键字优先级的理解。