1. 项目概述从正则表达式到NFA的桥梁如果你写过代码尤其是处理过文本匹配、数据验证或者日志分析那你一定用过正则表达式。比如\d{3}-\d{8}匹配一个电话号码或者^[a-zA-Z0-9._%-][a-zA-Z0-9.-]\.[a-zA-Z]{2,}$匹配一个邮箱地址。我们把这些模式写出来交给编程语言的正则引擎它就能神奇地在一大段文本里找到我们想要的东西。但你想过没有这个引擎是怎么看懂你写的这一串“天书”的它怎么知道a|b是匹配 a 或者 b而ab*是匹配一个 a 后面跟着零个或多个 b这背后就是编译原理的魔法。正则表达式本身对人类来说是一种声明式的描述但对计算机来说它需要一种可以“执行”的、状态明确的计算模型。这个模型就是有限自动机。而Thompson 构造法就是实现这个魔法转换的第一步也是最经典、最直观的一步它能把我们手写的、结构复杂的正则表达式系统地、机械地转换成一个等价的非确定有限自动机。NFA 是什么你可以把它想象成一个迷宫里面有很多房间状态房间之间有各种单向通道状态转移有的通道上贴着字母输入符号有的通道是免费的ε-转移不需要消耗输入字符就能走。你从入口初态出发手里拿着待匹配的字符串每读一个字符就尝试走对应标签的通道。如果你能走到出口终态并且刚好把手里的字符用完那就匹配成功了。NFA 的“非确定性”体现在你可能同时站在好几个房间里因为有ε-转移面对一个字符时也可能有好几条路可以选。Thompson 构造法的精妙之处在于它把正则表达式的语法结构连接、选择、闭包拆解成一个个小的、标准的 NFA “积木块”然后像搭乐高一样按照表达式的结构把这些积木块组合起来最终拼成一个完整的大 NFA。这个方法由 Ken Thompson 在 1968 年提出不仅是理论上的瑰宝更是许多现实正则引擎如早期 grep、awk的实现基石。理解它你就能真正窥见正则表达式引擎的“五脏六腑”而不再把它当作一个黑盒。2. 核心概念与前置知识拆解在动手“搭积木”之前我们必须把工具箱里的零件认清楚。Thompson 构造法涉及几个核心的计算模型和概念理解它们之间的关系是看懂整个构造过程的关键。2.1 正则表达式我们写了什么正则表达式定义了一个字符串的集合称为“语言”。它的语法虽然在不同工具中略有扩展但其核心操作只有三种连接表达式AB表示语言A和语言B的连接。即先匹配一个来自A的字符串紧接着匹配一个来自B的字符串。这是默认操作不需要显式运算符。选择表达式A|B表示语言A和语言B的并集。即匹配A或者匹配B。克林闭包表达式A*表示语言A的零次或多次重复。即匹配空串或者一个A或者AA或者AAA以此类推。此外我们还有基本的原子单位空串 ε匹配一个长度为0的字符串。符号 a属于字母表 Σ匹配单个字符a。例如正则表达式(a|b)c*描述的语言是要么是a后面跟着零个或多个c要么是b后面跟着零个或多个c。字符串a,b,ac,bc,acc,bccc都属于这个语言。2.2 有限自动机机器如何“思考”有限自动机是正则表达式的计算模型。它分为两种NFA如前所述它的状态转移是“非确定”的。对于一个状态和一个输入符号包括 ε它可以有零个、一个或多个下一个状态。这种不确定性使得它的设计非常灵活和直观Thompson 构造法生成的就是 NFA。DFA确定有限自动机。它是 NFA 的一个特例对于任何一个状态和任何一个输入符号不包括 ε有且仅有一个确定的下一个状态。DFA 运行效率高但直接构造往往比 NFA 复杂。为什么我们要先构造 NFA 而不是直接构造 DFA因为Thompson 构造法的规则是模块化的、递归的它天然地、优雅地对应了正则表达式的递归语法结构。直接为复杂正则表达式构造 DFA 的算法子集构造法逻辑上更绕而 Thompson 法则像一套清晰的说明书告诉我们如何用标准零件组装出最终产品。通常的流程是正则表达式 -(Thompson构造法)- NFA -(子集构造法)- DFA -(最小化)- 最小 DFA这个最小 DFA 才是最终用于高效匹配的引擎核心。2.3 ε-转移看不见的捷径ε-转移是 NFA 的一个关键特性也是 Thompson 构造法的“粘合剂”。它允许自动机在不消耗任何输入字符的情况下从一个状态跳转到另一个状态。这有什么用呢连接组件把两个子 NFA 的首尾用 ε-转移连起来表示“先完成第一个紧接着开始第二个”。实现选择从一个分支点出发用两条 ε-转移分别指向两个选项的入口表示“可以走这条路也可以走那条路”。构造闭包用 ε-转移创建一个循环允许重复匹配同时提供一条“跳过”循环的路径匹配零次。ε-转移极大地简化了 NFA 的组合逻辑让构造过程变得像流程图设计一样直观。但它也带来了复杂性在匹配时机器可能同时处于多个状态这些状态通过 ε-转移连通这就是 NFA 的“非确定性”。3. Thompson 构造法递归组合的艺术现在进入正题。Thompson 构造法是一组递归规则它为每一种正则表达式的基本单元定义了一个标准的 NFA 模版并为复合表达式定义了组合这些模版的方法。我们约定每个基本的 NFA 模版都有且仅有一个开始状态和一个接受状态用双圈表示。组合时我们通过 ε-转移来连接这些模版并确保最终合成的 NFA 也只有一个开始状态和一个接受状态。3.1 基础原子单元的构造这是我们的乐高积木最基础的零件。1. 匹配空串 ε 的 NFA这个 NFA 只做一件事不消耗任何输入直接从开始状态走到接受状态。开始状态 --ε-- 接受状态它有两个状态中间一条 ε-转移。这看起来简单但在组合中用于表示“这里可以什么都不匹配”是连接操作中的重要环节。2. 匹配单个符号 a 的 NFA这个 NFA 匹配且仅匹配一个具体的字符a。开始状态 --a-- 接受状态它有两个状态中间一条标有a的转移边。这是所有匹配的基石。注意这里a可以是任何定义在字母表 Σ 中的字符。在实现中我们通常用一个通用的“符号”类型来表示它可能是一个具体的字符如a也可能是一个字符类如[0-9]。在基础的 Thompson 构造中我们通常先处理字面字符字符类可以视为一个特殊的“符号”其匹配逻辑在后续的 NFA 模拟或转换为 DFA 时处理。3.2 复合表达式的组合规则有了基础零件我们就可以用三种操作符把它们组装成更大的结构。1. 连接操作 NFA (RS)假设我们已经为正则表达式R构造了 NFAN(R)为S构造了N(S)。要构造RS的 NFAN(RS)方法如下将N(R)的接受状态和N(S)的开始状态用一条ε-转移连接起来。N(RS)的开始状态就是N(R)的开始状态。N(RS)的接受状态就是N(S)的接受状态。原N(R)的接受状态和N(S)的开始状态将变成内部状态不再具有“开始”或“接受”的属性。N(RS): [Start of N(R)] -- ... (NFA for R) ... -- [Accept of N(R)] --ε-- [Start of N(S)] -- ... (NFA for S) ... -- [Accept of N(S)]为什么用 ε-转移连接因为连接操作RS的语义是先完整匹配R紧接着匹配S。ε-转移完美地表达了“紧接着”这个时序关系且不消耗输入字符确保匹配完R后能立刻、无条件地进入S的匹配流程。2. 选择操作 NFA (R|S)构造R|S的 NFAN(R|S)创建一个全新的开始状态q_start和一个全新的接受状态q_accept。从q_start分别引出两条ε-转移一条指向N(R)的开始状态另一条指向N(S)的开始状态。这表示机器可以从起点自由选择进入R分支或S分支。从N(R)的接受状态和N(S)的接受状态分别引出一条ε-转移都指向共同的q_accept。这表示无论走哪条分支成功结束后都会到达同一个终点。N(R|S): --ε-- [Start of N(R)] -- ... -- [Accept of N(R)] --ε-- / \ q_start q_accept \ / --ε-- [Start of N(S)] -- ... -- [Accept of N(S)] --ε--设计考量引入新的q_start和q_accept是为了保持 NFA 的“单入口单出口”的规整性这使得递归组合可以无限进行下去。所有子 NFA 的接受状态都“归附”于新的接受状态逻辑清晰。3. 克林闭包 NFA (R)* 构造R*的 NFAN(R*)创建一个全新的开始状态q_start和一个全新的接受状态q_accept。注意q_start本身也是一个接受状态因为R*可以匹配零次即空串。从q_start引出一条ε-转移到N(R)的开始状态。这表示可以开始一次R的匹配。从N(R)的接受状态引出一条ε-转移指回N(R)的开始状态。这构成了一个循环实现了“多次”匹配。从N(R)的接受状态再引出一条ε-转移指向q_accept。这表示完成一次或多次匹配后可以结束。最后从q_start直接引出一条ε-转移到q_accept。这条路径允许自动机完全不经过N(R)就直接接受对应匹配零次的情况。N(R*): q_start (也是接受状态) | | ε v [Start of N(R)] -- ... -- [Accept of N(R)] ^ | \ | | ε (to q_accept) |_________ε_______________| | v q_accept闭包逻辑的体现这个结构巧妙地涵盖了所有情况1) 走直接到q_accept的 ε 路径零次2) 走N(R)一次然后到q_accept一次3) 走N(R)一次通过循环边回到开头再走N(R)... 最后到q_accept多次。q_start是接受状态这一点至关重要它确保了空串能被正确识别。3.3 一个完整的构造示例(a|b)c*让我们把规则用起来构造正则表达式(a|b)c*的 NFA。我们自底向上构造。构造原子 NFAN(a):q0 --a-- q1N(b):q2 --b-- q3N(c):q4 --c-- q5构造(a|b)创建新状态q6(开始) 和q7(接受)。q6 --ε-- q0q6 --ε-- q2q1 --ε-- q7q3 --ε-- q7现在N(a|b)的开始状态是q6接受状态是q7。构造c*创建新状态q8(开始/接受) 和q9(接受)。q8 --ε-- q4q5 --ε-- q4(循环)q5 --ε-- q9q8 --ε-- q9(零次路径)现在N(c*)的开始状态是q8接受状态是q9。构造(a|b)c*(连接操作)将N(a|b)的接受状态q7与N(c*)的开始状态q8用 ε-转移连接q7 --ε-- q8。整个 NFA 的开始状态是q6接受状态是q9。最终得到的 NFA 虽然状态不少但结构清晰完全反映了原始表达式的语义先匹配a或b然后匹配零个或多个c。4. 从理论到实践实现与模拟理解了构造原理我们可以尝试用代码来实现它并编写一个 NFA 模拟器来验证其正确性。这里我们用 Python 来演示核心思想因为它足够清晰。4.1 数据结构定义首先我们需要定义 NFA 和状态的数据结构。class State: 表示NFA中的一个状态 def __init__(self, is_acceptFalse): # 状态转移表key为转移条件字符或None代表εvalue为下一状态集合 self.transitions {} self.is_accept is_accept def add_transition(self, symbol, state): 添加一条转移边。symbol为None表示ε转移 if symbol not in self.transitions: self.transitions[symbol] set() self.transitions[symbol].add(state) class NFA: 表示一个完整的NFA def __init__(self, start_state, accept_state): self.start_state start_state self.accept_state accept_state staticmethod def from_epsilon(): 构造匹配空串ε的NFA start State() accept State(is_acceptTrue) start.add_transition(None, accept) # ε转移 return NFA(start, accept) staticmethod def from_symbol(symbol): 构造匹配单个符号的NFA start State() accept State(is_acceptTrue) start.add_transition(symbol, accept) return NFA(start, accept)4.2 组合操作的实现接下来实现 Thompson 构造法的三个组合操作。def concat(nfa1, nfa2): 连接操作nfa1 nfa2 # 将nfa1的接受状态到nfa2开始状态的ε转移 nfa1.accept_state.is_accept False # 它不再是接受状态 nfa1.accept_state.add_transition(None, nfa2.start_state) # 新的NFA以nfa1开始以nfa2结束 return NFA(nfa1.start_state, nfa2.accept_state) def union(nfa1, nfa2): 选择操作nfa1 | nfa2 start State() accept State(is_acceptTrue) # 原接受状态不再是接受状态 nfa1.accept_state.is_accept False nfa2.accept_state.is_accept False # 从新开始状态ε转移到两个子NFA的开始 start.add_transition(None, nfa1.start_state) start.add_transition(None, nfa2.start_state) # 从两个子NFA的接受状态ε转移到新接受状态 nfa1.accept_state.add_transition(None, accept) nfa2.accept_state.add_transition(None, accept) return NFA(start, accept) def kleene_star(nfa): 克林闭包操作nfa* start State(is_acceptTrue) # 新开始状态也是接受状态匹配零次 accept State(is_acceptTrue) # 原接受状态不再是接受状态 nfa.accept_state.is_accept False # 新开始状态可以ε转移到原NFA开始也可以直接ε转移到新接受状态 start.add_transition(None, nfa.start_state) start.add_transition(None, accept) # 原NFA接受状态可以ε转移回原开始状态循环也可以ε转移到新接受状态 nfa.accept_state.add_transition(None, nfa.start_state) nfa.accept_state.add_transition(None, accept) return NFA(start, accept)4.3 NFA 模拟器它如何运行构造出 NFA 后我们需要一个模拟器来执行它看看给定字符串是否被接受。模拟的核心是处理ε-闭包和非确定性。def epsilon_closure(states): 计算给定状态集合的ε-闭包。 即从这些状态出发只通过ε转移所能到达的所有状态的集合。 closure set(states) stack list(states) while stack: state stack.pop() # 遍历该状态的所有ε转移 for next_state in state.transitions.get(None, set()): if next_state not in closure: closure.add(next_state) stack.append(next_state) return closure def nfa_simulate(nfa, input_string): 模拟NFA运行判断输入字符串是否被接受 # 当前可能处于的状态集合初始为开始状态的ε-闭包 current_states epsilon_closure({nfa.start_state}) for char in input_string: next_states set() # 对于当前集合中的每一个状态 for state in current_states: # 查看该状态在输入字符char上的转移 if char in state.transitions: next_states.update(state.transitions[char]) # 计算新状态集合的ε-闭包 current_states epsilon_closure(next_states) # 如果当前没有可能的状态提前拒绝 if not current_states: return False # 读取完所有字符后检查当前状态集合中是否包含接受状态 return any(state.is_accept for state in current_states) # 使用示例构造 (a|b)c* 并测试 if __name__ __main__: # 构造原子NFA nfa_a NFA.from_symbol(a) nfa_b NFA.from_symbol(b) nfa_c NFA.from_symbol(c) # 构造 (a|b) nfa_a_or_b union(nfa_a, nfa_b) # 构造 c* nfa_c_star kleene_star(nfa_c) # 构造 (a|b)c* final_nfa concat(nfa_a_or_b, nfa_c_star) # 测试 test_cases [a, b, ac, bc, acc, bccc, , ab, ca] for test in test_cases: result nfa_simulate(final_nfa, test) print(f{test}: {result})运行这段代码你会看到a,b,ac,bc,acc,bccc返回True而,ab,ca返回False这与我们对(a|b)c*的语言定义完全一致。5. 深入解析特性、问题与优化Thompson 构造法优美而强大但它构造出的 NFA 也有一些鲜明的特点在实际应用中会带来一些需要考虑的问题。5.1 Thompson NFA 的特点状态数线性增长对于一个长度为 n 的正则表达式Thompson 构造法产生的 NFA 状态数最多为 O(n)。每个基本符号a, ε引入2个状态每个操作符|, *, 连接引入最多2个新状态。这保证了构造过程的高效性。ε-转移众多这是该方法的显著特征。ε-转移是组合模版的“胶水”但也导致了状态的“爆炸式”连接。在模拟运行时需要频繁计算 ε-闭包这会带来一定的开销。单接受状态每个子 NFA 和最终 NFA 都严格遵循单入口单出口的约定这使得递归组合非常规整。结构性清晰NFA 的结构与正则表达式的语法树几乎同构查看 NFA 就能反推出原始表达式的结构可读性强。5.2 性能考量与常见问题模拟开销直接模拟 Thompson NFA 最耗时的部分就是计算 ε-闭包。在每一步读入字符后都需要对新的状态集合求一次 ε-闭包。在最坏情况下这可能导致算法复杂度为 O(n * s^2)其中 n 是输入字符串长度s 是 NFA 状态数。虽然 s 是线性的但平方项在状态数多时仍不可忽视。递归实现陷阱在实现组合操作尤其是闭包时要特别注意状态对象的修改。我们的示例代码中concat和union操作都修改了原 NFA 接受状态的is_accept属性。这意味着一个 NFA 对象被用于构建更大的 NFA 后它本身就不再是一个独立的、有效的 NFA 了。这在某些设计场景下需要注意你可能需要深度拷贝状态来避免副作用。贪婪匹配与回溯Thompson 构造法本身只定义了自动机的结构不定义匹配策略。上述模拟器采用的方式是在每个输入字符处收集所有可能的下一状态集合即同时探索所有路径。这是一种“并行”模拟能找到匹配当且仅当存在一条接受路径。这与某些正则引擎如 Perl、Pythonre模块的回溯算法不同。回溯算法是深度优先搜索并且通常配合贪婪、惰性等量词模式。Thompson 方法本身是无关贪婪与否的它产生的是所有可能路径的蓝图。5.3 从 Thompson NFA 到高效 DFA正因为直接模拟 NFA 有开销实践中更常用的路线是Thompson 构造 - 子集构造法 - DFA。子集构造法该算法将 NFA 模拟过程中的“当前可能状态集合”这个概念直接变成 DFA 的一个状态。算法从 NFA 开始状态的 ε-闭包出发将其作为 DFA 的初始状态。然后对于这个 DFA 状态即一个 NFA 状态集合考虑每个输入字符 a计算先从这个集合中的每个 NFA 状态出发经过 a 转移能到达哪些状态然后再求这个结果的 ε-闭包。这个新的 NFA 状态集合就构成了 DFA 中的一个新状态和一条转移边。重复这个过程直到没有新的 DFA 状态产生。最小化 DFA子集构造法产生的 DFA 可能不是最简的。可以通过 Hopcroft 算法等进一步最小化合并等价状态得到状态数最少的 DFA。最终匹配这个最小 DFA 就是最终用于匹配的引擎。对于任何输入字符串DFA 都只有一条确定路径匹配速度是 O(n)且与正则表达式复杂度无关性能极高。编译原理课程中著名的lex词法分析器生成器其核心就是这套流程。实操心得在实现 Thompson 构造法时一个很好的测试方法是可视化。你可以将生成的 NFA 状态和转移边输出为DOT 语言格式然后用 Graphviz 工具生成图片。肉眼观察 NFA 的结构对比正则表达式的语法树能极大地帮助你调试构造逻辑是否正确。例如检查闭包操作是否正确地创建了循环和零次路径检查选择操作是否有两个分支等。6. 扩展与变体应对更复杂的正则语法基础的 Thompson 构造法只处理|,*, 连接和基本符号。现代正则表达式语法丰富得多如(一次或多次)、?(零次或一次)、[a-z](字符类)、.(任意字符) 等。这些都可以基于基础操作来定义和实现。R(一次或多次)可以定义为RR*。在构造时可以直接实现一个plus函数其逻辑类似于kleene_star但去掉从新开始状态直接到新接受状态的那条 ε-转移因为至少需要一次匹配。def plus(nfa): start State() accept State(is_acceptTrue) nfa.accept_state.is_accept False start.add_transition(None, nfa.start_state) nfa.accept_state.add_transition(None, nfa.start_state) # 循环 nfa.accept_state.add_transition(None, accept) return NFA(start, accept)R?(零次或一次)可以定义为R|ε。即一个选择操作一边是R一边是匹配空串的 NFA。def optional(nfa): nfa_epsilon NFA.from_epsilon() return union(nfa, nfa_epsilon)字符类[abc]这本质上是一个选择操作a|b|c。我们可以构造一个特殊的 NFA其开始状态在输入字符为 a、b 或 c 时都能转移到接受状态。在实现上可以不为每个字符创建独立路径再合并而是优化为开始状态到接受状态有多条不同标签的转移边。staticmethod def from_char_class(chars): 构造匹配字符类中任意一个字符的NFA start State() accept State(is_acceptTrue) for ch in chars: start.add_transition(ch, accept) return NFA(start, accept)任意字符.这可以看作一个匹配“任何”字符的 NFA。在模拟时需要对输入字符进行通配检查。在转换为 DFA 时需要特殊处理这个转移。处理括号与优先级真正的正则表达式解析器需要处理操作符优先级通常闭包*?最高然后是连接最后是选择|和括号()来改变优先级。这需要一个语法分析步骤将输入的正则表达式字符串转换成一棵抽象语法树。Thompson 构造法则作为语义分析的一部分递归地遍历这棵 AST为每个节点调用对应的构造函数。注意事项当你开始支持括号和优先级时构造过程就变成了对 AST 的后序遍历或递归下降。确保你的语法分析器能正确生成 AST。一个常见的错误是忽略连接的隐式操作符。例如ab*c的 AST 应该是连接(a, 连接(闭包(b),c))而不是连接(a, 闭包(b),c)。连接是左结合的。