第 4 章 · 03 Thompson 构造:把正则编译成 NFA

第 4 章 · 03 Thompson 构造:把正则编译成 NFA

本节摘要:这是第 4 章的核心算法,也是最优雅的部分。Thompson 构造法(Ken Thompson 1968 年提出)解决的问题是:给定任意一个正则表达式,如何系统地把它编译成一个 NFA?它的思路极其优美——对正则的每种构造(连接、选择、闭包),给出对应的 NFA 片段模板,递归组合。掌握它,你就掌握了「把一种语言翻译成可执行机器」的核心功夫,这也是编译器前端(第 9 章)的微缩预演。

内容来源:基于正则理论与「Build your own X」Regex Engine 域整理的导读。

学习目标

阅读完本节,你应当能够:

1. 说清 Thompson 构造法解决的问题:把正则系统编译成 NFA。
2. 理解它的递归思路:对每种正则构造给一个 NFA 片段模板,组合而成。
3. 描述三种基本构造的模板:单字符、连接(ab)、选择(a|b)、闭包(a*)。
4. 理解这个算法是「编译器前端」的微缩版——把语言翻译成可执行形式。

一、学习价值:这是「语言→机器」的范本

Thompson 构造法之所以重要,不只因为它是正则引擎的基础,更因为它展示了一种通用模式:把一种语言(正则)系统地翻译成另一种可执行形式(NFA)。这种「语言→机器」的翻译,正是编译器的核心工作。第 9 章造编译器时,你会看到几乎相同的思路:对源码的每种语法构造,给出对应的中间表示片段,递归组合。

所以,理解 Thompson 构造,你不仅学会了造正则引擎,更预演了编译器前端的核心思想。这是本书把「正则引擎」放在第 4 章(在编译器第 9 章之前)的原因——它是一座桥。

二、子系统拆解:三种基本构造的 NFA 模板

Thompson 构造法的关键洞察:任何正则,无论多复杂,都由少数几种基本构造组合而成。只要为每种构造定义一个「NFA 片段模板」,就能递归地把整个正则编译成 NFA。

构造 1:单字符 a

新建两状态: 起始 → 接受, 转移标 a
   a
( ) ──► ( )
​

构造 2:连接 ab(先 a 后 b)

把 a 的 NFA 的接受状态,用 ε 转移接到 b 的 NFA 的起始状态:

a 的 NFA ──ε──► b 的 NFA
​

整体起始是 a 的起始,接受是 b 的接受。

构造 3:选择 a|b(a 或 b)

新建一个起始状态,用 ε 分叉到 a 和 b 两个 NFA;两者接受状态用 ε 汇到一个新接受状态:

        ┌──ε──► a 的 NFA ──ε──┐
起始 ──ε─┤                     ├─ε──► 接受
        └──ε──► b 的 NFA ──ε──┘
​

构造 4:闭包 a*(零个或多个 a)

新建起始与接受,起始 ε 到 a 的 NFA 起始,a 的接受 ε 回起始(循环)并 ε 到接受(跳过):

       ┌─────────ε─────────┐
       ▼                   │
起始 ──ε──► a 的 NFA ──ε──┬──► 接受
  └──────────ε────────────┘
   (起始也可直接 ε 到接受, 表示"零个 a")
​

递归组合

任何正则,先解析成抽象语法树(AST),再对 AST 递归应用上面的模板:

正则: (a|b)*c
AST:    concat( star(alt(a, b)), c )
应用模板: 先 alt(a,b) 用选择模板, 再 star(...) 用闭包模板, 最后与 c 用连接模板组合
得到一整台 NFA
​

这就是 Thompson 构造的全部——对每种构造应用模板,递归组合。

三、上手第一步:从最简单的开始

写代码前,先用纸笔练:

1. 手动构造 a、ab、a|b、a* 的 NFA(各用上面模板)。
2. 构造 (a|b)*(组合选择 + 闭包)。
3. 构造 ab*c(连接 + 闭包 + 连接)。

熟练后,代码实现就是:

1. 写正则解析器(把正则字符串解析成 AST;可借用递归下降,参考第 9 章)。
2. 对 AST 递归应用 Thompson 模板,生成 NFA(一组状态 + 转移表)。

本节要点回顾

1. Thompson 构造法:对正则的每种构造(字符/连接/选择/闭包)定义 NFA 片段模板,递归组合,把任意正则编译成 NFA。
2. 四种基本模板:单字符(线性)、连接(ε 串接)、选择(ε 分叉+汇合)、闭包(ε 循环+跳过)。
3. 递归过程:先把正则解析成 AST,再对 AST 递归应用模板。
4. 它是编译器前端的微缩:「语言→可执行机器」的翻译模式,第 9 章编译器会深化。

推荐上手顺序

1. 纸笔练习四种基本模板的 NFA 构造(字符/连接/选择/闭包)。
2. 练习组合:(a|b)*、ab*c、a(b|c)*d。
3. 写正则解析器(字符串→AST),这是前置(可参考第 9 章的递归下降)。
4. 对 AST 递归应用 Thompson 模板,生成 NFA 数据结构(状态表 + 转移)。
5. 验证:用生成的 NFA 跑几个输入,看接受/拒绝是否符合预期。

下一节讲匹配策略——把编译好的 NFA 用起来,以及 DFA 式与回溯式的取舍。