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 有限自动机计算机执行模式的数学模型有限自动机就是这样一个模型。它就像一个拥有有限内存状态的小机器人从左到右读取输入字符串的每个字符并根据当前状态和读入的字符决定下一步转移到哪个状态。它分为两种NFA非确定有限自动机 这是Thompson构造法的直接产出。NFA的“非确定性”体现在ε-转移 可以不消耗任何输入字符就从一个状态跳到另一个状态。这就像程序里的“无条件跳转”。多路转移 对于同一个输入字符从一个状态可能有多条出路。机器需要“猜测”走哪一条。接受条件 如果存在至少一条路径使得读完整个输入字符串后机器处于某个“接受状态”那么整个输入就被接受匹配成功。NFA的结构更贴近正则表达式的直观构造易于从正则表达式生成但模拟运行起来相对复杂因为需要管理所有的可能性即“并行”探索多条路径。DFA确定有限自动机 这是经过优化后的形态通常由NFA通过“子集构造法”转换而来。DFA的特点是无ε-转移。确定转移 对于任何一个状态和任何一个输入字符有且只有一条转移路径。接受条件 读完输入字符串后机器所处的唯一状态如果是接受状态则匹配成功。DFA的运行效率极高一次只走一条路时间复杂度是O(n)但直接从复杂的正则表达式构造DFA往往比较困难且状态数可能呈指数级增长尽管可以通过算法优化。2.3 三者的关系链它们的关系是一条清晰的编译流水线正则表达式 -(Thompson构造法)- NFA -(子集构造法)- DFA -(最小化算法)- 最小DFAThompson构造法是这条流水线的第一站。它负责将灵活但难以直接执行的正则表达式翻译成结构规整、易于进行下一步处理的NFA。理解了这个定位我们就能明白Thompson构造法本身不追求产生最精简或最高效的自动机它追求的是正确性、机械性和模块化——确保转换过程绝对可靠并且可以像搭积木一样处理复杂的表达式。注意很多现代正则引擎如PCRE、Pythonre为了支持反向引用等非正则特性并不完全使用纯DFA而是使用NFA模拟回溯算法。但Thompson构造法及其思想仍然是理解自动机理论、构建高效纯正则匹配器的基石。3. Thompson构造法一步步搭起NFA的积木Thompson构造法的精妙之处在于它的递归和组合性。它定义了几种基本NFA模块分别对应正则表达式的原子操作基本字符、连接、选择、闭包然后像搭乐高一样将这些模块按照表达式的结构组合起来最终形成一个完整的大NFA。我们先定义NFA的表示法。一个NFA可以由一个五元组(Q, Σ, δ, q0, F)定义但在构造过程中我们更关心其图形化表示圆圈代表状态圆圈内可标号如S0,S1。箭头代表转移。箭头上标注消耗的字符如a或ε表示空转移。单圆圈是普通状态双圆圈是接受状态。有一个没有来源的箭头指向起始状态。下面我们来看每一种基本构造规则。3.1 基本单元匹配单个字符这是最简单的模块。对于正则表达式中的单个字符aa∈ Σ构造一个具有两个状态和一条转移边的NFA。a S0 ----- S1S0是起始状态。S1是接受状态双圈。从S0到S1有一条标有字符a的转移边。这个NFA只接受一个字符串“a”。在代码实现中我们通常用两个状态节点和一条边来表示这个结构。3.2 连接操作AB假设我们已经为子表达式A和B分别构造了NFA记为N(A)和N(B)。N(A)的接受状态集为F_AN(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构造如下创建一个新的起始状态S_new。从S_new分别添加两条 ε-转移一条指向N(A)的起始状态另一条指向N(B)的起始状态。创建一个新的接受状态F_new。从N(A)的所有接受状态分别添加 ε-转移指向F_new。从N(B)的所有接受状态分别添加 ε-转移指向F_new。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构造最为巧妙创建一个新的起始状态S_new它同时也是一个接受状态因为零次匹配是允许的。创建一个新的接受状态F_new。从S_new添加一条 ε-转移指向N(A)的起始状态。从N(A)的所有接受状态添加 ε-转移指回N(A)的起始状态实现“多次”循环。从N(A)的所有接受状态添加 ε-转移指向F_new实现“结束循环”。从S_new添加一条 ε-转移直接指向F_new实现“零次”匹配。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构造原子NFAN(a):a S0 -- S1N(b):b S2 -- S3注意这里用了不同的状态编号 S2, S3以示区别实际构造中状态需要全局唯一管理步骤3构造N(a|b)新建起始状态S4新建接受状态S5。S4通过 ε 连到N(a)的起始状态S0。S4通过 ε 连到N(b)的起始状态S2。N(a)的接受状态S1通过 ε 连到S5。N(b)的接受状态S3通过 ε 连到S5。图形化表示简化ε a ε S4 -- S0 -- S1 -- | -- S5 | ε b ε -- S2 -- S3 --步骤4构造N((a|b)*)新建起始状态S6它也是接受态新建接受状态S7。S6通过 ε 连到N(a|b)的起始状态S4。N(a|b)的接受状态S5通过 ε 连回S4实现循环。N(a|b)的接受状态S5通过 ε 连到S7结束循环。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_acceptingFalse): 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的模拟执行之所以复杂是因为 ε-转移和多路转移。核心思想是不是跟踪单个当前状态而是跟踪一个“当前可能的状态集合”。ε-闭包 给定一个状态集合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模拟执行算法初始化 当前状态集合current_states ε-closure({start_state})。读入字符 对于输入字符串中的每个字符ch从current_states中的每个状态出发寻找所有标有ch的转移得到目标状态集合next_states。计算新的当前状态集合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_acceptingTrue) 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 局限性分析ε-转移泛滥 构造出的NFA包含大量ε-转移。这些转移不匹配任何字符但在模拟执行时需要反复计算ε-闭包增加了运行时开销。状态数膨胀 每个基本操作尤其是选择|和闭包*都会引入新的起始和接受状态导致最终NFA的状态数可能是原始表达式长度的数倍。非确定性 模拟执行需要维护一个状态集合并进行多路径探索虽然算法清晰但效率不如DFA。6.2 优化与变体正因为有这些局限性实际应用中很少直接使用Thompson原教旨主义NFA进行匹配。常见的优化路径是转换为DFA子集构造法 这是最经典的优化。将NFA特别是Thompson NFA转换为DFA可以消除非确定性和ε-转移获得一个确定性的、运行效率极高的自动机。虽然转换过程可能导致状态数爆炸最坏情况指数级但对于大多数实际的正则表达式产生的DFA状态数是可接受的。许多高效的正则引擎如grep、lex在内部使用DFA或DFA族。NFA模拟优化 对于支持复杂功能如捕获组、反向引用的引擎它们通常坚持使用NFA模拟但会采用优化策略延迟计算 不是每一步都计算完整的ε-闭包而是按需计算。缓存 缓存常见的ε-闭包计算结果。“汤普森NFA”的现代实现 Rob Pike和Ken Thompson在1968年论文中描述的方法经过精心实现其速度可以与DFA媲美同时保留了NFA的灵活性。Russ Cox的系列文章《Regular Expression Matching Can Be Simple And Fast》对此有精彩阐述。混合引擎 一些引擎如Google的RE2会先尝试用DFA进行快速匹配如果DFA无法处理如包含反向引用则回退到NFA模拟。6.3 在编译器与工具中的应用Thompson构造法的直接应用场景远不止正则表达式匹配词法分析器生成器如Lex/Flex 这些工具的核心就是将用户定义的一组词法规则本质是正则表达式分别转换为NFA然后合并成一个大NFA再转换为DFA最终生成高效的词法分析器C代码。搜索引擎与文本编辑器 早期的grep命令就是基于Thompson NFA转换为DFA的原理实现的速度极快。许多高性能的文本搜索库也借鉴了这一思想。协议分析与网络入侵检测 在深度包检测中需要匹配大量的模式将规则集编译成DFA可以极大提升匹配速度。理解Thompson构造法不仅仅是学习一个算法更是掌握了一种“将声明式规范转换为可执行状态机”的通用思维模式。这种模式在解析、匹配、监控等众多领域都有用武之地。当你下次再使用正则表达式时或许可以想一想你写下的那串符号正在你看不见的地方经历着这样一场奇妙的变形之旅。