第四章：正则表达式与自动机——从文本到状态机的魔法

说实话，编译器前端最让我着迷的部分，就是词法分析这一块。你想想看，一堆乱七八糟的字符流，怎么就能被识别成有意义的单词？这背后靠的就是正则表达式和自动机理论。今天我就带你把这套东西彻底搞明白。

4.1 正则表达式到NFA：Thompson构造法

我记得刚学编译器那会儿，看到Thompson构造法觉得特别神奇。它能把任何正则表达式，转化成等价的NFA。说白了，就是给每个正则操作都配一套固定的NFA模板。

基本的构造规则其实就几条：

• 空串ε：直接一个开始状态到接受状态的ε边
• 单个字符a：开始状态通过a到接受状态
• 连接AB：把A的接受状态和B的开始状态合并
• 选择A|B：新开始状态通过ε边分别到A和B的开始状态
• 闭包A*：新开始状态既是接受状态，又通过ε边到A的开始状态

举个例子，正则表达式 a(b|c)* 的NFA构造过程：

1. 构造 a 的NFA：  [0] --a--> [1]
2. 构造 (b|c) 的NFA：
   [2] --ε--> [3] --b--> [4] --ε--> [5]
   [2] --ε--> [6] --c--> [7] --ε--> [5]
3. 构造 (b|c)* 的NFA：
   [8] --ε--> [2] ... [5] --ε--> [8]
   [8] 也是接受状态
4. 连接 a 和 (b|c)*：
   [1] --ε--> [8]

嗯，这里要注意：Thompson构造法生成的NFA有个特点——每个状态最多有两个出边，而且ε边特别多。这为后续的NFA到DFA转换埋下了伏笔。

4.2 NFA到DFA：子集构造法

NFA虽然构造简单，但执行起来效率低。为啥？因为一个状态可能同时走多条路径。DFA就不一样了，每个输入字符只有一条确定的路径。

子集构造法的核心思路：把NFA的状态集合，映射成DFA的单个状态。

具体步骤我总结成三步：

1. 计算ε闭包：从一个状态出发，所有能通过ε边到达的状态集合
2. 计算转移：对每个输入字符，计算当前状态集经过该字符能到达的状态集
3. 重复直到没有新状态集出现

来看个具体例子。假设NFA有状态{0,1,2}，其中0通过a到1，1通过ε到2。那么：

ε-closure(0) = {0, 1, 2}  // 因为0→1→2都是ε可达
move({0,1,2}, a) = {3, 4}  // 假设3和4是a转移的目标
ε-closure({3,4}) = {3, 4, 5}  // 继续计算ε闭包

你想想看，这个过程其实就是在做状态集的幂集构造。最坏情况下，DFA的状态数可能达到2^n，但实际中远小于这个数。

4.3 DFA的最小化

DFA构造完了，但往往不是最简的。有些状态其实是等价的，可以合并。最小化的目的就是找出这些等价状态。

我常用的方法是填表算法：

• 先把所有状态对标记为「可能等价」
• 然后反复检查：如果两个状态对同一个输入字符转移到不同等价类的状态，那它们就不等价
• 直到没有新的不等价对出现

举个例子，假设DFA有状态A、B、C，其中C是接受状态：

初始划分：{A, B} 和 {C}
检查A和B：对输入a，A→C，B→C（都到接受状态，暂时等价）
          对输入b，A→B，B→A（都在非接受状态集内，暂时等价）
所以A和B等价，可以合并

我个人习惯在最小化之后，再手动检查一遍所有转移是否完整。有时候最小化会暴露一些死状态，需要补上默认的出错转移。

4.4 词法分析器生成工具：Lex/Flex

理论讲完了，来点实际的。Lex（及其GNU版本Flex）就是基于上述理论的词法分析器生成工具。你写正则表达式，它帮你生成C代码。

一个典型的Lex文件结构：

%{
// C代码头，比如头文件、全局变量
#include <stdio.h>
%}

%%
// 规则部分：正则表达式 + 动作
"if"        { return IF; }
"then"      { return THEN; }
[a-zA-Z]+   { return ID; }
[0-9]+      { return NUM; }
[ \t\n]     { /* 跳过空白 */ }
.           { printf("非法字符: %c\n", yytext[0]); }

%%
// C代码尾，比如main函数
int main() {
    yylex();
    return 0;
}

Flex的工作原理，其实就是把我们前面讲的理论串起来了：

• 把每条正则表达式用Thompson构造法转成NFA
• 用子集构造法把NFA合并成DFA
• 对DFA做最小化
• 生成C代码，用表驱动或直接编码的方式执行匹配

我记得第一次用Flex生成词法分析器时，看到它自动处理了那么多细节，真心佩服前人的智慧。你只需要关注「匹配什么模式」和「匹配后做什么」，剩下的交给工具。

本章小结

这一章我们走完了从正则表达式到词法分析器的完整路径：

步骤	输入	输出	核心算法
1	正则表达式	NFA	Thompson构造法
2	NFA	DFA	子集构造法
3	DFA	最小化DFA	填表算法
4	正则规则	词法分析器	Lex/Flex

说白了，这些理论不是空中楼阁。你写的每一行Lex规则，背后都在经历这些转换。理解了底层原理，遇到问题才能快速定位。

嗯，这一章的内容就到这。代码写多了，回头看看这些基础理论，反而觉得更有味道。