如果你也在做编译原理实验里的词法分析，多半会被要求实现一个“从正则表达式到自动机”的构造器，而课堂和教材里最常出现的名字就是Thompson构造法。这个实验看起来只是把一个正则转成NFA，但它其实是整个词法分析器自动生成链路的地基：先用正则描述单词，再用Thompson构造法生成NFA，之后才能谈得上子集构造、DFA最小化、表驱动识别这些后续步骤。
这篇东西适合两类人看：一类是正在写编译原理实验、对着作业要求不知道从哪下手的学生；另一类是工作后想回头把正则引擎原理补扎实的开发者。我不打算复述教材上的抽象定义，而是把构造法的五条规则、数据结构设计、完整代码实现、以及我在实验里踩过的三个坑一次性讲清楚。尤其那个“三个坑”的部分，网上教材基本不会写，但你在调试时一定会撞上。
1. 实验意图拆解：词法分析器为什么绕不开Thompson
先弄清楚这个实验到底在做什么。词法分析的核心任务是把源代码的字符流切成一个个token，比如标识符、关键字、整数字面量、运算符、分隔符。几乎所有教材都会告诉你，描述token最方便的工具是正则表达式，例如标识符就是[a-zA-Z_][a-zA-Z0-9_]*，无符号整数就是[0-9]+。
问题来了：代码本身不认正则，它只认状态和转移。所以你需要一个算法，把正则表达式翻译成等价的状态机。这就是Thompson构造法登场的时机。
可能有同学会说：“那我直接手写一个状态机不就行了？”对于小实验确实可以，比如识别一个if关键字，写几个状态就够了。但等你把运算符、分隔符、数字、标识符全部塞进去，手写状态机会变成一个巨大的switch-case地狱，加一个token类型就要重画一遍状态图，很痛苦。而Thompson构造法的思路完全不同：它先把正则表达式拆成最基本的组成单元，再用统一的拼接规则把它们组合起来，整个过程像搭积木一样，加规则只是再加一块积木的事。
围绕这个实验任务，完整的自动化词法分析流水线长这样：
正则表达式 → Thompson构造NFA → 子集构造法转DFA → DFA最小化 → 表驱动词法分析器
如果你这门课的实验只要求做到NFA为止，也没关系。NFA本身理论上就能直接用来识别单词，只是需要做ε闭包运算，性能不如DFA，但作为验证构造正确性的手段完全够用。
下面的表格是一个典型的实验需求，你会发现每个token类型都能对应一个正则表达式：
| token类型 | 正则表达式 | 说明 |
|---|---|---|
| 标识符 | [a-zA-Z_][a-zA-Z0-9_]* | 首个字符不能是数字 |
| 关键字 | if/else/while等 | 本质是特殊的标识符 |
| 整数字面量 | [0-9]+ | 无符号整数 |
| 浮点字面量 | [0-9]+\.[0-9]+ | 简化版，不包括科学计数法 |
| 运算符 | + - * / == != <= >=等 | 每个运算符一个正则 |
| 分隔符 | ; ( ) { }等 | 单字符token |
每个正则用Thompson构造法转换成一个NFA，然后把所有NFA合并成一个大的NFA，最后给每个接受状态绑定一个token编号。识别时从开始状态出发，对输入字符执行状态转移，到达哪个接受状态就返回哪个token编号。这就是lex系词法分析器生成器的核心思路。
所以做这个实验，不要把它当成一次性的作业代码，它的每一部分都是后面DFA实验的铺垫。我自己的经验是，把Thompson构造法写扎实，后面做子集构造法会省一半力气，因为你已经有了一个能输出NFA的可靠基础设施。
2. Thompson构造法的五条规则与组合原理
Thompson构造法对任何正则表达式都只做五件事：字符、空串、并、连接、闭包。这五个操作对应一个NFA的五个构造模式，每个模式都保证输入一个或多个子NFA后，输出一个新的NFA，并且新NFA始终保留一个“标准接口”：一个起始状态、一到多个接受状态。保持接口不变这一点非常重要，因为它允许你无限递归地组合更大的表达式。
2.1 基础规则：单字符和空串
最基本的单元是单字符正则，比如a。它的NFA构造极其简单：一个起始状态，一个接受状态，起始状态有一条标号为a的边指向接受状态。
start(S) --a--> A这里A是接受状态。如果是空串正则ε，那就是一个起始状态直接等于接受状态，没有边。这个基础规则没啥好说的，但它是整个构造法的地基。
2.2 组合规则：并、连接、闭包
有了单字符的NFA，就能往上拼了。
并运算a|b的思路是：新建一个起始状态S，从S分别用ε边连到子表达式a的起始状态和b的起始状态；再把a和b各自的接受状态用ε边接到同一个新的接受状态F上。这样一来，从S出发要么走a分支、要么走b分支，最后都汇入F。
S -ε-> Na.start ... Na.accept -ε-> F S -ε-> Nb.start ... Nb.accept -ε-> F因为用了ε边，两个分支互不干扰，逻辑非常干净。
连接运算ab更简单：把a的接受状态用ε边连到b的起始状态，然后整体作为新NFA。新NFA的起始状态就是a的起始状态，接受状态就是b的接受状态。注意原来a的接受状态现在不再被当作整体接受状态，它只是中间状态。
闭包运算a*稍微绕一点：新建起始状态S和接受状态F，从S用ε边分别连到a的起始状态和F；然后把a的接受状态用ε边分别连回a的起始状态和F。这样做的效果是：可以直接跳过a走S到F，也可以走a一次后通过“a的接受状态→a的起始状态”的环反复多次，最后从a的接受状态走到F结束。
S -ε-> Na.start S -ε-> F Na.accept -ε-> Na.start Na.accept -ε-> F闭包这个模式经常有人写错，把“回到a起始状态”和“跳到F”两条ε边漏掉一条。漏了跳到F那一条，a*就退化成了a+；漏了回到起始那一条，a*最多只能匹配一次a。后面的踩坑环节我会详细说。
2.3 为什么接受状态必须用“集合”而不是“单个状态”
你可能注意到了，我说“接受状态”一直是复数。这是Thompson构造法实现里很容易被忽略的细节。很多教材为了讲解方便，把每个NFA画成一个起始状态和一个接受状态，但那只适用于基础字符的情况。
并运算和闭包运算会把多个子NFA的接受状态汇聚到新状态上，可如果被合并的接受状态后续还要参与其他运算呢？比如(a|b)*c，构造完a|b后，它的接受状态要被闭包运算连出去，而闭包运算要求我们知道“这个片段的所有当前接受状态是哪些”，才能给它们加边。单个状态根本不够用，必须保存一个接受状态集合。
所以实现时，我通常定义一个Fragment对象，包含两个字段：起始状态start，接受状态集合accept_set。每构造完一个表达式片段，就得到一个Fragment；组合运算的输入是若干Fragment，输出是一个新Fragment。这个设计贯穿下面所有代码。
把五个规则表列出来方便对照：
| 运算 | 输入 | 构造动作 | 输出Fragment |
|---|---|---|---|
字符a | 无 | 新建S、F，S标a边连F | start=S, accept={F} |
| 空串ε | 无 | 新建一个状态S，直接作为接受状态 | start=S, accept={S} |
并\ | ` | 两个Fragments | 新建S、F，S ε连两起始，两接受ε连F |
连接ab | 两个Fragments | 左接受ε连右起始 | start=左start, accept=右accept |
闭包a* | 一个Fragment | 新建S、F，S ε连起始和F，接受ε连回起始和F | start=S, accept={F} |
其中连接运算输出Fragment的accept_set是右子片段的accept_set，这是一个容易踩的细节：连接完成后，左片段的接受状态已经变成普通中间状态了，不能再继续充当整体接受状态。如果你在程序里把左右accept_set合并了，后面闭包运算就会给错误的状态加边，最后画出来的NFA多出一堆不存在的接受路径。
3. 数据结构设计：NFA怎么存、状态号怎么管
动手写代码之前，先把数据结构定下来。这一步很关键，直接决定你后面调试的难易程度。
我推荐用一个邻接表结构表示NFA。每个状态是一个对象，保存自己的编号、出边列表，以及是否为接受状态的标记。每条边是一个二元组：转移字符加目标状态。字符用一个特殊值表示ε转移。
EPSILON = None class NFAState: def __init__(self, sid): self.id = sid self.edges = [] # (symbol, target_state) self.is_accept = False为什么不直接用邻接矩阵？因为NFA的状态边通常很稀疏，而且ε边和字符边混在一起，用邻接表遍历起来最自然。模拟NFA时要频繁做“从一组状态出发，按某个字符找下一组状态”的操作，邻接表正好匹配。
再定义一个Fragment类：
class Fragment: def __init__(self, start, accept_set): self.start = start self.accept_set = accept_set状态编号管理是另一个重点。我建议用一个全局自增计数器，每创建新状态就分配一个编号，绝对不要手动指定，否则很容易重复。具体到代码里，我会在构造函数内部维护一个计数器：
def build_nfa(postfix_expr): stack = [] state_counter = 0 def new_state(): nonlocal state_counter s = NFAState(state_counter) state_counter += 1 return s这个计数器的作用范围是一次正则表达式的构造。如果你后面要把多个正则合并成一个总NFA来做完整的词法分析，就要格外小心：每个子NFA构造完时的状态编号是独立的，合并时要么重新编号，要么用一个所有子NFA共享的计数器。我在第5章的第三个坑里会讲共享计数器用错是什么后果。
还有一个我在实际调试中特别受益的设计：给状态加一个label字段，用来说明这个状态是由哪个正则片段产生的。比如闭包运算创建的新状态标上*_start、*_accept，连接运算的中间状态标上&_bridge。NFA规模大了以后，打印调试日志时没有标签的状态编号几乎无法辨认。
我记得第一次做这个实验时，没有label字段，构造(a|b)*c这种稍微复杂一点的正则，打印出30多个状态编号，完全看不出哪里对应哪里。后来加上标签，配合可视化渲染，一秒定位问题。
另一个实用建议：调试时一定把“状态编号+出边信息+是否接受”三件套打印完整。我见过很多同学的调试代码只print状态编号，边信息靠猜，这纯粹是给自己找麻烦。打印格式大概长这样：
state 0 label='a_start' edges=[('a', 1)] accept=False state 1 label='a_accept' edges=[] accept=True看见这个输出，构造逻辑对不对一目了然。
4. 代码实现：从正则字符串到可运行的NFA
数据结构定好了，接下来是完整实现。我实验里采用的方案分成两个阶段：先把中缀正则表达式转换成后缀形式，再通过后缀表达式逐个应用Thompson规则。这样做的好处是，正则的运算符优先级问题交给第一阶段处理，第二阶段只用盯着一串线性规则做栈操作，出错了也容易定位。
4.1 第一阶段：中缀转后缀
正则表达式的运算符优先级和算术表达式类似：闭包运算优先级最高，连接运算次之，并运算优先级最低，括号改变优先级。要把中缀转成后缀，需要两个处理：第一，显式补出连接运算符&；第二，用调度场算法把运算符排序。
补连接符这一步很多人忽略。正则里的连接是隐式的，ab表示a和b连接，但程序需要显式的&才能在后续用后缀算法处理。我给一个能用的版本：
def insert_concat(expr): out = [] n = len(expr) for i, c in enumerate(expr): out.append(c) if i + 1 < n: nxt = expr[i + 1] if (c not in '(|') and (nxt not in '|)*'): out.append('&') return ''.join(out)这里的逻辑是：当前字符不是左括号或并运算符，同时下一个字符不是右括号、并运算符或闭包运算符时，说明这两个字符之间存在一个隐式连接，补一个&。
动机：闭包运算符*是后缀运算符，它只作用于前一个表达式片段。a*中间不需要补连接符；但a*b在*和b之间需要补，因为a*结束后要和b连接。
然后是中缀转后缀：
ALPHABET = 'abcdefghijklmnopqrstuvwxyz0123456789' def to_postfix(expr): expr = insert_concat(expr) output = [] ops = [] prec = {'|': 1, '&': 2} for c in expr: if c in ALPHABET: output.append(c) elif c == '*': output.append(c) elif c == '(': ops.append(c) elif c == ')': while ops and ops[-1] != '(': output.append(ops.pop()) ops.pop() else: while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[c]: output.append(ops.pop()) ops.append(c) while ops: output.append(ops.pop()) return ''.join(output)注意这里*是直接输出到结果串里的，因为它是后缀运算符，放在它操作的操作数后面正好。如果你在实验里还支持+、?这类后缀运算符，同样的做法：遇到它们直接追加到output。
4.2 第二阶段：逐个应用Thompson规则
拿到后缀表达式后，用栈维护已经构造好的Fragment，遍历每个符号：
- 遇到字符：创建一个单字符NFA片段，压栈。
- 遇到
*：弹出一个片段，套用闭包规则，压栈。 - 遇到
&：弹出两个片段，套用连接规则，压栈。 - 遇到
|：弹出两个片段，套用并规则，压栈。
完整代码如下：
def build_nfa(postfix_expr): stack = [] state_counter = 0 def new_state(): nonlocal state_counter s = NFAState(state_counter) state_counter += 1 return s for c in postfix_expr: if c == '|': right = stack.pop() left = stack.pop() start = new_state() end = new_state() start.edges.append((EPSILON, left.start)) start.edges.append((EPSILON, right.start)) for s in left.accept_set: s.edges.append((EPSILON, end)) for s in right.accept_set: s.edges.append((EPSILON, end)) stack.append(Fragment(start, {end})) elif c == '&': right = stack.pop() left = stack.pop() for s in left.accept_set: s.edges.append((EPSILON, right.start)) stack.append(Fragment(left.start, right.accept_set)) elif c == '*': frag = stack.pop() start = new_state() end = new_state() start.edges.append((EPSILON, frag.start)) start.edges.append((EPSILON, end)) for s in frag.accept_set: s.edges.append((EPSILON, frag.start)) s.edges.append((EPSILON, end)) stack.append(Fragment(start, {end})) else: start = new_state() end = new_state() start.edges.append((c, end)) end.is_accept = True stack.append(Fragment(start, {end})) return stack.pop()闭包运算里那两条从旧接受状态发出的ε边，非常值得多默写几遍。一条回到frag.start产生循环，一条跳到最终接受状态允许提前退出。两条都缺一不可。
4.3 NFA识别字符串的模拟器
NFA构造出来以后，怎么验证它认识哪些字符串？写一个模拟器。核心是两个操作：ε闭包和单字符转移。
ε闭包的意思是，从一组状态出发，沿着ε边能走到的所有状态的集合。因为NFA在不消费任何字符的情况下可以自由沿着ε边移动。单字符转移就是从一组状态出发，沿着某条字符边能到达的下一组状态。
def epsilon_closure(state_set): closure = set(state_set) stack = list(state_set) while stack: s = stack.pop() for sym, target in s.edges: if sym is EPSILON and target not in closure: closure.add(target) stack.append(target) return closure def move(state_set, symbol): nxt = set() for s in state_set: for sym, target in s.edges: if sym == symbol: nxt.add(target) return nxt def accept_string(frag, text): current = epsilon_closure({frag.start}) for ch in text: current = epsilon_closure(move(current, ch)) return any(s in frag.accept_set for s in current)判断是否接受时，看最后的状态集合是否和frag.accept_set有交集。注意不能只看状态的is_accept标记，因为在构造过程中，某些曾经是接受状态的状态在后续步骤里被“降级”成了普通状态，而frag.accept_set才是当前片段真正有效的接受状态。这个区别务必记牢。
测试一下：
postfix = to_postfix('(a|b)*abb') nfa = build_nfa(postfix) print(accept_string(nfa, 'abb')) # True print(accept_string(nfa, 'aabb')) # True print(accept_string(nfa, 'babb')) # True print(accept_string(nfa, 'ab')) # False这组输出能跑通的话，说明构造逻辑基本没问题。
5. 这次实验我踩过的三个坑（含完整排查链路）
这个实验看起来算法步骤清清楚楚，但真正调试时，隐藏的坑一个接一个。下面三个是我当时实际撞上的，每一个我都写了从“症状出现”到“根因确定”的完整排查过程，方便你复现排查思路。
5.1 闭包漏边：a*被悄悄变成了a+
症状：构造a*后，用空串""测试返回False，用"a"测试返回True，用"aa"测试返回True。看起来就像是把a*实现成了a+。
排查链路：第一步，打印a*的NFA状态表。发现新建的起始状态只有一条ε边连到a的起始状态，没有连到最终接受状态。于是从起始状态出发，不消费字符，ε闭包只能到达a的起始状态，a的接受状态和最终接受状态都到不了。空串自然不被接受。
根因：闭包运算规定，起始状态必须通过ε边同时连接到子表达式起始状态和最终接受状态。只有连接到最终接受状态，a*才能表示“匹配零次”。我当时漏掉了这条边。
修复：在闭包分支里补上start.edges.append((EPSILON, end))。修完后空串和任意多个a都能接受，问题消失。
验证：修复后立刻重跑三个用例：""、"a"、"aaa"。全部返回True。
这个坑告诉我们，测试正则时不要只测“能匹配的串”，至少要补一个“空串能不能匹配”的边界用例。闭包运算是否支持零次匹配，测试空串是最直接的检验。
5.2 片段被污染：连接操作改了共享状态
症状：构造ab|cd后，用"cd"测试返回False，用"ab"测试返回True。这还不太明显；更诡异的是，用"abd"测试也返回了True，而abd根本不该匹配ab|cd。
排查链路：把NFA完整打印出来后，我发现在cd分支里，c字符规则的接受状态上竟然多了一条指向d起始状态的ε边。这看起来是连接运算正确加上的边，但问题是这条边竟然出现在了并运算里的两个分支中，导致起始状态可以跳过c直接进入d，又走一段无关的转移，最终意外接受了abd。
根因：我最初的实现里，NFAState只保存了状态编号，边集合是一个全局的二维数组，不同片段之间通过编号索引共享了状态数据。连接运算修改“左片段接受状态”的边时，修改的是全局数组里的某个状态行；而并运算在合并两个片段时，右片段的起始状态编号恰好和左片段接受状态编号有引用重叠，结果一个操作改了两处。
修复：彻底废弃“全局数组+编号索引”的方案，改成每个状态对象独立持有自己的边列表，也就是第3章里最终展示的邻接表结构。状态对象是独立的内存实体，不会因为修改了一个变量的引用就影响另一个片段。
验证：重新构造ab|cd，跑四组用例："ab"真、"cd"真、"abd"假、"cbd"假。
教训：NFA构造本质上是把多个子片段拼成一棵状态图，所有状态必须是独立分配的新对象。任何“复用对象”“共享编号”的小聪明都会在组合复杂表达式时爆雷。
5.3 多条正则合并成词法分析器时，接受状态编号错乱
症状：做完整词法分析器时，我把[0-9]+和[a-z]+两条正则分别构造NFA后合并成一个总NFA。测试输入"123abc"，期望结果是先识别出整数token，再识别出标识符token。实际运行结果却是：第一个字符就被返回成了标识符token。
排查链路：在总NFA的开始状态上加了一条ε边到两个子NFA的起始状态。使用NFA模拟器跑第一个字符'1'时，当前状态集合同时包含了两个子NFA中各自的数字字符状态和字母字符状态的ε闭包。判断接受状态时，我遍历了所有状态的is_accept标记，发现两个子NFA里负责接受的状态都在当前集合里，而代码总是返回第一个碰到的接受状态，于是字母分支的编号被误用了。
根因：合并多条正则时，子NFA的原有接受状态仍然保留着“接受”标记。但词法分析器需要区分的是“哪种正则匹配了”，而不是“任何一个接受状态匹配了”。所有旧接受状态现在都应该被当成普通状态，真正有效的是每个正则对应的最终终止状态，而这些终止状态必须绑定唯一的token编号。
修复：合并时，为每条正则创建一个新的终止状态，把该正则原接受状态集合里的所有状态用ε边连到新终止状态，在新终止状态上记录token编号；然后清掉所有旧接受状态的is_accept标记。识别时统一检查当前状态集合是否包含某个“带编号的终止状态”。
验证：重新跑"123abc"，第一个阶段返回整数token，第二个阶段返回标识符token；再跑边界用例"abc123"，顺序正确。
老生常谈但确实重要：合并正则不是简单地把NFA拼在一起，而是要让整个大NFA从“接受与否”的二元判断升级成“接受哪个规则编号”的分类判断。这一步做不对，后面子集构造转DFA时还会连带出错。
6. 测试与验证：如何说服自己构造的NFA是对的
代码写完不是结束，你得有系统的方法证明它是对的，不然实验报告里的“测试结果”根本站不住脚。我推荐四层验证，从浅到深。
第一层是基础用例。准备一张测试矩阵，把每个运算单独测一遍，再混合测：
| 正则表达式 | 应接受的字符串 | 应拒绝的字符串 |
|---|---|---|
a | a | 空串、b、aa |
a|b | a、b | 空串、ab |
ab | ab | a、b、空串 |
a* | 空串、a、aaa | b、ab |
(a|b)* | 空串、a、ab、ba | c |
(a|b)*c | c、ac、babbbc | 空串、ab |
a|b* | a、空串、bbb | ab、ba |
a|b*和(a|b)*这个对比尤其有价值，它能检验你的运算符优先级处理是否正确。前者表示“一个a，或任意多个b”；后者表示“由a和b组成任意长度的串”。如果实现时把|和*优先级搞反，这两个正则的NFA会一模一样，那就有问题了。
第二层是自动化对照测试。拿Python自带的re模块当裁判，把测试用例随机生成一批，在re和你的NFA模拟器上跑结果，两边不一致就是Bug。要注意的是re的正则语法和我们实验里用的不太一样：re没有显式的&连接符，括号的含义也可能有差异，所以最好生成只包含字母、|、*和括号的受限正则。基本做法是写一个递归生成器，随机生成简单表达式，再用随机字符串验证。
第三层是可视化验证。这一步强烈推荐，它能把抽象的状态图变成你能直接看到的图片。写一个函数，把NFA转成DOT格式文本，然后用相关渲染工具生成图片。DOT格式非常简单：
def to_dot(frag, all_states): lines = ['digraph NFA {', 'rankdir=LR;'] for s in all_states: shape = 'doublecircle' if s in frag.accept_set else 'circle' lines.append(f' {s.id} [shape={shape}, label="{s.label}({s.id})"];') for sym, target in s.edges: label = 'ε' if sym is None else sym lines.append(f' {s.id} -> {target.id} [label="{label}"];') lines.append('}') return '\n'.join(lines)验证时把a*、(a|b)*c这类表达式渲染出来，用肉眼对比第2章的规则图。很多时候Bug在图片里一眼就能看出来，比对着状态编号打印快得多。
第四层是构造过程的中间断言。可以在构造函数里加一些assert，比如构造完闭包运算后，断言起始状态至少有两条ε边；构造完连接运算后，断言左片段接受状态都已经不是Fragment的accept_set成员。这些断言在复杂表达式里能提前拦住一大批错误。
我的体感是，前三层测试都过了，这个Thompson构造器基本就稳了。后面做DFA实验时可以放心复用。
7. 从实验到工程：DFA化、长匹配与工具链对比
Thompson构造法只是自动化词法分析的起点，它生成的NFA在工程上并不直接可用：NFA存在ε边，多个状态同时活跃，每次读入一个字符都可能要维护一个状态集合，效率比确定性状态机的逐状态转移差一个量级。所以真实词法分析器一定会做子集构造法，把NFA转成DFA，再用跳转表或哈希表加速。
我建议做完本次实验后，顺手把这三件事做了，对理解帮助很大。
第一件：实现子集构造法。把NFA所有状态集合映射成DFA的一个状态，处理ε闭包和字符转移，得到一张确定性跳转表。你会直观看到为什么DFA的状态数最坏情况下是NFA的指数级，但在实际词法规则中往往只扩大几倍。这个实验做完，你对“为什么编译器前端要用DFA而非直接跑NFA”会有真实的体感，而不是只知道一句“DFA更快”。
第二件：实现最长匹配。词法分析器在切分token时，经常遇到一个前缀同时匹配多个规则的情况，比如if既可能是关键字，也可能是标识符的前缀。工程上通用的做法是记录最后一次到达接受状态的位置，如果之后没有接受状态再出现，就回退到那个位置并输出token。这个“最长匹配+回退”机制不需要改NFA，只需要在模拟器里多记录几个变量，但它是词法分析从玩具到可用的关键一步。
第三件：把多正则合并成完整词法分析器后，用一段含不同类型token的代码文本做端到端测试。你会发现最终产物相当于一个微型版的lex系工具：给一组规则，吐出一个切词器。这个感觉挺奇妙的——当年看教材里“flex就是干这个的”一句话，现在是自己亲手把原理走了一遍。
做这个实验，我的另一个建议是：把“状态编号”和“标签”这两个基础设施从一开始就建设好。很多人觉得它们是调试用的次要功能，但事实上，没有标签的NFA在表达式一复杂就完全无法阅读，而有标签的NFA能让你把代码逻辑和Thompson规则逐一对应上。这是我在整个实验里收获最大的一个实操技巧，也是我认为最值得分享给后来者的一点。
如果你有时间，还可以试着把构造器改成支持+、?、字符类和.通配符，你会发现这些都是在五条基础规则上增加一些对应的构造模式，难度不大，但成就感很足。到那时你再回头看最初手写状态机的方案，大概会和我一样感慨：工具化的思路，解决的不仅仅是一次作业，而是一整类问题。
