企业官网建设流程全解析

正则表达式这东西，搞编程的几乎天天用。搜个关键词用grep -E，写后端逻辑用re.match，前端做校验也离不开它。但你有没有想过，你写下的那一串字符——比如a(b|c)*——在计算机内部是怎么变成一个能真正匹配字符串的机器的？我早年研究编译原理的时候，卡在正则引擎的实现上卡了挺久。后来把 Thompson 算法啃下来才明白，正则表达式到 NFA（非确定有限自动机）这一步，正是所有事情的核心。

这篇内容我准备彻底讲透 Thompson 算法。用最通俗的语言，配合一个完整的手工构建示例，带你从零把一串正则变成一张 NFA 状态图。同时我会给出可运行的 Python 代码骨架、边界情况排查经验，以及它和我们日常用到的回溯型正则引擎之间的底层差异。不管你是补基础的在校学生，还是想给自研框架写个匹配器的工程师，这篇都应该能帮到你。

1. 为什么非要“正则转NFA”这一步

1.1 正则表达式和有限自动机，其实是同一件事的两种说法

我从接触编译原理第一天起，就被老师反复强调一句话：正则表达式描述的是“正则语言”，而正则语言恰好就是有限自动机能识别的语言。这句话在当时听来像绕口令，但它的意义非常深远。正则表达式是人类友好、书写方便的语法糖，但计算机真正擅长执行的，是一张状态图：从一个状态出发，读入字符，跳到下一个状态，最终落在接受状态就说明匹配成功。

Thompson 算法干的事情，就是把这层“语法糖”剥掉，露出底层的图结构。它由 Ken Thompson 在 1968 年提出，和 Unix 上早期的grep工具紧密相关。理解它的一个关键点是：Thompson 算法构建出来的不是一般的 NFA，而是带ε（epsilon）转移的 ε-NFA。ε 转移表示不消耗任何输入字符就能从一个状态跳去另一个状态，它就像状态图里的“免费传送门”。利用这些 ε 边，我们才能把复杂表达式拆解成小模块再拼起来。

如果你觉得这个概念还是有点抽象，可以这样类比：正则表达式好比是乐高玩具的说明书——描述你要搭的最终造型；而 Thompson 算法是里面的拼装步骤，把一个个“基础积木”（单个字符状态的自动机）按规则拼成最终成品。这样一想，整个流程就没有那么玄乎了。

1.2 非确定性和ε转移，凭什么能简化构建

初学者最容易问的一句话是：为什么要搞出非确定性和 ε 转移这种看起来“麻烦”的东西？直接生成 DFA（确定有限自动机）不是更省事吗？现实是，直接从正则构造 DFA 非常反直觉，因为你要考虑“当前状态 + 下一字符 → 唯一状态”这个严格的确定性约束。构造过程牵涉很多前瞻和合并操作，代码写起来又长又容易错。

Thompson 算法的聪明之处在于“先构建，后确定化”。它先把正则表达式拆成五种基本操作：单字符匹配、连接、并、零次或多次（星号）、以及一次或多次（加号），后两者本质通过 ε 闭包实现。每一步构建都是局部操作，不需要全局视野，因此实现起来非常机械、可靠。

有了 ε 转移之后，并操作和闭包操作都变得异常简洁：并操作就是新增一个起始状态，用 ε 边分别通向两个子表达式的自动机；闭包操作只需要加一组 ε 边，让状态能循环回去再跑出去，就能表达“零次也行、多次也行”。正是这种“图状拼接”的思路，让 Thompson 算法在工程中成为了构建正则引擎的基石。

2. 核心原理拆解：Thompson算法到底做了什么

2.1 五种基本构造的NFA片段

Thompson 算法的一切，都建立在五种基本构造之上。只要把这五种构造的“图纸”刻在脑子里，后面再做复杂表达式就是重复套用。下面我用状态图的方式逐一说明：

单个字符a：创建一个起始状态和接受状态，用标有a的边连接。

连接ab：把a的接受状态和b的起始状态合并。更准确地说，a的接受状态变成非接受状态，通过 ε 边连接到b的起始状态。这里的关键是“拼接”而不是重新构造，保证了整体结构是线性增长的。

并操作a|b：新增一个起始状态，用 ε 边分别连接到a和b的起始状态；再新增一个接受状态，a和b的接受状态分别用 ε 边连接到这个新的接受状态。

零次或多次a*：新增起始和接受状态，从新的起始状态用 ε 边连到a的起始状态，同时新增一条 ε 边直接连到新的接受状态（表示可以跳过）；a的接受状态用 ε 边回到a的起始状态（表示可以循环），也用 ε 边连到新的接受状态（表示可以退出）。

一次或多次a+：本质上就是a a*，或者说是a*去掉“跳过”路径，保证至少经过一次。直接实现时可以复用闭包的构造，去掉到接受状态的直接 ε 边即可。

这些构造还有一个共同优点：每个子表达式生成的 NFA 恰好有一个起始状态和一个接受状态。这个“单入口、单出口”性质保证了递归拼接的可行性和简单性。

2.2 运算符优先级与递归下降解析

光有五种拼装图纸还不够，你必须知道什么时候该用哪种拼法。这就是语法分析要解决的优先级问题。正则表达式的优先级从高到低依次是：括号 > 闭包（*+?）> 连接 > 并（|）。

既然优先级有差异，我们就应该在解析时体现出来。我常用的是递归下降解析器，核心逻辑分三层：parse_union处理并操作，parse_concat处理连接，parse_repeat处理闭包和单字符。括号则在parse_atom里递归调用parse_union来处理。这样既简洁又不容易出错。

在实际代码中，我会先对输入做一次预处理：把所有显式连接符（.或·）插入到表达式里。比如ab变成a.b，(a|b)*c变成(a|b)*.c。这一步看似不起眼，却能极大简化解析器的逻辑——你不需要在解析时去判断“上一个 token 和当前 token 是否隐含连接”，而是把连接当作和并、闭包同级的显式运算符来处理。我的个人习惯是用字符.作为内部连接符，因为它的优先级介于|和*之间，处理起来刚刚好。

2.3 为什么NFA片段数量是线性的

Thompson 算法在工程上还有一个极其重要的性质：最终生成的 NFA 状态数和边数，与正则表达式的长度呈线性关系。这个性质直接保证了“把任意复杂的正则转成 NFA”这一步不会带来性能灾难。我们来看一下每种构造的状态增量：

• 单字符：新增 2 个状态，1 条转移边
• 并操作：新增 2 个状态，外加 4 条 ε 边
• 连接：不新增状态，只加 1 条 ε 边
• 闭包：新增 2 个状态，外加 4 条 ε 边

无论怎么组合，状态总数始终是2 * 操作数的量级，边数同样可控。这个线性增长在工程中非常宝贵。等到后续做 NFA 转 DFA 时，DFA 的状态数在最坏情况下会指数爆炸，但那是另一个问题——至少从 NFA 生成这一步开始，计算代价就已经被严格限制住了。

3. 手工实战：构建a(b|c)*的完整NFA

3.1 从表达式到解析树

要真正理解一个算法，只看伪代码是远远不够的。我带大家手工走一遍完整的实战，目标是把正则表达式a(b|c)*转成 NFA。第一步，我们先把表达式按优先级解析成一棵语法树：

• 根节点：连接操作.
• 左子树：字符a
• 右子树：闭包操作*
  • 子节点：并操作|
    • 左子树：字符b
    • -右子树：字符c

这棵树的构建过程直观地反映了优先级规则：括号优先级最高，所以(b|c)被作为一个整体解析，然后*作用在这个整体上，最后才与a做连接。

3.2 按顺序拼接NFA片段

现在我们按自底向上的顺序构建 NFA 片段。

第1步：构建字符b的自动机。它有两个状态，从状态1到状态2有一条标记为b的边。同理，字符c的自动机由状态3到状态4的一条c边构成。

第2步：构建b|c的并操作。新增状态5作为起始，新增状态6作为接受。ε 边从5分别连向1和3；ε 边从2和4分别连向6。

第3步：对b|c的自动机应用闭包*。新增状态7和状态8。ε边从7连到5，表示“进入并结构”；从5连到8需要经过原来的接受状态6再 ε 连到8；同时从8引一条 ε 边回到7，实现循环。

这里容易写乱的一点是闭包之后的状态连接关系。我在实际手工推导时，习惯把新加的“入口状态”放在最左边，“出口状态”放在最右边，循环边永远是从旧的接受状态回到旧的起始状态。这样的排布能让图画出来非常清晰。

第4步：连接字符a。构建a的自动机，状态9到状态10有一条a边。然后把状态10通过 ε 边连到第3步生成的起始状态7。

至此，完整的 NFA 就构建完成了。你可以顺着它走一遍：从状态9读到a，跳到状态10，ε 到7，进入循环体（可能执行零次、一次、多次的b或c匹配），最后落到接受状态8。

3.3 核心原则：单入口与单出口

手工推导过程中，我反复确认的一个原则就是：每个子结构都保持单入口和单出口。这在 Thompson 算法实现里尤其重要。比如闭包构造时，新增的入口状态 7 和出口状态 8 一旦确定，就不能让其他边直接穿入或穿出这个闭合区间；并操作时，新的入口 5 和出口 6 也必须严格隔离两个子分支。

这样做的原因很简单：任何不遵守单入口、单出口规则的拼接，都会让后续的“连接”操作变得极其复杂——你不知道应该把上一个结构的哪个状态当作“尾部”，也不知道应该把下一个结构的哪个状态当作“头部”。坚持这一原则，你的 NFA 构建代码就会像流水线一样顺畅。

4. 代码实现：一个简化的Thompson引擎

4.1 数据结构设计

聊完了理论，我们看具体怎么实现。我要写的这个引擎用 Python 实现，但思路完全适用于任何语言。数据结构不需要多复杂，关键在于清楚的转移表达方式。首先定义状态和转移边：

class State: def __init__(self, is_end=False): self.is_end = is_end self.transitions = [] # 每条边是一个 (字符或None, 目标状态) class Fragment: def __init__(self, start, ends): self.start = start self.ends = ends # 目前所有“悬空”的结束状态

这里我把状态设计为一个通用的节点，transitions里存储两种转移：普通字符转移和 ε 转移（用None标记）。Fragment则代表一个已完成构建的子自动机，它有明确的出口集合。为什么要用“出口集合”而不是“唯一出口”？因为在某些中间阶段可能存在多个悬空出口，需要把它们统一连接起来。

4.2 核心构造函数

五个核心构造函数的代码可以这样写：

def char_fragment(c): start = State() end = State(is_end=True) start.transitions.append((c, end)) return Fragment(start, [end]) def concat_fragment(f1, f2): for end in f1.ends: end.is_end = False end.transitions.append((None, f2.start)) return Fragment(f1.start, f2.ends) def union_fragment(f1, f2): start = State() end = State(is_end=True) start.transitions.append((None, f1.start)) start.transitions.append((None, f2.start)) for end_state in f1.ends + f2.ends: end_state.is_end = False end_state.transitions.append((None, end)) return Fragment(start, [end]) def star_fragment(f): start = State() end = State(is_end=True) start.transitions.append((None, f.start)) start.transitions.append((None, end)) for end_state in f.ends: end_state.transitions.append((None, f.start)) end_state.transitions.append((None, end)) end_state.is_end = False return Fragment(start, [end])

这里有个细节值得说：连接操作时，f1的结束状态要取消is_end标记，而f2的结束状态保持标记；并操作时，两个子结构的结束状态都取消标记，统一汇聚到新状态；闭包则要新增双向 ε 回路。每一步都必须仔细处理is_end的归属，否则最终的匹配判断会出现错误。

4.3 解析器与构建主流程

有了构造函数，还需要一个把正则字符串解析成Fragment的驱动器。我用一个简单的递归下降解析器，维护一个“当前位置”指针：

class RegexParser: def __init__(self, pattern): self.pattern = pattern self.pos = 0 def parse_union(self): fragment = self.parse_concat() while self.pos < len(self.pattern) and self.pattern[self.pos] == '|': self.pos += 1 right = self.parse_concat() fragment = union_fragment(fragment, right) return fragment def parse_concat(self): fragment = self.parse_repeat() while self.pos < len(self.pattern) and self.pattern[self.pos] not in '|)': right = self.parse_repeat() fragment = concat_fragment(fragment, right) return fragment def parse_repeat(self): fragment = self.parse_atom() while self.pos < len(self.pattern) and self.pattern[self.pos] in '*+?': op = self.pattern[self.pos] if op == '*': fragment = star_fragment(fragment) elif op == '+': # a+ 可以视为 aa* inner = fragment fragment = concat_fragment(inner, star_fragment(inner)) elif op == '?': # a? 可视为 a|ε epsilon = empty_fragment() fragment = union_fragment(fragment, epsilon) self.pos += 1 return fragment def parse_atom(self): ch = self.pattern[self.pos] if ch == '(': self.pos += 1 frag = self.parse_union() if self.pattern[self.pos] == ')': self.pos += 1 return frag self.pos += 1 return char_fragment(ch)

这段代码已经可以处理|、*、+、?以及括号。+的处理方式我特意用inner复制了一下，避免同一个 Fragment 被多次用于拼接导致共享状态污染。这一点是实际编码时踩坑最多的位置——状态对象是引用类型，直接复用会造成环状错误连接。

5. 从NFA到匹配：闭包与模拟执行

5.1 为什么不能直接“走”NFA

构建出来的 NFA 是个带 ε 边的图，我们没法像走数组那样从起始状态一个字符一个字符地走到目标。“非确定性”意味着在同一时刻可能存在多个可能的当前状态。比如匹配a(b|c)*时，在读完a之后，自动机可能同时处于“等待循环体入口”和“已经完成循环体、准备结束”的状态。

所以实际匹配时，我们需要一种能同时跟踪多个状态的算法。核心思路是维护一个“当前状态集合”，每次读入一个字符时，对集合里每个状态执行两步操作：先计算它们的 ε 闭包，再沿着匹配字符的边移动到新状态。

5.2 ε闭包与单字符推进

ε闭包算法的定义很简单：从当前状态出发，沿着所有 ε 边（以及 ε 边的 ε 边）能到达的状态，全部加入集合。实现时可以写个广度优先遍历：

def epsilon_closure(states): stack = list(states) closure = set(states) while stack: state = stack.pop() for ch, target in state.transitions: if ch is None and target not in closure: closure.add(target) stack.append(target) return closure def move(states, ch): next_states = set() for state in states: for edge_ch, target in state.transitions: if edge_ch == ch: next_states.add(target) return next_states def match(pattern, text): parser = RegexParser(pattern) nfa = parser.parse_union() current_states = epsilon_closure({nfa.start}) for ch in text: current_states = epsilon_closure(move(current_states, ch)) if not current_states: return False return any(state.is_end for state in current_states)

这种匹配方式的时间复杂度是O(len(text) * N)，其中N是 NFA 的状态数。正因为 Thompson NFA 的状态数是线性增长的，整体匹配效率在工程上是完全可以接受的——它正是许多现代正则引擎采用的思路。

但这里我特别提醒一句：上面的代码只是一个教学用原型，实际生产级的正则引擎需要考虑更多边界，比如贪婪匹配、反向引用、零宽断言等。那些特性已经超出正则语言本身的范畴，属于“正则表达式方言”的扩展。如果你只是要一个严谨的“纯粹正则引擎”，Thompson 算法 + ε闭包模拟已经能覆盖所有需求。

6. 工具验证与调试技巧

6.1 手工绘制NFA图

虽然纯手推 NFA 能加深理解，但遇到复杂正则时，肉眼检查状态图还是要命地痛苦。我的经验是把 NFA 结构导出成 Graphviz 的 DOT 格式，用图形化的方式直观检查。比如写上：

digraph NFA { rankdir=LR; node [shape=circle]; 7 [shape=doublecircle]; 0 -> 1 [label="a"]; 1 -> 2 [label="ε"]; 2 -> 3 [label="ε"]; 3 -> 4 [label="b"]; 3 -> 5 [label="ε"]; ... }

一导出你就能立刻看到，哪条 ε 边连错了、哪个状态忘了标记接受态。

6.2 单元测试的黄金用例

我构建完 NFA 之后，一般会跑一组覆盖各种结构的测试用例：空表达式、单字符、连接、并、闭包、嵌套括号、多次闭包。尤其建议测一下a*匹配空字符串的场景，这是最容易暴露 ε闭包 bug 的经典用例。另外，(|a)这种“空分支”的并集也值得优先测试，因为它混入了 ε 与普通字符的组合。

我自己的测试清单大致如下：

这组用例能覆盖绝大多数边界情况。如果你测完这些全部通过，你的 Thompson 实现基本就稳了。

7. 从Thompson到DFA：下一步往哪走

7.1 为什么还需要子集构造算法

既然 NFA 加 ε闭包已经能完成匹配，为什么还要费劲转成 DFA？核心原因是性能。NFA 模拟运行时，每一步都要维护一个状态集合，做 ε闭包计算；而 DFA 每个状态下每个字符最多只有一条转移边，匹配复杂度严格等于文本长度，且没有任何集合操作的开销。

代价自然是 DFA 的状态数可能远大于 NFA。但好消息是，通过子集构造算法（Subset Construction），我们可以把 NFA 的状态集合作为 DFA 的“状态”——这套思路非常优雅：NFA 的若干状态集合被映射成 DFA 的单一状态。很多工具库就是这么做的，比如正则表达式相关的re2就基于 NFA 模拟和非回溯策略，而经典的lex工具则直接生成 DFA 表。

7.2 子集构造的关键步骤

子集构造的流程大概是这样：

1. 从 NFA 的起始状态出发，计算它的 ε闭包，把它作为 DFA 的初始状态。
2. 对当前 DFA 状态（即 NFA 状态集合），针对每个输入字符计算move和 ε闭包。
3. 如果得到的新状态集合从未出现过，就加入 DFA 状态集合，继续处理。
4. 如果某个 DFA 状态集合里包含任一 NFA 接受状态，则该 DFA 状态为接受状态。

整个过程本质上是对 NFA 的“惰性求值”。在工程实现上，可以配合一个哈希表记录状态集合到新状态的映射，避免重复计算。这里还要注意：DFA 的某个状态集合如果同时包含“接受路径”和“非接受路径”，它在匹配的语义上仍然算接受——因为只要存在一条路径到达接受状态，字符串就是匹配的。

7.3 最小化DFA与真正的日常选择

DFA 生成之后，还可以再做一步最小化，合并等价状态，让状态表更紧凑。经典的 Hopcroft 算法或 Moore 算法都可以做这件事。不过坦白说，如果只是做教学项目或轻量级匹配器，NFA 模拟已经足够，DFA 优化往往要等到你处理超大文本或者追求极致的匹配速度时才真正值得投入。

在日常工程里，你写python的re模块时，用的是基于回溯的引擎，它能支持\1反向引用这类超纲特性；你写 Go 的regexp包时，底层则完全是 Thompson NFA 的思路，无论在什么输入上都能保证线性时间。理解 Thompson 算法之后，你再去体会这两种引擎的取舍，会有一种知识终于串起来的通透感。

8. 常见问题与排查经验

8.1 闭包后无法匹配空串

症状：a*匹配""返回False。原因：状态start到end的直接 ε 边没有正确添加，或者end.is_end没设为True。排查：打印起始状态的 ε闭包，确认里面是否包含接受状态。

8.2 连接操作把状态搞乱

症状：ab能匹配a，或者能匹配b，但不能匹配ab。原因：多半是连接时没有清除左边结构的is_end标记，导致在左边结构结束时就提前判定成功。排查：检查concat_fragment里是否写了end.is_end = False。这一个疏漏是新手最高频的 bug。

8.3 并操作中的分支串扰

症状：a|b匹配ac时返回True。原因：并操作的两个分支可能共享了不该共享的状态，通常是因为你复用了同一个Fragment实例。比如在处理a|a时，如果直接把同一个fragment对象传入union_fragment，它的结束状态会被连接两次，产生意外的路径。解决：保证传入并操作的每个Fragment都是“可独立使用”的新实例，必要时做深拷贝或用工厂函数生成新状态。

8.4 加号被当成普通字符

症状：a+匹配a返回False，却匹配了+字符。原因：解析parse_repeat时，没有在+分支处移动pos，导致循环条件把+当成普通字符处理。排查：检查每个运算符处理的self.pos递增位置，以及parse_atom中是否对运算符字符做了过滤。

8.5 优先级错误导致灾难

症状：ab|c被解析成a(b|c)。原因：解析时没按“并优先级最低”处理，把parse_union和parse_concat的顺序搞反了。排查：按照“parse_union 最高层，内部调用 parse_concat；parse_concat 内部调用 parse_repeat；parse_atom 处理单字符和括号”的层级来实现，一般就不会错。

9. 我积累的一点实操心得

在反复手推和调试 NFA 的这几年，我有几个习惯一直保留到今天。第一，每个复杂正则开始前，我习惯先用括号把隐式结构写全。比如ab|c我会先写成(ab)|c再动手推导，这能避免九成优先级错误。第二，状态编号保持规律：每次新增片段时，入口编号小于出口编号，闭包结构编号连续，图形化导出时一目了然。第三，尽量让每个子结构的构建代码独立成函数，方便单测和复用。

真正上手完成一个“正则到 NFA”的小工程，你对正则表达式的理解会有一个质的飞跃。以前你只会“用它”，现在你知道它底层是一张什么样的图。以后看到回溯、看到灾难性回溯的新闻，你也能从自动机的角度理解，为什么某些匹配在传统回溯引擎里会慢到怀疑人生——因为那些引擎根本没有走 Thompson 的线性路径，而是走了指数级的回溯搜索。

建议你动手把这套代码写完，跑一遍我上面给出的测试用例，再试着给代码加上^和$锚点的支持。等你做到这一步，再去搜“NFA 转 DFA”的资料，衔接感会自然很多。到那时候，编译原理里最难啃的自动机部分，也会变成你的舒适区。