正则表达式引擎核心：Thompson构造法原理与NFA实现详解

1. 从正则表达式到自动机：为什么我们需要Thompson构造法

如果你写过代码，几乎不可能没用过正则表达式。无论是验证用户输入的邮箱格式、从日志里提取特定信息，还是做复杂的文本替换，正则表达式都是程序员工具箱里的瑞士军刀。但你想过没有，当你写下a(b|c)*d这样一个看似简单的模式时，计算机底层是如何理解它，并在一大段文本里飞速找到匹配项的呢？

这背后，就是编译原理中一个经典且优雅的算法在起作用：Thompson构造法。它的核心任务，是将对人类友好的、声明式的正则表达式，转换成一个对计算机友好的、可执行的数学模型——非确定有限自动机。简单来说，它搭建了一座桥，桥的一头是你写的文本模式，另一头是一个可以“跑起来”的状态机。

为什么非得绕这个弯子？直接解释执行正则表达式不行吗？理论上可以，但效率会非常低下。NFA（以及后续可以进一步转换成的DFA）是一种经过严格数学定义的抽象机器，它有明确的状态和转移规则。一旦构建完成，就可以用固定的、高效的算法（比如子集构造法、模拟执行算法）来驱动它处理输入字符串。Thompson构造法的价值就在于，它提供了一套系统、机械的规则，确保任何正则表达式都能被无误地转换成一个等价的NFA。这个NFA就是后续所有匹配、优化、乃至编译成更高效代码的基石。

我最初接触这个概念时，觉得它有点“学院派”，离实际开发很远。直到有一次，我需要为一个内部工具实现一个自定义的、支持部分正则特性的简单模式匹配器。当我试图手写解析逻辑时，代码迅速变得复杂且漏洞百出。这时我才回头去认真研究了Thompson构造法，按照它的步骤一步步构建NFA，再实现一个简单的NFA模拟器，整个匹配引擎的核心逻辑变得异常清晰和健壮。这次经历让我深刻体会到，理解这个“造轮子”的过程，不仅能让你更懂正则引擎的内部原理，更能让你在需要定制文本处理逻辑时，拥有从理论到实践的完整工具箱。

2. 理解基石：正则表达式、NFA与DFA的核心概念拆解

在深入Thompson构造法的具体步骤之前，我们必须先统一语言，搞清楚几个核心概念到底是什么，以及它们之间的关系。这就像盖房子前得先认识砖、瓦和水泥。

2.1 正则表达式：人类描述模式的语法糖

正则表达式是一套形式化的语言，用于描述字符串的集合（称为“正则语言”）。我们常用的语法，如连接（ab）、选择（a|b）、闭包（a*）、可选（a?）等，都是它的运算符。例如：

• a： 表示只包含单个字符“a”的字符串集合{“a”}。
• a|b： 表示集合{“a”, “b”}。
• a*： 表示由零个或多个“a”组成的字符串集合{“”, “a”, “aa”, “aaa”, …}。
• ab： 表示字符串“a”后面紧跟着“b”，集合为{“ab”}。

正则表达式很强大，但它只是一个“声明”。计算机无法直接拿着这个字符串去匹配，它需要一种可以“运行”的模型。

2.2 有限自动机：计算机执行模式的数学模型

有限自动机就是这样一个模型。它就像一个拥有有限内存（状态）的小机器人，从左到右读取输入字符串的每个字符，并根据当前状态和读入的字符，决定下一步转移到哪个状态。它分为两种：

1. NFA（非确定有限自动机）： 这是Thompson构造法的直接产出。NFA的“非确定性”体现在：

   • ε-转移： 可以不消耗任何输入字符就从一个状态跳到另一个状态。这就像程序里的“无条件跳转”。
   • 多路转移： 对于同一个输入字符，从一个状态可能有多条出路。机器需要“猜测”走哪一条。
   • 接受条件： 如果存在至少一条路径，使得读完整个输入字符串后，机器处于某个“接受状态”，那么整个输入就被接受（匹配成功）。

   NFA的结构更贴近正则表达式的直观构造，易于从正则表达式生成，但模拟运行起来相对复杂，因为需要管理所有的可能性（即“并行”探索多条路径）。

2. DFA（确定有限自动机）： 这是经过优化后的形态，通常由NFA通过“子集构造法”转换而来。DFA的特点是：

   • 无ε-转移。
   • 确定转移： 对于任何一个状态和任何一个输入字符，有且只有一条转移路径。
   • 接受条件： 读完输入字符串后，机器所处的唯一状态如果是接受状态，则匹配成功。

   DFA的运行效率极高（一次只走一条路，时间复杂度是O(n)），但直接从复杂的正则表达式构造DFA往往比较困难，且状态数可能呈指数级增长（尽管可以通过算法优化）。

2.3 三者的关系链

它们的关系是一条清晰的编译流水线：正则表达式 -(Thompson构造法)-> NFA -(子集构造法)-> DFA -(最小化算法)-> 最小DFA

Thompson构造法是这条流水线的第一站。它负责将灵活但难以直接执行的正则表达式，翻译成结构规整、易于进行下一步处理的NFA。理解了这个定位，我们就能明白，Thompson构造法本身不追求产生最精简或最高效的自动机，它追求的是正确性、机械性和模块化——确保转换过程绝对可靠，并且可以像搭积木一样处理复杂的表达式。

注意：很多现代正则引擎（如PCRE、Pythonre）为了支持反向引用等非正则特性，并不完全使用纯DFA，而是使用NFA模拟回溯算法。但Thompson构造法及其思想，仍然是理解自动机理论、构建高效纯正则匹配器的基石。

3. Thompson构造法：一步步搭起NFA的积木

Thompson构造法的精妙之处在于它的递归和组合性。它定义了几种基本NFA模块，分别对应正则表达式的原子操作（基本字符、连接、选择、闭包），然后像搭乐高一样，将这些模块按照表达式的结构组合起来，最终形成一个完整的大NFA。

我们先定义NFA的表示法。一个NFA可以由一个五元组(Q, Σ, δ, q0, F)定义，但在构造过程中，我们更关心其图形化表示：

• 圆圈代表状态，圆圈内可标号（如S0,S1）。
• 箭头代表转移。箭头上标注消耗的字符（如a），或ε表示空转移。
• 单圆圈是普通状态，双圆圈是接受状态。
• 有一个没有来源的箭头指向起始状态。

下面我们来看每一种基本构造规则。

3.1 基本单元：匹配单个字符

这是最简单的模块。对于正则表达式中的单个字符a（a∈ Σ），构造一个具有两个状态和一条转移边的NFA。

a S0 -----> S1

• S0是起始状态。
• S1是接受状态（双圈）。
• 从S0到S1有一条标有字符a的转移边。

这个NFA只接受一个字符串：“a”。在代码实现中，我们通常用两个状态节点和一条边来表示这个结构。

3.2 连接操作：AB

假设我们已经为子表达式A和B分别构造了NFA，记为N(A)和N(B)。N(A)的接受状态集为F_A，N(B)的起始状态为q_B。

连接操作AB的NFA构造方法是：将N(A)的所有接受状态，通过 ε-转移，连接到N(B)的起始状态。然后，N(A)的起始状态作为新NFA的起始状态，N(B)的接受状态集作为新NFA的接受状态集。

N(A)的内部结构... --> [F_A] --ε--> [q_B] --> N(B)的内部结构...

为什么这样做？因为要匹配AB，必须先完整匹配A，然后紧接着匹配B。ε-转移在这里起到了“胶水”的作用。当N(A)运行到接受状态时，意味着A部分已经匹配成功。此时，通过不消耗输入字符的 ε-转移，自动机可以“无缝”地进入N(B)的起始状态，开始尝试匹配B部分。这完美模拟了连接语义。

3.3 选择操作：A|B

为子表达式A和B构造好N(A)和N(B)后，选择操作A|B的NFA构造如下：

1. 创建一个新的起始状态S_new。
2. 从S_new分别添加两条 ε-转移，一条指向N(A)的起始状态，另一条指向N(B)的起始状态。
3. 创建一个新的接受状态F_new。
4. 从N(A)的所有接受状态分别添加 ε-转移指向F_new。
5. 从N(B)的所有接受状态分别添加 ε-转移指向F_new。
6. S_new是新NFA的起始状态，F_new是唯一的接受状态。N(A)和N(B)原有的接受状态均变为普通状态。

ε +------> [N(A) Start] --> ... --> [N(A) Old Accept] --+ | | [S_new] +--ε--> [F_new] | | +------> [N(B) Start] --> ... --> [N(B) Old Accept] --+ ε

为什么这样做？选择意味着“要么A，要么B”。新的起始状态S_new通过 ε-转移提供了这个“选择”分支，机器可以非确定性地决定走A路径还是B路径。无论走哪条路径，最终都需要到达一个共同的终点F_new来表示匹配成功。原有的接受状态被“短路”掉，是为了确保整个大NFA只有一个统一的接受点，便于管理。

3.4 闭包操作：A*

克林闭包A*表示“零次或多次A”。它的NFA构造最为巧妙：

1. 创建一个新的起始状态S_new，它同时也是一个接受状态（因为零次匹配是允许的）。
2. 创建一个新的接受状态F_new。
3. 从S_new添加一条 ε-转移指向N(A)的起始状态。
4. 从N(A)的所有接受状态添加 ε-转移，指回N(A)的起始状态（实现“多次”循环）。
5. 从N(A)的所有接受状态添加 ε-转移，指向F_new（实现“结束循环”）。
6. 从S_new添加一条 ε-转移直接指向F_new（实现“零次”匹配）。
7. S_new是新NFA的起始状态，F_new是唯一的接受状态。

ε +-------------------+ | | | +---ε---> [N(A) Start] --> ... --> [N(A) Old Accept] | | | | [S_new] (也是接受态) +----+ | | | | ε | | | v | +------------ε-------------------------+ [F_new] | (零次路径) +-------------------ε------------------------->

为什么这样设计？这个结构提供了三种可能：

• 零次：直接从S_new经 ε-转移到达F_new。
• 一次：从S_new进入N(A)，匹配一次A后，从其接受状态经 ε-转移到达F_new。
• 多次：从N(A)的接受状态经 ε-转移指回其起始状态，形成循环，可以匹配多次A，最后再跳到F_new。

S_new本身是接受态，确保了空字符串ε被接受。这个设计将“循环”和“跳过”的语义通过 ε-转移清晰地表达了出来。

3.5 可选操作与正闭包

掌握了以上三种核心操作，其他常用操作都可以推导出来：

• 可选A?： 等价于A|ε。你可以用选择操作的构造法，其中N(B)是一个匹配空串 ε 的NFA（即一个既是起始又是接受的状态）。
• 正闭包A+： 等价于AA*。先构造N(A)，再构造N(A*)，然后用连接操作将它们组合起来。

4. 实战推演：从正则表达式(a|b)*c到NFA

让我们用一个具体的例子，把上面的积木搭起来。假设我们要为正则表达式(a|b)*c构造NFA。

步骤1：分解表达式这个表达式可以看作X*和c的连接，其中X = (a|b)。所以我们先构造最内层的a和b，再构造(a|b)，接着构造(a|b)*，最后与c连接。

步骤2：构造原子NFA

• N(a):

  a S0 --> S1

• N(b):

  b S2 --> S3

  （注意：这里用了不同的状态编号 S2, S3，以示区别，实际构造中状态需要全局唯一管理）

步骤3：构造N(a|b)

1. 新建起始状态S4，新建接受状态S5。
2. S4通过 ε 连到N(a)的起始状态S0。
3. S4通过 ε 连到N(b)的起始状态S2。
4. N(a)的接受状态S1通过 ε 连到S5。
5. N(b)的接受状态S3通过 ε 连到S5。

图形化表示（简化）：

ε a ε S4 --> S0 --> S1 --+ | +--> S5 | ε b ε +--> S2 --> S3 --+

步骤4：构造N((a|b)*)

1. 新建起始状态S6（它也是接受态），新建接受状态S7。
2. S6通过 ε 连到N(a|b)的起始状态S4。
3. N(a|b)的接受状态S5通过 ε 连回S4（实现循环）。
4. N(a|b)的接受状态S5通过 ε 连到S7（结束循环）。
5. S6通过 ε 直接连到S7（零次匹配）。

步骤5：构造N(c)

c S8 --> S9

步骤6：构造最终的N((a|b)*c)使用连接操作，将N((a|b)*)的接受状态S7，通过 ε-转移，连接到N(c)的起始状态S8。

• 最终NFA的起始状态是S6。
• 最终NFA的接受状态是N(c)的接受状态S9。

这样，我们就得到了一个完整的、可能包含十几个状态和众多 ε-转移的NFA。这个NFA可以接受诸如“c”,“ac”,“bc”,“aabac”,“bbbc”等字符串。

实操心得：手工画这样的图很容易乱。在实际编程实现时，我们通常用数据结构（如状态节点列表、转移边列表）来表示NFA。构造过程就是递归地创建和组合这些节点与边。为每个新状态生成全局唯一的ID是避免混乱的关键。

5. 从理论到代码：NFA的表示与模拟执行

理解了构造原理，下一步就是如何在计算机中表示它，并让它“跑”起来。这是将理论转化为实用工具的关键一步。

5.1 数据结构设计

一个典型的NFA可以这样定义（以Python为例）：

class State: def __init__(self, is_accepting=False): self.id = id(self) # 或用全局计数器 self.is_accepting = is_accepting self.transitions = {} # key: 字符/‘ε‘, value: list of State class NFA: def __init__(self, start_state, accept_state): self.start_state = start_state self.accept_state = accept_state # 对于Thompson构造，我们常维护单个接受状态

• State类代表一个状态。transitions字典存储转移关系，因为一个状态对同一个字符可能有多个转移目标（非确定性），所以用列表存储。
• NFA类封装一个自动机，通常持有起始状态和接受状态的引用。在Thompson构造中，我们通过构造规则总能得到一个唯一的起始和接受状态（即使内部有多个接受态，最终也会被整合）。

5.2 核心算法：ε-闭包与模拟执行

NFA的模拟执行之所以复杂，是因为 ε-转移和多路转移。核心思想是：不是跟踪单个当前状态，而是跟踪一个“当前可能的状态集合”。

1. ε-闭包： 给定一个状态集合T，ε-closure(T)定义为从T中任一状态出发，只通过若干条 ε-转移所能到达的所有状态的集合。这包括T自身。这个操作是NFA模拟的基石。

   def epsilon_closure(states): closure = set(states) stack = list(states) while stack: s = stack.pop() for next_state in s.transitions.get('ε', []): if next_state not in closure: closure.add(next_state) stack.append(next_state) return closure

2. 模拟执行算法：

   • 初始化： 当前状态集合current_states = ε-closure({start_state})。
   • 读入字符： 对于输入字符串中的每个字符ch：
     1. 从current_states中的每个状态出发，寻找所有标有ch的转移，得到目标状态集合next_states。
     2. 计算新的当前状态集合：current_states = ε-closure(next_states)。
   • 判断接受： 读完所有字符后，检查current_states中是否包含至少一个接受状态。若有，则匹配成功。

def simulate_nfa(nfa, input_string): current_states = epsilon_closure({nfa.start_state}) for ch in input_string: next_states = set() for state in current_states: next_states.update(state.transitions.get(ch, [])) current_states = epsilon_closure(next_states) if not current_states: # 没有可达状态，提前失败 return False # 检查最终状态集合中是否有接受状态 return any(state.is_accepting for state in current_states)

5.3 一个简单的构造器实现示例

结合上面的数据结构和算法，我们可以实现一个简化的Thompson构造器。这里以连接操作为例：

def build_char_nfa(c): """构造匹配单个字符c的NFA""" start = State() accept = State(is_accepting=True) start.transitions[c] = [accept] return NFA(start, accept) def concat_nfa(nfa1, nfa2): """连接两个NFA: nfa1 nfa2""" # 将nfa1的接受状态改为普通状态，并连接到nfa2的起始状态 nfa1.accept_state.is_accepting = False nfa1.accept_state.transitions.setdefault('ε', []).append(nfa2.start_state) # 新的NFA以nfa1的起始状态为起始，以nfa2的接受状态为接受 return NFA(nfa1.start_state, nfa2.accept_state) # 类似地，可以实现 union_nfa, star_nfa 等函数。

踩坑实录：在实现epsilon_closure时，我最初用了递归，对于复杂NFA很容易栈溢出。后来改用显式栈（或队列）的迭代方法，问题就解决了。另外，管理状态ID时要非常小心，特别是在组合NFA时，确保不会意外地修改了已构建好的子NFA的内部状态，除非这正是构造规则要求的（如连接操作中修改接受状态）。

6. Thompson构造法的局限性与实际应用中的考量

Thompson构造法优美而强大，但它并非完美，在实际的正则表达式引擎实现中，工程师们会根据需求做出各种调整和优化。

6.1 局限性分析

1. ε-转移泛滥： 构造出的NFA包含大量ε-转移。这些转移不匹配任何字符，但在模拟执行时需要反复计算ε-闭包，增加了运行时开销。
2. 状态数膨胀： 每个基本操作（尤其是选择|和闭包*）都会引入新的起始和接受状态，导致最终NFA的状态数可能是原始表达式长度的数倍。
3. 非确定性： 模拟执行需要维护一个状态集合并进行多路径探索，虽然算法清晰，但效率不如DFA。

6.2 优化与变体

正因为有这些局限性，实际应用中很少直接使用Thompson原教旨主义NFA进行匹配。常见的优化路径是：

1. 转换为DFA（子集构造法）： 这是最经典的优化。将NFA（特别是Thompson NFA）转换为DFA，可以消除非确定性和ε-转移，获得一个确定性的、运行效率极高的自动机。虽然转换过程可能导致状态数爆炸（最坏情况指数级），但对于大多数实际的正则表达式，产生的DFA状态数是可接受的。许多高效的正则引擎（如grep、lex）在内部使用DFA或DFA族。
2. NFA模拟优化： 对于支持复杂功能（如捕获组、反向引用）的引擎，它们通常坚持使用NFA模拟，但会采用优化策略：
   • 延迟计算： 不是每一步都计算完整的ε-闭包，而是按需计算。
   • 缓存： 缓存常见的ε-闭包计算结果。
   • “汤普森NFA”的现代实现： Rob Pike和Ken Thompson在1968年论文中描述的方法，经过精心实现，其速度可以与DFA媲美，同时保留了NFA的灵活性。Russ Cox的系列文章《Regular Expression Matching Can Be Simple And Fast》对此有精彩阐述。
3. 混合引擎： 一些引擎（如Google的RE2）会先尝试用DFA进行快速匹配，如果DFA无法处理（如包含反向引用），则回退到NFA模拟。

6.3 在编译器与工具中的应用

Thompson构造法的直接应用场景远不止正则表达式匹配：

1. 词法分析器生成器（如Lex/Flex）： 这些工具的核心就是将用户定义的一组词法规则（本质是正则表达式）分别转换为NFA，然后合并成一个大NFA，再转换为DFA，最终生成高效的词法分析器C代码。
2. 搜索引擎与文本编辑器： 早期的grep命令就是基于Thompson NFA转换为DFA的原理实现的，速度极快。许多高性能的文本搜索库也借鉴了这一思想。
3. 协议分析与网络入侵检测： 在深度包检测中，需要匹配大量的模式，将规则集编译成DFA可以极大提升匹配速度。

理解Thompson构造法，不仅仅是学习一个算法，更是掌握了一种“将声明式规范转换为可执行状态机”的通用思维模式。这种模式在解析、匹配、监控等众多领域都有用武之地。当你下次再使用正则表达式时，或许可以想一想，你写下的那串符号，正在你看不见的地方，经历着这样一场奇妙的变形之旅。