简介一份以C语言实现的正则表达式转最小化DFA源码面向具备C基础、正在学习编译原理或自动机理论的CS专业学生与开发者。程序代码共1000余行依次实现三个核心环节先将正则表达式解析为NFA非确定性有限自动机再通过子集构造法将NFA确定化为DFA最后对DFA执行最小化操作覆盖了理论课程中从Regex到DFA的经典构造方法。压缩包为rar格式包含1个cpp源文件包体仅7KB方便直接阅读与改造。目前已有191人学习下载。资源价值在于打通从正则文法到状态机的完整算法链路——无论是文本模式匹配、自研简易正则引擎还是巩固编译前端知识都能从代码中提取数据结构设计与转换思路迁移到自己的项目中去。1. 正则表达式转最小化DFA从一行匹配到一个状态机做文本过滤、协议字段提取、编译器词法分析的时候很多人第一反应是拿正则表达式库直接匹配。可一旦你面对嵌入式环境、海量日志流或者想搞清楚正则引擎匹配的本质就会意识到正则表达式在做完一次转换之后可以变成一张确定性的DFA匹配时只需要查表跳转、没有回溯也没有指数爆炸。把正则表达式转成最小化DFA是编译原理里最值得亲手实现一遍的管道先构造NFA再用子集构造法变成DFA最后用划分法压掉等价状态。这篇笔记按这条线用C把每一步落到可编译的代码参数怎么设、坑在哪都写在对应位置。2. 先构造AST再生成NFAThompson构造法与表达式解析2.1 为什么非要用NFA当中间站两种构造路线的取舍直接从正则表达式构造DFA在理论上完全可以做经典算法是正则表达式求导或Brzozowski导数但实现起来要处理大量代数化简很容易在细节上翻车。常见做法是先构造NFA再用子集构造法转DFA因为Thompson构造法与AST结构一一对应每个正则子表达式生成一个小片段片段之间用ε转移连接逻辑清晰、边界好查。NFA的缺点是匹配时要维护一个活动状态集合每次读入字符都要对集合里的每个状态做迁移和ε闭包计算DFA的优点是每个状态只有一个确定的去向匹配过程退化成一次查表。用NFA当中间站等于把“匹配”和“构造”分开构造阶段负责把正则变成图匹配阶段只认图。这条路线最大的价值是每一阶段都能单独测试出了问题知道该查谁。2.2 正则AST的数据结构把字符类、连接、选择、重复统一成节点AST节点要覆盖正则的基本操作字符、连接、选择、闭包。我一开始只设计四种节点后来发现处理、?时要在解析阶段复制子树来展开成a aa*代码啰嗦还容易内存泄漏所以直接把PLUS、OPT加进节点类型让构造阶段去处理反而更干净。enum class NodeType { CHAR, CAT, ALT, STAR, PLUS, OPT, EPSILON }; struct ASTNode { NodeType type; std::vectorstd::pairunsigned char, unsigned char ranges; // 字符区间 bool negate false; // [^...] 取反 std::vectorASTNode* children; // CAT、ALT 的子节点 ASTNode* child nullptr; // STAR、PLUS、OPT 的单一子节点 ~ASTNode() { for (auto* c : children) delete c; delete child; } };EPSILON节点表达空串处理()、空片段、a?的“什么都不匹配”分支都需要它。ranges用区间而不是单个字符是为了让[a-z]在NFA里只生成一条边匹配时判断lo c hi即可不必拆成26条边。negate先存在AST里构造NFA时再按补集展开。2.3 递归下降解析器把字符串变成AST解析器按正则的文法写递归下降表达式由|分隔的若干连接项组成连接项由若干因子组成因子是基本元素后跟*、、?。核心逻辑如下class RegexParser { public: explicit RegexParser(const std::string s) : s_(s) {} ASTNode* parse() { ASTNode* node parseExpr(); if (pos_ ! s_.size()) throw std::runtime_error(unexpected char); return node; } private: std::string s_; size_t pos_ 0; int depth_ 0; ASTNode* parseExpr() { ASTNode* left parseCat(); while (pos_ s_.size() s_[pos_] |) { pos_; ASTNode* right parseCat(); left new ASTNode{NodeType::ALT, {}, false, {left, right}, nullptr}; } return left; } ASTNode* parseCat() { std::vectorASTNode* items; while (pos_ s_.size() s_[pos_] ! | s_[pos_] ! )) { items.push_back(parseFactor()); } if (items.empty()) return new ASTNode{NodeType::EPSILON}; if (items.size() 1) return items[0]; return new ASTNode{NodeType::CAT, {}, false, std::move(items), nullptr}; } ASTNode* parseFactor() { if (depth_ 1000) throw std::runtime_error(regex nested too deep); ASTNode* base parsePrimary(); --depth_; while (pos_ s_.size() (s_[pos_] * || s_[pos_] || s_[pos_] ?)) { char op s_[pos_]; if (op *) base new ASTNode{NodeType::STAR, {}, false, {}, base}; else if (op ) base new ASTNode{NodeType::PLUS, {}, false, {}, base}; else if (op ?) base new ASTNode{NodeType::OPT, {}, false, {}, base}; } return base; } ASTNode* parsePrimary() { if (pos_ s_.size()) throw std::runtime_error(unexpected end); char c s_[pos_]; if (c () { ASTNode* node parseExpr(); if (pos_ s_.size() || s_[pos_] ! )) throw std::runtime_error(missing )); pos_; return node; } if (c [) return parseCharClass(); if (c \\) return parseEscape(); if (c .) { ASTNode* node new ASTNode{NodeType::CHAR}; node-ranges.push_back( {static_castunsigned char(0), static_castunsigned char(255)}); return node; } if (c ) || c | || c * || c || c ?) throw std::runtime_error(unexpected meta char); ASTNode* node new ASTNode{NodeType::CHAR}; node-ranges.push_back({static_castunsigned char(c), static_castunsigned char(c)}); return node; } };parseCharClass和parseEscape是字符层面的细节parseCharClass需要处理开头的^取反以及[a-z0-9]这种多区间parseEscape把\d、\w、\n展开成对应区间。这里为了控制篇幅没有把这两个函数展开教学用例只用到[a-z]和普通转义按同样的区间思路补全即可。depth_计数器很重要嵌套深度超过1000直接抛异常避免递归解析爆栈。2.4 Thompson构造法片段拼接的细节与完整代码Thompson构造的核心是“片段”这个概念每个AST节点对应一个NFA片段包含一个开始状态和一组接受状态。片段之间只通过ε边拼接构造过程不读字符、不做匹配只建图。struct NFA { struct Edge { int to; bool eps; unsigned char lo, hi; }; std::vectorstd::vectorEdge g; int start 0; std::setint accept; int newState() { g.emplace_back(); return static_castint(g.size()) - 1; } void addEps(int from, int to) { g[from].push_back({to, true, 0, 0}); } void addChar(int from, int to, unsigned char lo, unsigned char hi) { g[from].push_back({to, false, lo, hi}); } }; struct NFAFragment { int start; std::vectorint accepts; }; NFAFragment buildNFA(ASTNode* node, NFA nfa) { NFAFragment frag; if (node-type NodeType::CHAR) { int s nfa.newState(); int a nfa.newState(); if (node-negate) { auto ranges complementRanges(node-ranges); for (auto [lo, hi] : ranges) nfa.addChar(s, a, lo, hi); } else { for (auto [lo, hi] : node-ranges) nfa.addChar(s, a, lo, hi); } frag {s, {a}}; } else if (node-type NodeType::EPSILON) { int s nfa.newState(); int a nfa.newState(); nfa.addEps(s, a); frag {s, {a}}; } else if (node-type NodeType::CAT) { NFAFragment l buildNFA(node-children[0], nfa); NFAFragment r buildNFA(node-children[1], nfa); for (int a : l.accepts) nfa.addEps(a, r.start); frag {l.start, r.accepts}; } else if (node-type NodeType::ALT) { NFAFragment l buildNFA(node-children[0], nfa); NFAFragment r buildNFA(node-children[1], nfa); int s nfa.newState(); int a nfa.newState(); nfa.addEps(s, l.start); nfa.addEps(s, r.start); for (int x : l.accepts) nfa.addEps(x, a); for (int x : r.accepts) nfa.addEps(x, a); frag {s, {a}}; } else if (node-type NodeType::STAR) { NFAFragment inner buildNFA(node-child, nfa); int s nfa.newState(); int a nfa.newState(); nfa.addEps(s, inner.start); nfa.addEps(s, a); for (int x : inner.accepts) { nfa.addEps(x, inner.start); nfa.addEps(x, a); } frag {s, {a}}; } else if (node-type NodeType::PLUS) { NFAFragment inner buildNFA(node-child, nfa); int s nfa.newState(); int a nfa.newState(); nfa.addEps(s, inner.start); for (int x : inner.accepts) { nfa.addEps(x, inner.start); nfa.addEps(x, a); } frag {s, {a}}; } else if (node-type NodeType::OPT) { NFAFragment inner buildNFA(node-child, nfa); int s nfa.newState(); int a nfa.newState(); nfa.addEps(s, inner.start); nfa.addEps(s, a); for (int x : inner.accepts) nfa.addEps(x, a); frag {s, {a}}; } return frag; }这段代码里有几个关键点。ALT必须新建一个接受状态让两个分支的接受状态都通过ε边汇聚到它而不是直接复用两个子片段的接受状态。如果不合并成单点后面子集构造时ε闭包会把多个接受状态继续往下传播DFA的接受判定会出现偏差。STAR除了补充进入内部和退出的ε边还必须加一条从新开始状态直接到新接受状态的ε边这是“匹配零次”的唯一路径。PLUS少了这条零次边OPT则保留它但不连接内部接受状态到自身。这个片段接口统一为“单开始、单接受”是整条流水线能继续往前走的前提。3. 子集构造法把NFA转成DFA用ε闭包消除不确定性3.1 为什么用子集构造而不是直接模拟NFANFA匹配时活动状态是一个集合每读一个字符要对集合里所有状态执行move再对结果做ε闭包集合的规模可能随输入长度波动。DFA匹配时活动状态是一个整数每次转移直接查表。子集构造法做的事情就是把NFA的“状态集合”当作DFA的“一个状态”显式建出来。最坏情况下DFA状态数是NFA状态数的指数但常见正则表达式远达不到这个上界而对文本匹配来说一次扫描O(n)的代价是刚需。用一个简单例子看状态膨胀正则ab|acNFA状态数大概8个子集构造后有效状态3个初态读a到一个状态该状态读b到接受读c到接受其中两个接受状态其实等价。如果不最小化状态2和状态3就会白白占两份空间如果正则再复杂一点等价状态的浪费会翻倍。3.2 epsilon闭包与move两个基础函数using StateSet std::setint; StateSet epsilonClosure(const NFA nfa, const StateSet states) { StateSet result states; std::vectorint stack(states.begin(), states.end()); while (!stack.empty()) { int s stack.back(); stack.pop_back(); for (const auto e : nfa.g[s]) { if (e.eps !result.count(e.to)) { result.insert(e.to); stack.push_back(e.to); } } } return result; } StateSet move(const NFA nfa, const StateSet states, unsigned char c) { StateSet result; for (int s : states) { for (const auto e : nfa.g[s]) { if (!e.eps e.lo c c e.hi) { result.insert(e.to); } } } return result; }epsilonClosure用显式栈而不是递归因为ε边可能形成环STAR结构里就有回到自身的ε边递归写法容易踩爆调用栈。初始状态在做子集构造前也必须先闭包因为NFA的开始状态可能立刻通过ε边走到其他状态。move只看非ε边区间判断用unsigned char保证0到255的字节值不会因符号位出问题。3.3 用队列完成子集构造并编号子集构造的循环本质上是一个队列从初态闭包开始每次对一个DFA状态、一个字符类计算move closure得到的新集合如果没见过就分配新编号压入待处理队列。下面的实现用vector充当队列因为循环条件会在每次迭代重新读取states.size()新增状态自然会在后续轮次被处理。struct DFA { int start 0; std::vectorstd::vectorint trans; std::vectorbool accept; }; bool containsAccept(const NFA nfa, const StateSet s) { for (int x : s) if (nfa.accept.count(x)) return true; return false; } DFA subsetConstruction(const NFA nfa, int numClasses) { DFA dfa; std::mapStateSet, int id; std::vectorStateSet states; StateSet init epsilonClosure(nfa, {nfa.start}); id[init] 0; states.push_back(init); dfa.accept.push_back(containsAccept(nfa, init)); dfa.trans.emplace_back(numClasses, -1); for (size_t i 0; i states.size(); i) { for (int j 0; j numClasses; j) { unsigned char c static_castunsigned char(j); StateSet t epsilonClosure(nfa, move(nfa, states[i], c)); if (t.empty()) continue; auto it id.find(t); if (it id.end()) { int nextId static_castint(states.size()); id[t] nextId; states.push_back(t); dfa.accept.push_back(containsAccept(nfa, t)); dfa.trans.emplace_back(numClasses, -1); dfa.trans[i][j] nextId; } else { dfa.trans[i][j] it-second; } } } dfa.start 0; return dfa; }参数numClasses表示字符集合被分成多少列。教学实现里直接传256每个字节一列最简单。生产环境我一般先做字符等价类收集NFA所有边上的lo和hi 1把它们当作切分点把0到255切成若干区间同一区间内的字符对所有状态行为一致。这样trans[j][k]的矩阵从“状态数 × 256”缩成“状态数 × 等价类数”内存和后续最小化迭代都能省一大截。提示for (size_t i 0; i states.size(); i)的写法依赖每次循环重新取size()新增状态会继续被消费这是故意为之不是写错了。4. DFA最小化划分法把状态压到最简4.1 状态膨胀从哪来最小化为什么是刚需子集构造产生的DFA里经常会有两个状态从初态到达后对任意剩余输入的表现完全相同。比如ab|ac子集构造后两个接受状态都没有出边它们就是等价的可以合并成一个。另一个典型来源是手工画DFA时容易画出多余的中间状态或者从NFA机械转换时留下了冗余路径。状态等价的形式化定义是从状态s和t出发输入任意长度的任意字符串接受结果完全一致。最小化的价值不仅是省内存。词法分析器里DFA的状态数直接影响生成表的体积和缓存命中率嵌入式场景下更明显。划分法是最容易实现且可以证明收敛的算法它从“按接受/非接受分组”开始反复用转移目标组来拆分直到分组不再变化。4.2 划分法迭代按转移目标组拆分DFA minimizeDFA(const DFA dfa, int numClasses) { int n static_castint(dfa.trans.size()); std::vectorint group(n); for (int i 0; i n; i) { group[i] dfa.accept[i] ? 0 : 1; } while (true) { std::mapstd::vectorint, int mp; std::vectorint nextGroup(n); for (int s 0; s n; s) { std::vectorint sig; sig.push_back(group[s]); for (int j 0; j numClasses; j) { int t dfa.trans[s][j]; sig.push_back(t -1 ? -1 : group[t]); } auto it mp.find(sig); if (it mp.end()) { int gid static_castint(mp.size()); mp[sig] gid; nextGroup[s] gid; } else { nextGroup[s] it-second; } } if (nextGroup group) break; group.swap(nextGroup); } std::mapint, int remap; for (int g : group) { if (!remap.count(g)) remap[g] static_castint(remap.size()); } std::vectorint compact(n); for (int i 0; i n; i) compact[i] remap[group[i]]; DFA m; int mSize static_castint(remap.size()); m.trans.assign(mSize, std::vectorint(numClasses, -1)); m.accept.assign(mSize, false); for (int s 0; s n; s) { int gs compact[s]; if (dfa.accept[s]) m.accept[gs] true; for (int j 0; j numClasses; j) { int t dfa.trans[s][j]; if (t ! -1) m.trans[gs][j] compact[t]; } } m.start compact[dfa.start]; return m; }签名里包含group[s]等价的两个状态必然属于同一个当前组所以这一项不会阻止正确合并它排除掉“两个状态当前不同组但转移目标恰好组号相同”的偶然一致。迭代终止条件是分组编号完全不变此时每个组内的状态对所有字符的转移目标都落在同一个组里满足等价状态的封闭性。最后一步压缩组号把不连续的编号映射成0到M-1方便重建转移表。4.3 重建最小化后的DFA转移表重建时最需要注意的是绝不能把接受状态和非接受状态合并。初始分组时两者就被分开后续拆分只会越来越细所以这个保证是算法自带的。但重建代码里还要小心-1一个状态对某个字符没有定义转移最小化后依然要保持“转移不存在”的语义而不是顺手连到某个代理状态。上面的代码里t -1时直接跳过trans保持-1这个约定贯穿匹配阶段。验证最小化结果是否正确我通常先做语言等价抽查准备一组测试串分别跑最小化前后的accepts结果必须一致。更严格的做法是随机生成大量串做差分第6章会展开。还有一个容易忽略的点dfa.start在压缩后可能不是0所以m.start要改成compact[dfa.start]别默认成0。5. 避坑指南正则转最小化DFA常见的五个翻车点5.1 空正则和空字符串两个最容易被轻视的输入现象配置一个空模式或者只包含括号的表达式比如()标准正则库能正确匹配空串自己构建的DFA却崩溃或者直接判定不匹配。原因初版实现里没有EPSILON节点。parseCat遇到空连接项时返回了nullptrbuildNFA对空指针解引用崩溃就算没崩DFA的初态不是接受状态空串自然匹配失败。解决解析器里空cat返回new ASTNode{NodeType::EPSILON}Thompson构造里为EPSILON生成“两个状态一条ε边”的片段。匹配函数不要假设输入至少消费一个字符直接判断dfa.accept[dfa.start]是否为真。这个坑在实现“可选前缀”之类的正则时一定会碰上。5.2 负字符类补集边界与字符集全集现象[^a]在过滤含换行的文本时结果不对[^\x00-\x1F]这种控制字符排除模式匹配结果和标准库对不上。原因负字符类实现时按补集展开区间但搞错了边界。比如有人写lo prevHi 1当prevHi 255时1溢出成0或者没有把区间排序合并就求补集导致[z-a]这种错误区间混进去。解决所有字符码点统一用int存0到255闭区间补集前先排序合并。下面的函数可以直接抄std::vectorstd::pairint, int complementRanges( const std::vectorstd::pairint, int ranges, int minC 0, int maxC 255) { auto sorted ranges; std::sort(sorted.begin(), sorted.end()); std::vectorstd::pairint, int result; int cur minC; for (auto [lo, hi] : sorted) { if (cur lo) result.push_back({cur, lo - 1}); cur std::max(cur, hi 1); if (cur maxC) break; } if (cur maxC) result.push_back({cur, maxC}); return result; }参数说明minC0, maxC255是针对字节级匹配的默认值如果将来要按UTF-8语义处理多字节字符这里的“字符”概念要改成“码点区间”别把UTF-8的连续字节切开处理否则中文和Emoji会被拆得面目全非。5.3 死状态的表示-1和显式死状态不能混用现象最小化之后某些输入串的匹配结果和最小化前不一致画出的DFA状态图里某些状态缺少指向死状态的边看起来“少了东西”。原因子集构造用-1表示“无转移”重建最小化DFA时有人习惯给每个状态补上转移到自身的死状态用来“补全”转移表。一旦把死状态当成普通状态参与分组签名里就会出现指向死状态的转移项而另一处用的是-1两边语义不一致合并结果就会变形。解决全流程统一约定——不显式建死状态转移矩阵用-1表示无定义转移匹配函数遇到-1立刻返回false。最小化的签名里也把-1当成一个固定的“桶”不展开成真实状态。匹配函数必须作为唯一语义来源bool accepts(const DFA dfa, const std::string text) { int cur dfa.start; for (unsigned char c : text) { int next dfa.trans[cur][static_castint(c)]; if (next -1) return false; cur next; } return dfa.accept[cur]; }注意这里用的是unsigned char作下标。如果字符表的列数不是256而是字符等价类需要先把字节映射到列号再查表但-1语义不变。5.4 char默认符号性导致的匹配玄学现象[0-9]一切正常换成[\x80-\xFF]永远匹配不到处理中文文本时DFA结果和标准正则库对不上看起来像算法写错了。原因C的char是否带符号由实现定义x86平台大多数默认是signed char。\x80被解释成负值-128存进NFA边里再用char参与比较自然全部错位。另一个隐蔽坑是for (unsigned char c 0; c 255; c)当c 255时再会回绕成0构成死循环。解决字符值统一用unsigned char存储和比较遍历0到255时用int循环。NFA边的lo、hi类型已经是unsigned char解析器里所有字符常量都用static_castunsigned char转换匹配函数里读字节也转一次auto byte static_castunsigned char(text[i]); int next dfa.trans[cur][byte];这个坑在日志二进制流、编码探测、协议解析这类场景里会反复出现属于“看起来是算法问题实际是内存表示问题”的典型。5.5 递归构造深度超限解析和NFA构造的爆栈隐患现象输入一个嵌套上千层的正则比如几百层括号叠加(a|b)*解析器或buildNFA直接段错误调试器里看到栈溢出。原因parseExpr、parseFactor、buildNFA都是递归实现递归深度等于正则嵌套深度。默认栈空间下几千层就会爆而且错误发生在深层递归里不好定位。解决在解析器入口维护depth_计数器超过阈值直接抛异常。上面2.3的parseFactor里已经加了if (depth_ 1000) throw std::runtime_error(regex nested too deep);注意这个depth_必须在所有递归路径上恢复否则后面正常的正则也会被误判。1000这个阈值覆盖绝大多数真实需求能压到这么深的正则通常不是手写的而是某个生成器拼出来的这时候直接报错比默默崩溃好得多。6. 验证与调试技巧对拍测试和DOT可视化算法写完不等于正确我的习惯是两条腿走路随机差分测试加DOT图可视化。差分测试用标准库当参考实现随机生成正则和输入串对比自研DFA和std::regex的匹配结果。生成器只生成自己支持的语法子集避免标准库和自研实现语法差异造成的误报std::string genRegex(std::mt19937 rng, int depth) { if (depth 0) return std::string(1, ab[rng() % 2]); switch (rng() % 5) { case 0: return genRegex(rng, depth - 1) | genRegex(rng, depth - 1); case 1: return genRegex(rng, depth - 1) genRegex(rng, depth - 1); case 2: return ( genRegex(rng, depth - 1) )*; case 3: return a; default: return b; } }对比时统一用std::regex_match它要求整个字符串完整匹配和DFA的语义一致如果误用regex_search会找子串匹配产生大量假反例。随机测试跑到几十万组不会花太长时间能覆盖绝大多数字符类边界、空串路径和STAR的零次分支。DOT可视化则用来在出反例时一眼定位问题。把DFA的状态、接受、转移输出成DOT格式丢进Graphviz生成状态图人眼检查比盯着转移矩阵快得多std::cout digraph DFA {\n; for (int s 0; s (int)dfa.trans.size(); s) { std::cout s [shape (dfa.accept[s] ? doublecircle : circle) ];\n; for (int j 0; j (int)dfa.trans[s].size(); j) if (dfa.trans[s][j] ! -1) std::cout s - dfa.trans[s][j] [label\ j \];\n; } std::cout }\n;我个人最深的一次教训就是在负字符类上栽了跟头算法全对边界全错。从那以后我要求自己每次改动解析或最小化逻辑必须先把随机对拍跑过一遍再谈优化。这个方向值得投入一旦把“正则 → NFA → DFA → 最小化”这条流水线跑通后面再做词法分析器、协议过滤器、甚至是自定义匹配引擎都是同一套骨架在复用。希望帮到你。本文还有配套的精品资源点击获取
