简介一套用C实现正则表达式转最小化DFA的完整源码适合编译原理课程学习者、自动机理论爱好者以及需要在文本匹配或词法分析中构造底层驱动的开发者。压缩包内仅含1个cpp文件体积约7KB但代码规模超过1000行完整实现了从正则表达式生成NFA、通过子集构造法转换为DFA、再对DFA执行最小化的三个核心阶段。代码对符号表、状态集合、转移函数及闭包运算等关键结构做了封装同时处理了不可达状态与等价状态合并便于读者结合教材中的Thompson构造法、子集构造法和DFA最小化算法逐行对照学习。目前该资源已有191人学习下载既能作为课程实验的参考实现也可在此基础上二次扩展完成更完整的词法分析或正则引擎开发。1. 一个能用正则直接驱动词法的引擎从输入字符串到最小化状态表很多人以为正则转 DFA 是编译原理教材里那种「考试画图题」考完就忘了。但如果你在写词法分析器、协议解析器或者一个需要高速文本匹配的中间件就会发现手写的字符串匹配在复杂规则面前根本撑不住而正则引擎又不能只停留在std::regex这种黑盒调用上。这篇笔记拆的模拟项目X是一个用 C 从零实现的「正则表达式 → NFA → DFA → 最小化 DFA」命令行工具输入(a|b)*abb这类正则输出一张状态转移表。适合两类人一类是正在学编译原理、想把教材算法变成可运行代码的学生另一类是想把 DFA 状态机集成进自己词法分析器的开发者。读完你能跑通它也能照着改出自己的版本。2. 整体架构与核心数据结构AST、NFA、DFA 三层模型如何组织把一个正则字符串变成最小 DFA路上要经过三层中间表示。这三层不是随手建的每一层都对应一类算法操作AST 层处理优先级和结合性NFA 层用少量规则拼出语言结构DFA 层去掉空转移并为状态合并做准备。理清这层关系后面写代码才不会到处补丁。2.1 模块划分与文件职责整个项目按「表示层 → 转换层 → 输出层」拆成五个文件每个文件只干一件事。拆文件的原则很简单凡是超过两百行的 C 代码按「数据结构归属」而不是「算法流程」来分。比如 NFA 的状态池归nfa.h/cppDFA 的划分表格归dfa.h/cpp谁改动谁就拿走自己的数据。文件职责对外接口regex_parser.h/cpp正则字符串 → ASTNode* parse(const string)nfa.h/cppAST → NFAFrag buildNFA(Node*)dfa.h/cppNFA → DFA → 最小化DFA buildDFA(NFA)main.cpp命令行入口与输出int main(int, char**)test.cpp回归测试与差分验证void runTests()主流程在main.cpp里只有十几行真正的工作全部在转换函数里完成。我见过不少人喜欢把 AST 节点、NFA 边、DFA 状态放到一个巨大的struct Automaton里结果每次改造都要把整个文件翻一遍。这里用Frag结构把 NFA 的「起点和接受态」打包返回天然屏蔽了内部细节后一阶段只需要盯住两个状态编号。2.2 数据结构状态点、转移边与 NFA 片段NFA 的状态用一个结构体表示核心是转移边的存储方式。项目里没有单独定义Edge类而是把边直接挂在状态上用vectorpairchar,int存储char \0表示 ε 转移。常见做法是开一个全局std::vectorState当状态池状态编号就是数组下标这样联盟状态、遍历状态集都会很顺手。struct State { int id; // 状态编号等于在状态池里的下标 vectorpairchar, int out; // 每条边字符 目标状态\0 表示 ε bool isEnd false; // 是否为接受态 }; struct Frag { int start; int end; // NFA 子图的唯一接受态 };这个设计的核心思想NFA 构造时始终保证每个片段只有一个接受态。Thompson 构造法里所有运算都是「拿若干片段拼成新片段」唯一接受态这个约定让拼接操作不需要遍历整个图只用Frag的两个整数就能完成连接。2.3 主流程从输入到输出的五段管线main.cpp里的数据流是线性的每一段的输出恰好是下一段的输入。这种管线结构在调试时非常友好——你想知道正则解析错了还是子集构造错了只要在任意两段之间加上一个 dump 函数打印中间结构即可。我把五个阶段列在这里后面几章逐段展开。int main(int argc, char* argv[]) { if (argc 2) { cerr Usage: regex2dfa \(a|b)*abb\ endl; return 1; } string pattern argv[1]; Node* ast parse(pattern); // 阶段1正则 → AST Frag nfa buildNFA(ast); // 阶段2AST → NFA DFA dfa buildDFA(nfa); // 阶段3NFA → DFA minimizeDFA(dfa); // 阶段4DFA → 最小化 DFA printDFA(dfa); // 阶段5输出状态表 return 0; }阶段3内部又分成两步先求 ε 闭包和 move 集合做子集构造再对生成的 DFA 做最小化划分。所以buildDFA里会先构建一张未最小化状态表再调用minimizeDFA原地改写。这个设计让「最小化」成为可选的优化步骤——如果你只是临时要一个 DFA可以注释掉阶段4直接看原始转换结果。3. 正则解析把一串字符变成语法树是后面所有转换的地基正则转 DFA 的教科书算法往往直接从「后缀表达式构造 NFA」讲起但实际写代码时第一步要把(a|b)*abb这样的字符串拆成机器能处理的语法树。这一步没做好后面 NFA 构造再漂亮也是空中楼阁。3.1 分词运算符与字符的边界划分解析的第一步是分词。正则里的运算符只有|、*、、?、括号和「显式连接符」这里用.表示其余字符都是普通字符。注意.在正则语义里通常是「任意字符」但在内部实现中我们把它当连接符避免和通配符混淆。真正的通配符需要单独设计字符类这里先不支持。分词还有一个关键点自动插入连接符。ab在正则语义里是「先 a 后 b」但在语法树里必须表达为CONCAT(a, b)节点。常见做法是维护一个canFollow布尔值遇到普通字符、)、*等可以结束一个原子的符号时如果下一个 token 是普通字符或(就自动插入一个.连接符。这一步错一个条件整棵树的形态就变了。vectorToken tokenize(const string s) { vectorToken tokens; bool canFollow false; // 上一个 token 是否可以出现在连接符左侧 for (size_t i 0; i s.size(); i) { char c s[i]; if (c \\) { // 转义字符如 \* 表示字面量 * if (i 1 s.size()) throw runtime_error(trailing backslash); if (canFollow) tokens.push_back({., 0}); tokens.push_back({c, s[i]}); canFollow true; continue; } if (c () { if (canFollow) tokens.push_back({., 0}); // a( a.( 自动插连接符 tokens.push_back({(, 0}); canFollow false; } else if (c )) { tokens.push_back({), 0}); canFollow true; } else if (c | || c *) { tokens.push_back({c, 0}); canFollow false; // 注意* 之后还可以跟普通字符这行是错的 } else { if (canFollow) tokens.push_back({., 0}); tokens.push_back({c, c}); canFollow true; } } return tokens; }上面代码里我故意留了一个容易写错的地方。*是后缀运算符它只会作用于它左边的原子之后如果紧跟a应该在*和a之间插入连接符所以canFollow在遇到*时应该保持true而不是变成false。这个 bug 的典型症状是a*b被解析成「a 星号然后 b」但没有连接关系最后生成的 DFA 只能匹配b或aaa...漏掉了aab。排查方法很简单把 token 序列打印出来看.有没有出现在*和b之间。3.2 构建 AST基于优先级的递归下降token 序列准备好之后用递归下降解析器构建 AST。这里优先级从低到高是|并、.连接左结合、*?后缀最高。递归下降的写法是每个优先级对应一个函数parseUnion调parseConcatparseConcat调parseRepeatparseRepeat调parseAtom层层向下。每个函数解析完自己那一层的操作符后把结果返回上一层。struct Node { char type; // c字符, .连接, |并, *闭包 char ch; // typec 时保存字符 Node* left; Node* right; Node(char t, char c 0) : type(t), ch(c), left(nullptr), right(nullptr) {} }; Node* parseConcat() { Node* left parseRepeat(); // 先解析一个可重复的单元 while (peek() .) { // 循环处理连续的连接ab.c ((a.b).c) nextToken(); Node* right parseRepeat(); Node* node new Node(.); node-left left; node-right right; left node; } return left; }这段代码有几个值得注意的细节。第一parseConcat用循环而不是递归处理多个连接项避免构建出左深/右深不均匀的二叉树。第二parseRepeat解析到*或时会创建对应的闭包节点并把parseAtom返回的原子节点作为它的子节点。第三所有节点用裸指针new分配项目里没有做内存池这点在几万次解析的测试下没问题但如果你要把它嵌进长时间运行的服务里应该改成unique_ptr或 Arena 分配器。AST 结构为下一步 NFA 构造提供了关键便利构造 NFA 时只需要对六种节点类型做递归分派不需要再关心括号和优先级。括号在解析阶段已经被「吃掉」了(a|b)*会变成*节点左子节点是|节点左右叶节点是字符a和b整棵树的形状和正则语义一一对应。3.3 AST 的正确性验证先打印再转换解析器写完的第一件事不是去接 NFA而是写一个dump(Node*)函数把语法树以括号表达式形式打印出来。比如输入(a|b)*abb合法的输出应该是(.((*(|(a,b)),a),b),b)。这个函数只要十几行但它能把「括号丢失」「连接符插入错误」「优先级颠倒」三类问题直接暴露在眼前。void dump(Node* n) { if (!n) return; if (n-type c) { cout n-ch; return; } cout ( n-type ,; dump(n-left); if (n-right) { cout ,; dump(n-right); } cout ); }我当时第一次写完解析器输入a|b*发现 dump 结果是(|(a,*(b)))。按正则语义b*的优先级高于|这个结果是正确的。但如果输入(ab)*得到(*,(a,b))而不是(*,(.(a,b)))那说明连接符插入逻辑漏了括号内部的情况。把这几个用例跑一遍基础就算稳了。4. NFA 构造与子集构造Thompson 算法到 DFA 状态集编号AST 就绪后进入整条链路里算法密度最高的阶段。这一章从 Thompson 构造法出发逐段实现 NFA再把 NFA 通过子集构造变成 DFA。每一步都有对应的数据结构变化不建议跳过任何一个中间层直接写「正则 → DFA」。4.1 Thompson 构造五种基础运算的状态拼接Thompson 构造法把每种正则运算映射为一种固定的状态图拼接模式。字符a是两个状态加一条标号a的边连接A.B是把 A 的接受态和 B 的起始态用 ε 边串起来并集A|B是新增一个起始态、一个接受态各自用 ε 边连到两个子图闭包A*是新增两个状态形成绕回环类似闭包但至少执行一次。实现时核心数据结构是前面定义的Frag。每次运算接收一个或两个Frag返回一个新的Frag。代码里的newState()负责向全局状态池追加状态并返回编号addEdge(from, ch, to)在状态池里给某个状态追加一条边。Frag buildNFA(Node* node) { if (node-type c) { int s newState(), e newState(); addEdge(s, node-ch, e); return {s, e}; } if (node-type .) { Frag left buildNFA(node-left); Frag right buildNFA(node-right); addEdge(left.end, \0, right.start); // 左接受态 → 右起始态ε return {left.start, right.end}; } if (node-type |) { Frag left buildNFA(node-left); Frag right buildNFA(node-right); int s newState(), e newState(); addEdge(s, \0, left.start); // 新起始态分两路 addEdge(s, \0, right.start); addEdge(left.end, \0, e); // 两路汇入新接受态 addEdge(right.end, \0, e); return {s, e}; } if (node-type *) { Frag inner buildNFA(node-left); int s newState(), e newState(); addEdge(s, \0, inner.start); // 从新起始态进入内部 addEdge(s, \0, e); // 也允许直接跳过匹配空串 addEdge(inner.end, \0, inner.start); // 内部末尾绕回起点实现循环 addEdge(inner.end, \0, e); // 循环结束后走向接受态 return {s, e}; } // 其他节点类型抛异常 }几个实现细节值得说明。第一闭包运算里「允许匹配空串」和「循环任意次」是由那两条s→e和inner.end→inner.start的 ε 边共同保证的如果漏掉s→e(a*)就不能匹配空串。第二所有 ε 边用\0表示在子集构造阶段需要特殊处理后面会看到。第三本项目的和?会先在解析阶段改写为等价形式A转成A.A*A?转成A|εε 用空字符节点表示这样buildNFA不需要为这两个运算符单独写分支。实际运行一次ab|aNFA 状态数应该是 8 个左右。跑完构造后把这 NFA 的每条边打印出来看一遍确认每个Frag的接受态只有一个再进入下一步。4.2 ε 闭包与 move子集构造的两个基础操作子集构造的核心是从 NFA 状态集合构建 DFA 状态其中两个操作贯穿始终eclosure(S)求某个状态集合的全体 ε 可达状态move(S, c)求集合 S 中所有经过字符c边一步可达的状态集合。它们配合起来完成一件事把 NFA 的「不确定性」折叠成分组每个分组对应一个 DFA 状态。setint eclosure(const setint s) { setint result s; vectorint stack(s.begin(), s.end()); while (!stack.empty()) { int cur stack.back(); stack.pop_back(); for (auto [ch, to] : statePool[cur].out) { if (ch \0 !result.count(to)) { // 只沿 ε 边扩展 result.insert(to); stack.push_back(to); } } } return result; } setint move(const setint s, char c) { setint result; for (int id : s) { for (auto [ch, to] : statePool[id].out) { if (ch c) result.insert(to); } } return result; }这两个函数加起来不到三十行但它们是整个子集构造里最容易出 bug 的位置。eclosure用显式栈而不是递归是因为 NFA 的 ε 边可能形成环A*构造必然产生环递归写法在环存在时会栈溢出。另外注意move只收集一步可达的目标状态收集完之后必须立刻对结果再执行eclosure这是子集构造的标准步骤。很多新手把这两个步骤分开写导致 DFA 漏掉状态。4.3 子集构造主循环把集合映射成编号有了两个基础操作主循环就是经典的「按未处理队列扩张」。每一轮取出一个 DFA 状态对应一个 NFA 状态集合对输入 alphabet 里的每个字符求出eclosure(move(S, c))查表看看这个新集合是否已经出现过没出现过就分配新编号并入队。struct DFA { vectormapchar, int transitions; // 每个 DFA 状态字符 → 目标状态编号 vectorbool isAccept; // 是否为接受态 }; DFA buildDFA(const Frag nfa) { DFA dfa; mapsetint, int dict; // NFA 状态集合 → DFA 状态编号 vectorsetint pending; setint init eclosure({nfa.start}); dict[init] 0; pending.push_back(init); dfa.transitions.emplace_back(); dfa.isAccept.push_back(containsAccept(init, nfa.end)); for (size_t i 0; i pending.size(); i) { for (char c : getAlphabet()) { setint ns eclosure(move(pending[i], c)); if (ns.empty()) continue; int nextId; if (dict.count(ns)) { nextId dict[ns]; } else { nextId pending.size(); dict[ns] nextId; pending.push_back(ns); dfa.transitions.emplace_back(); dfa.isAccept.push_back(containsAccept(ns, nfa.end)); } dfa.transitions[i][c] nextId; } } return dfa; }这里getAlphabet()返回正则里出现过的所有普通字符由解析阶段收集。关键点在于pending和dfa.transitions是同步扩展的pending[i]永远对应dfa.transitions[i]读完pending的同时建完全部 DFA 状态。containsAccept检查集合里是否包含 NFA 接受态nfa.end——注意 Thompson 构造里每个片段有唯一接受态所以这个检查就是s.count(nfa.end)。跑一次(a|b)*abb未最小化的 DFA 状态数量通常在 8 到 10 个。如果发现状态数爆炸几十个最常见的原因是eclosure漏了把起始状态自身加入结果导致每次闭包都不完整状态被反复创建。5. DFA 最小化实战与常见问题排查从 9 个状态压到 4 个的划分算法DFA 最小化本身是一个让人容易「感觉懂了但写不对」的算法。本项目采用基于反向划分的迭代法把状态按接受/非接受分成两组然后不断按「每个字符转移到哪个组」来细分直到分组不再变化。最后每组保留一个代表状态把其他状态从转移表中删除。5.1 划分算法的实现细节先初始化分区接受态和非接受态是两个初始组。然后反复扫描每个组看组内状态对每个字符的转移目标是否属于同一个组。如果组内状态 A 和状态 B 在字符c上分别转移到组 1 和组 2那 A 和 B 必须被拆开。注意拆开时要按「转移目标组编号」重新分组不是简单地两两比较。vectorint minimizeDFA(DFA dfa) { int n dfa.transitions.size(); vectorint group(n, 0); for (int i 0; i n; i) if (dfa.isAccept[i]) group[i] 1; // 初始划分非接受0接受1 int groupCount 2; while (true) { vectorint oldGroup group; vectormapint, int signature(n); for (int s 0; s n; s) { for (auto [ch, to] : dfa.transitions[s]) { int g oldGroup[to]; // 关键基于「上一轮」分组 if (!signature[s].count(g)) signature[s][g] ch; } } // 按 signature 重新标号分组 mapvectorint, int idBySig; vectorint newGroup(n); int newCount 0; for (int s 0; s n; s) { vectorint sig; for (auto [g, ch] : signature[s]) sig.push_back(g); sig.push_back(oldGroup[s]); if (!idBySig.count(sig)) idBySig[sig] newCount; newGroup[s] idBySig[sig]; } if (newCount groupCount) break; // 分组数不再变化收敛 group newGroup; groupCount newCount; } // 按 group 合并状态重建转移表 return group; }这个实现的关键是每轮都基于oldGroup生成新的分组绝不能在原group上原地更新。我在最初实现时直接在group里改编号结果两轮之后就出现「组 1 的状态转移到组 1但因为组内编号已变导致拆不干净」的怪现象最终状态数永远压不下去。另外注意 signature 里要拼上oldGroup[s]本身——两个状态如果字符转移组完全相同但一个在接受组一个在非接受组初始化时就已经分开但为了保险每轮把自身组号也放进签名里参与比对。5.2 压缩状态表从分区到最终 DFA拿到分组后重建一个更小的 DFA。策略是每个分组保留编号最小的状态作为代表遍历原 DFA 的每个状态把它的每条边重定向到对应分组的代表。最终转移表只保留代表状态。DFA compressDFA(const DFA old, const vectorint group) { mapint, int rep; // 组号 → 代表状态 for (int s 0; s old.transitions.size(); s) if (!rep.count(group[s])) rep[group[s]] s; int newN rep.size(); DFA res; res.transitions.resize(newN); res.isAccept.resize(newN); for (int s 0; s old.transitions.size(); s) { if (rep[group[s]] ! s) continue; // 只处理代表状态 int ns rep[group[s]]; // 新编号 res.isAccept[ns] old.isAccept[s]; for (auto [ch, to] : old.transitions[s]) res.transitions[ns][ch] rep[group[to]]; // 重定向到目标组代表 } return res; }合并后要立刻检查一件事代表状态如果恰好是非接受态组里的第一个而组里另一个状态是接受态会丢掉接受信息。上面的实现里在重建时重新读取old.isAccept[s]只要每个接受态的状态编号在合并后仍然指向isAccept问题就不会出现。建议合并完跑一遍「最小 DFA 全遍历」从初始状态出发沿每条边走确认每个接受态都能从某条路径到达。5.3 最小化结果的验证方法最小化是否真的「最小」可以通过两种方式验证。一是用穷举法把最小化前后的 DFA 分别模拟 1 到 6 个字符长度的所有输入字符串字母表限定为项目支持的 ASCII 小写字母比较接受集合是否完全一致。二是用反例手动构造一对等价状态确认算法把两者合并了。前者用来回归后者用来确认算法没有过度合并。我习惯在test.cpp里写一个verifyEquivalence(DFA a, DFA b, int maxLen)函数用 BFS 同时跑两个自动机逐位比对接受状态。这个函数虽然简单但在后续二次开发时它几乎每天都用——每改一遍最小化逻辑就全量跑一遍随机生成的正则能挡住大量隐蔽的回归问题。5.4 常见问题排查5 个我真实踩过的坑1. 现象输入a输出空表程序直接退出。原因正则字符串里只有单个字符解析器自动插入连接符后 token 序列和 AST 都没问题但子集构造里getAlphabet()从空集合取字符外层循环一次都没跑DFA 只有初始状态没有边。 解决在getAlphabet()之外额外维护一个hasAlphabet标志当字母表为空时直接构造单状态 DFA接受态为初始状态本身。更稳妥的写法是buildDFA开头就把初始 DFA 状态造好不要依赖 for 循环填充。2. 现象(a|b)*abb匹配abb成功但匹配ab失败。原因仔细查 NFA发现*闭包的「跳过路径」s→e没建a*无法匹配空串导致(a|b)*至少要消费一个字符。 解决闭包分支里检查addEdge(s, \0, e)这一行是否存在。我后来给所有构造分支加了断言的习惯每个Frag返回前必须保证end状态存在且没有多余出边。3. 现象DFA 状态数爆炸(a|b)*abb生成二十多个状态。原因move函数里只收集了直接目标状态没有在每轮收敛后做 ε 闭包或者闭包函数没有把集合自身元素包含进去。 解决统一写成eclosure(move(...))并且闭包入口处setint result s。排查时可以打印pending[i]集合的 size如果所有集合都偏小先查闭包如果偏大再查是否把 ε 边当普通字符处理了。4. 现象最小化后 DFA 出现「死状态」无法到达的初始状态或多条等价路径导致模拟不准。原因最小化分组里把一些「转移矩阵完全相同但初始状态不同」的状态合并了但压缩时没有保留初始状态的分组信息。 解决压缩前手动记录初始状态所在组号压缩后把代表状态设为新初始状态。另外建议把无任何字符可达、且非接受的状态在最小化前直接删除它们不影响语言识别但会污染分组计算。5. 现象字符*在正则字符串里出现分词结果变成「乘号」。原因字符*在tokenize里归属运算符但正则语义里它是后缀操作符如果正则本身是字面量\*需要转义。项目的语义标准和常见正则库一致。 解决在文档里明确规定本项目不支持未转义的原义*但支持\*同时给tokenize增加「标签不匹配警告」遇到未知转义序列直接抛异常而不是静默吞掉。6. 二次开发把「正则 → 最小 DFA」装进一个可复用的词法器组件有了前面这些代码你已经拿到一个能跑通的命令行工具。但一个真正的项目不会只要「打印状态表」它需要把这个 DFA 当作词法分析器的内核。这一章分享三个最常用的改造思路封装成类、接入最长匹配、差分验证。6.1 第一步封装成可复用的组件把main.cpp里的流程收拢成一个类对外只暴露build(pattern)和match(word)两个接口。build负责完成全部编译并缓存状态表match从初始状态出发逐字符走表走到末尾时判断当前状态是否接受。class RegexDFA { public: bool build(const string pattern) { try { Node* ast parse(pattern); Frag frag buildNFA(ast); dfa_ buildDFA(frag); vectorint group minimizeDFA(dfa_); dfa_ compressDFA(dfa_, group); return true; } catch (const exception e) { cerr build error: e.what() endl; return false; } } bool match(const string input) { int cur 0; for (char c : input) { auto it dfa_.transitions[cur].find(c); if (it dfa_.transitions[cur].end()) return false; cur it-second; } return dfa_.isAccept[cur]; } private: DFA dfa_; };这样封装之后上层业务完全不需要关心正则编译细节只需要维护一个RegexDFA实例。注意match匹配的是「完整字符串」和标准库regex_match语义一致如果你要的是「子串匹配」需要在匹配失败时从下一个位置重新尝试这是另一层逻辑不适合塞进这个类里。6.2 第二步扩展到最长匹配与 token 类型词法分析器的真实场景里一个输入字符串要匹配多个模式比如关键字、标识符、数字每个模式对应一个 DFA 的接受态。这时可以把每个接受态打上 token 类型标签然后把match改造成「从当前位置开始尽可能多地吃字符停在最后一个接受态」。具体做法在DFA结构里加一个mapint, int acceptTypebuild时对每个模式传入它的 token id。模拟时维护一个lastAcceptPos和lastAcceptType每走一步就检查当前状态是否为接受态并更新记录。走到死路或字符串末尾时回退到lastAcceptPos输出 token再把扫描位置移到那里。这套「最长匹配 回退」机制是词法分析器的基础也是 Lex 类的工具内部的核心策略。6.3 第三步用差分测试验证改造正确性改造任何一行状态转移逻辑后依赖单一用例不足以证明正确性。我建议写一个随机测试生成器随机组合a、b、c三个字符与|、*、括号生成 200 个正则表达式对每个表达式做三件事——用这个 DFA 匹配 1 到 5 长度的所有字符串用std::regex作为参考实现匹配同样的字符串然后逐条比对结果。DFA 与参考实现不一致时输出正则和触发字符串进行人工分析。这个测试的价值有两层那些「看似聪明实则错误」的优化比如跳过 ε 闭包、提前合并状态往往只会在特定输入组合下暴露随机测试能把这类隐含回归找出来。我自己的经验是把参考实现从std::regex换成自己写的 NFA 模拟器效果更好因为std::regex的语义比如*是否贪婪、空字符匹配规则和我们的 DFA 可能存在细微差别直接比对会误导排查方向。从那以后我每写一个自动机相关的模块都把「随机差分测试」作为提交前的强制步骤先跑 200 个随机正则再跑一组手写的边界用例空串、单字符、大量交替、嵌套闭包。代码改到哪一步往往自己心里没数测试一跑问题立刻摆到眼前。希望这份笔记能帮你少踩几个我在 NFA 和 DFA 之间反复横跳时才踩过的坑也希望你改出来的引擎比这个版本更快、更顺手。本文还有配套的精品资源点击获取