4. 正则表达式到NFA：Thompson构造法
正则表达式怎么变成自动机？这是编译原理里一个很经典的问题。我刚开始学的时候，总觉得这步很玄乎——明明是一串字符，怎么就变成一张图了？
其实说白了，Thompson构造法就是一套「搭积木」的规则。你给它一个正则表达式，它给你一个NFA。而且这个NFA有个特点：只有一个开始状态，一个接受状态。这个特性在后面做子集构造时会特别方便。
4.1 为什么需要Thompson构造法？
你想想看，正则表达式是人写的，但计算机不认识。计算机只认识状态和跳转。所以我们需要一个桥梁——把正则表达式翻译成NFA。
Thompson构造法就是这座桥。它由Ken Thompson在1968年提出，后来成了lex等词法分析器的核心算法。我在做编译器前端时，就亲手实现过这个算法。嗯，踩过不少坑，后面会讲到。
4.2 基本构造规则
Thompson构造法对每种正则表达式操作都有对应的NFA模板。我们一个一个来看。
4.2.1 空串 ε
最简单的正则表达式就是空串。它的NFA长这样：
开始状态 --ε--> 接受状态就两个状态，一条ε边。没什么好说的。
4.2.2 单个字符 a
对于单个字符，比如 'a'，NFA就是：
开始状态 --a--> 接受状态也是两个状态，一条标有 'a' 的边。
4.2.3 连接操作 r1r2
连接操作就是把两个NFA串起来。假设r1的NFA是N1，r2的NFA是N2。那么r1r2的NFA就是：
N1的开始状态 --...--> N1的接受状态 --ε--> N2的开始状态 --...--> N2的接受状态说白了，就是把N1的接受状态和N2的开始状态用ε边连起来。N1的接受状态不再是接受状态了，N2的接受状态才是最终的接受状态。
4.2.4 选择操作 r1|r2
选择操作表示「要么r1，要么r2」。它的NFA结构是：
--ε--> N1的开始状态 --...--> N1的接受状态
/ \
新的开始状态 --ε--> 新的接受状态
\ /
--ε--> N2的开始状态 --...--> N2的接受状态这里需要引入一个新的开始状态和一个新的接受状态。从新开始状态有两条ε边，分别指向N1和N2的开始状态。N1和N2的接受状态各有一条ε边指向新的接受状态。
我曾经在实现选择操作时犯过一个错误：忘了加新的接受状态，直接把N1和N2的接受状态合并了。结果导致某些路径走不通。嗯，这个坑我替你们踩过了。
4.2.5 重复操作 r*
重复操作表示「零次或多次」。它的NFA结构是：
--ε--> N的开始状态 --...--> N的接受状态 --ε--
/ \
新的开始状态 --> 新的接受状态
\ /
--------------------ε--------------------------这里的关键是两条ε边：一条从新的开始状态直接到新的接受状态（表示零次），另一条从N的接受状态回到N的开始状态（表示多次）。
4.3 构造步骤总结
好了，有了上面的基本模板，构造任意正则表达式的NFA就变成了一个递归过程：
- 解析正则表达式：把它拆成基本操作（字符、连接、选择、重复）
- 对每个基本操作：用对应的NFA模板构造
- 组合子NFA：按照正则表达式的结构，把子NFA组合起来
- 得到最终NFA：只有一个开始状态和一个接受状态
这个过程可以用语法分析树来驱动。每个节点对应一个操作，递归地构造子NFA，然后组合。
4.4 完整示例：构造 (a|b)*abb 的NFA
我们来走一遍完整的例子。这个正则表达式匹配的是：任意多个a或b，后面跟abb。
第一步：解析结构
- 整体是连接操作：(a|b)* 和 abb
- (a|b)* 是重复操作，里面是选择操作 a|b
- abb 是三个字符的连接
第二步：从内向外构造
先构造 a|b 的NFA：
--ε--> [1] --a--> [2] --ε--
/ \
[0] [5]
\ /
--ε--> [3] --b--> [4] --ε--然后构造 (a|b)* 的NFA：
--ε--> [1] --a--> [2] --ε--
/ \ / \
[0] --ε--> [5] -- [6]
\ / \ /
--ε--> [3] --b--> [4] --ε--
\ /
------ε--------最后构造整个 (a|b)*abb 的NFA：
(a|b)* 的NFA --ε--> [7] --a--> [8] --b--> [9] --b--> [10]其中[10]是最终的接受状态。
关键点：这个NFA有10个状态。虽然看起来复杂，但每个部分都是按照模板搭出来的。你只要记住模板，就能构造任意复杂的正则表达式。
4.5 我踩过的坑
做Thompson构造法时，有几个地方特别容易出错：
- ε边太多：每个操作都引入ε边，导致NFA状态数爆炸。其实有些ε边可以优化掉，但Thompson构造法为了保持结构统一，故意保留了所有ε边。
- 接受状态搞混：组合NFA时，子NFA的接受状态要重新标记。我刚开始实现时，忘了把子NFA的接受状态改为非接受，结果导致匹配提前结束。
- 重复操作的边界：r*的NFA中，从新开始状态到新接受状态的ε边表示「零次」。这条边不能少，否则r*就无法匹配空串。
4.6 知识体系图
下面这张图展示了Thompson构造法的核心逻辑：
这张图展示了Thompson构造法的三个核心步骤：解析结构、应用模板、组合子NFA。每一步都有明确的输入输出，你照着这个流程走，就不会乱。
4.7 小结
Thompson构造法其实不复杂。记住四个模板，然后递归地搭积木就行。我当年实现这个算法时，花了大概两天时间。第一天理解模板，第二天写代码。调试时遇到几个bug，但都是上面提到的那些坑。
你如果自己动手实现一遍，会发现对NFA的理解会深很多。别怕，试试看。
可可精品资料库