★ FEATURED ARTICLE 简介这是一份以C写就的正则表达式转最小化DFA源码面向编译原理课程学习者、自动机算法爱好者及需要完成词法分析实验的学生。代码共1000余行按正则表达式解析、NFA构造、子集构造法转DFA、DFA最小化四个阶段组织实现中大量使用状态表、集合与栈等结构处理字符集、闭包和状态转移覆盖了从理论模型到可运行程序的完整链路。资源为单个cpp文件以rar压缩包提供体积仅7KB无多余依赖便于直接阅读、编译调试或作为课程设计改造基础读者可对照代码逐步追踪NFA到DFA的状态变化也能借此复习自动机理论中的关键结论甚至直接作为编译原理大作业的可运行起点。目前已有191人学习下载适合需要结合实例动手验证编译原理知识点的人群。1. 正则表达式转最小化 DFAC 跑通这条链路到底图什么写词法分析器、做自定义 DSL、或者要给匹配引擎做性能优化时正则表达式转最小化 DFA 是一条绕不过去的路。C 里虽然能直接调 std::regex但 std::regex 是黑匣子实现随标准库走性能不稳定也没法直接读出匹配用的状态表。自己用 C 把「正则表达式 → 语法树 → NFA → DFA → 最小化 DFA」整条链路实现一遍不但能精确控制匹配过程还能拿到一张干净的、可序列化的状态转移表。这篇文章面向要写词法分析器或协议解析器的人从 AST 解析讲到最后的最小化每一段都有能跑的代码和参数选择逻辑。2. 先把正则吃透AST 解析与优先级处理的三个分层2.1 为什么解析正则不能只按字符逐个跑正则表达式描述的是一种正规语言而把字符串变成自动机的前提是先把表达式结构化。只按字符从左到右扫描没法区分a|b*和(a|b)*前者匹配单个 a或者任意个 b后者匹配任意个 a 或 b 组成的串。两种语言的接受集合完全不同。所以第一步不是急着构造自动机而是把正则字符串解析成一棵语法树树的每个节点明确表达「这是一个字符」「这是连接」「这是或」「这是闭包」。这个解析过程和写表达式编译器很像。C 里正则没有统一的标准语法比如 Linux 下常用的 POSIX 风格和 Perl 风格对转义、字符类的处理都有差异。我一般先定一个子集支持|或、隐式连接、*?量词、圆括号、转义、[a-z]字符区间。不支持捕获分组、反向引用因为反向引用描述的不是正规语言根本进不了 DFA。2.2 优先级、括号与转义解析器的三张牌正则表达式的优先级从低到高是|或运算、隐式连接、量词、原子。圆括号用来提升优先级。递归下降解析器正好按照这个次序组织函数层级每一层只处理一个优先级parseAlternation 处理|把左右两个子表达式拼成 Alternate 节点parseConcat 处理隐式连接它不断读入下一个「重复单元」直到遇到)或|或结尾parseRepeat 处理*?这些量词只作用于前一个原子parseAtom 处理括号、字面量、转义和字符类。转义要特别注意。\.应该解析成「字符 .」而不是「任意字符」\\是反斜杠本身\*是星号本身。字符类[a-z]需要单独识别成区间节点否则方括号和连字符都会被当成普通字符处理后面构造出来的自动机一堆莫名奇妙的边。2.3 最小可用的递归下降解析器与参数选择先看 AST 节点定义我用一个节点类型枚举加左右子指针字符类额外存起止字符。enum class NodeType { Char, CharClass, Concat, Alternate, Star, Plus, Option }; struct Node { NodeType type; char ch 0; // Char 节点用 char rangeLo 0; // CharClass 区间起点 char rangeHi 0; // CharClass 区间终点 Node* left nullptr; Node* right nullptr; explicit Node(NodeType t) : type(t) {} ~Node() { delete left; delete right; } };对应的高层结构体存储 AST 节点负责构建语法树。随后是递归下降 Parser 类的实现仅展示核心解析函数构造函数和成员变量见注释class Parser { const std::string s; size_t pos 0; public: explicit Parser(const std::string src) : s(src) {} Node* parse() { Node* n parseAlternation(); return n; } private: Node* parseAlternation() { Node* left parseConcat(); while (pos s.size() s[pos] |) { pos; Node* right parseConcat(); Node* p new Node(NodeType::Alternate); p-left left; p-right right; left p; } return left; } Node* parseConcat() { Node* left parseRepeat(); while (pos s.size() s[pos] ! ) s[pos] ! |) { Node* right parseRepeat(); Node* p new Node(NodeType::Concat); p-left left; p-right right; left p; } return left; } Node* parseRepeat() { Node* atom parseAtom(); while (pos s.size()) { if (s[pos] *) { pos; Node* p new Node(NodeType::Star); p-left atom; atom p; } else if (s[pos] ) { pos; Node* p new Node(NodeType::Plus); p-left atom; atom p; } else if (s[pos] ?) { pos; Node* p new Node(NodeType::Option); p-left atom; atom p; } else break; } return atom; } Node* parseAtom() { if (pos s.size() s[pos] () { pos; Node* n parseAlternation(); if (pos s.size() s[pos] )) pos; return n; } if (pos s.size() s[pos] \\) { pos; char c s[pos]; pos; Node* n new Node(NodeType::Char); n-ch c; return n; } if (pos s.size() s[pos] [) { // 只支持 [a-z] 这类闭区间连字符在中间时按区间处理 pos; char lo s[pos]; pos; if (pos s.size() s[pos] -) { pos; char hi s[pos]; pos; Node* n new Node(NodeType::CharClass); n-rangeLo lo; n-rangeHi hi; if (pos s.size() s[pos] ]) pos; return n; } Node* n new Node(NodeType::Char); n-ch lo; if (pos s.size() s[pos] ]) pos; return n; } char c s[pos]; pos; Node* n new Node(NodeType::Char); n-ch c; return n; } };这段代码的关键在于函数层级正好等于优先级层级。parseAlternation在最外层所以|的优先级最低a|b*会解析成 Alternate(a, Star(b))而不是 Star(Alternate(a, b))。parseConcat在parseAlternation下面一层因此连接运算在|之前完成。parseRepeat只包住一个原子所以ab*是 a 连接 b*不是 (ab)*。转义的实现很简单遇到\就无条件吃掉下一个字符无论它是字母还是符号都作为一个普通字符节点。需要注意这个解析器的参数假设字符集只支持单字符闭区间像[^a]取反、[a-z0-9]多段区间都不支持真实做编译器词法时得补上。另一个参数是内存AST 节点用裸指针 new 出来Parser 持有整棵树构造 NFA 后统一 delete。工程上可以用 unique_ptr 或对象池但教学代码里裸指针最直白。3. Thompson 构造法把 AST 一步步变成 NFA 的工程细节3.1 为什么中间要过 NFA避免直接构造 DFA 的爆炸很多人会问为什么不直接从正则构造 DFA因为直接构造 DFA 需要跟踪「所有可能的匹配路径」本质上就是把子集构造法暗含在结构里写起来极易漏转移边。Thompson 构造法的价值是让 NFA 的状态数随 AST 节点数线性增长每个字符节点引入两个状态每个一元或二元节点引入常数个新状态最终 NFA 状态总数大约是 2 乘以叶子节点数。先得到 NFA再用子集构造法转 DFA逻辑被拆成两段每一步都能单独验证。这也是编译原理教材里普遍采用的路径。这个阶段的状态专门用一个结构体存转移边不直接存二维表因为 NFA 允许同一个状态出发、同一字符走向多个目标而且大量 ε 边需要灵活追加。3.2 五种基本片段的拼接规则Thompson 构造的基本单位是片段 Fragment每个片段记录起始状态和接受状态。每种 AST 节点对应一种拼法字符节点新建 start 和 accept 两个状态start 通过该字符走到 accept连接节点把左片段接受态用 ε 接到右片段起始态或节点新建 start用 ε 分叉到左右片段的起始态左右片段的接受态用 ε 汇合到新 accept星号新建 start 和 acceptstart 用 ε 跳过整个片段或进入片段片段接受态用 ε 回到片段起始或跳到 accept加号和星号类似但 start 必须进入片段不能直接跳过问号和星号类似但片段内部不走循环。字符类节点就特殊一点把它展开为多条并行边从同一个 start 出发每个区间内字符分别连到同一个 accept。3.3 NFA 状态分配与递归构建的 C 实现我用一个全局向量做状态池状态用整数索引引用避免指针在 vector 扩容后失效。ε 边用特殊字符EPS表示这里我用char类型的0标记因为正则输入里正常情况下不会出现\0。static const char EPS 0; struct Transition { char ch; // EPS 表示 epsilon 边 int to; Transition(char c, int t) : ch(c), to(t) {} }; struct NFAState { std::vectorTransition next; }; static std::vectorNFAState statesPool; int newState() { statesPool.emplace_back(); return (int)statesPool.size() - 1; } struct Fragment { int start; int accept; }; Fragment buildNFA(Node* node) { switch (node-type) { case NodeType::Char: { int s newState(); int a newState(); statesPool[s].next.emplace_back(node-ch, a); return {s, a}; } case NodeType::CharClass: { int s newState(); int a newState(); for (char c node-rangeLo; c node-rangeHi; c) { statesPool[s].next.emplace_back(c, a); } return {s, a}; } case NodeType::Concat: { Fragment l buildNFA(node-left); Fragment r buildNFA(node-right); statesPool[l.accept].next.emplace_back(EPS, r.start); return {l.start, r.accept}; } case NodeType::Alternate: { Fragment l buildNFA(node-left); Fragment r buildNFA(node-right); int s newState(); int a newState(); statesPool[s].next.emplace_back(EPS, l.start); statesPool[s].next.emplace_back(EPS, r.start); statesPool[l.accept].next.emplace_back(EPS, a); statesPool[r.accept].next.emplace_back(EPS, a); return {s, a}; } case NodeType::Star: { Fragment inner buildNFA(node-left); int s newState(); int a newState(); statesPool[s].next.emplace_back(EPS, inner.start); statesPool[s].next.emplace_back(EPS, a); statesPool[inner.accept].next.emplace_back(EPS, inner.start); statesPool[inner.accept].next.emplace_back(EPS, a); return {s, a}; } case NodeType::Plus: { Fragment inner buildNFA(node-left); int s newState(); int a newState(); statesPool[s].next.emplace_back(EPS, inner.start); statesPool[inner.accept].next.emplace_back(EPS, inner.start); statesPool[inner.accept].next.emplace_back(EPS, a); return {s, a}; } case NodeType::Option: { Fragment inner buildNFA(node-left); int s newState(); int a newState(); statesPool[s].next.emplace_back(EPS, inner.start); statesPool[s].next.emplace_back(EPS, a); statesPool[inner.accept].next.emplace_back(EPS, a); return {s, a}; } } return {-1, -1}; }递归构建的逻辑不复杂容易看漏的是 Star 的 ε 边方向。Star 的 start 到 accept 的直连边负责「匹配零次」inner.accept 回到 inner.start 的边负责「重复多次」。这段顺序不能乱否则a*会变成只匹配一次 a 或者死循环。另一个参数细节是newState()每调用一次就往全局池里 push 一个空状态状态号从 0 递增最后 Fragment 的 accept 不额外标记因为 DFA 构造时只认最初那个根 Fragment 的 accept 编号。4. NFA 转 DFA 与最小化子集构造和划分法的完整链路4.1 ε-闭包与 move转换 DFA 的两个基本运算NFA 转 DFA 的原理是子集构造DFA 的每个状态对应一组 NFA 状态。两个基本运算是 ε-闭包和 move。ε-闭包求「从一组 NFA 状态出发只沿 ε 边走能到达的所有状态」move 求「从一组状态出发吃掉某个字符后能到达的下一批状态」。move 的结果要再做一次 ε-闭包因为到达新状态后可能还有 ε 转移。using NfaSet std::setint; NfaSet epsilonClosure(const NfaSet s) { NfaSet result s; std::vectorint stack(result.begin(), result.end()); while (!stack.empty()) { int cur stack.back(); stack.pop_back(); for (const auto t : statesPool[cur].next) { if (t.ch EPS !result.count(t.to)) { result.insert(t.to); stack.push_back(t.to); } } } return result; } NfaSet moveSet(const NfaSet s, char c) { NfaSet result; for (int st : s) { for (const auto t : statesPool[st].next) { if (t.ch c) result.insert(t.to); } } return epsilonClosure(result); }闭包运算用栈实现一个状态出栈时把它的所有 ε 后继加入集合并压栈直到栈空。这个算法的时间复杂度是 O(状态数加边数)每个状态最多入栈一次。若用递归实现表达式深的时候容易爆栈所以我平时习惯用显式栈。moveSet 里先收集原始目标再统一做闭包顺序不能反。4.2 不可达状态裁剪先剪枝再最小化子集构造从起始闭包出发用 BFS 逐层扩展天然只会生成可达的 DFA 状态。真正需要裁剪的场景是你从别处导入了一张 DFA 表或者调试最小化结果发现并掉了一堆无关状态。裁剪办法是先标记可达状态保留可达和出边可达的目标其余删除。注意裁剪必须先于最小化划分法的初始分组是「接受态 vs 非接受态」如果不可达状态混在里面最小化会花时间合并那些永远不参与匹配的等价类甚至影响最终分组编号的稳定性。死状态的处理是另一个关键约定。DFA 转移表里某状态遇到某个字符没有出边统一写成 -1也就是进入一个不存在的死状态。最小化时所有 -1 必须映射到同一个假想组否则相同行为的两个状态会因为「一个缺边、一个也有缺边但记法不同」被错误拆分。4.3 划分法最小化用签名分组把等价状态并掉DFA 最小化最直观的算法是划分法。初始把状态分成两组接受态和非接受态。然后反复迭代对每个组内状态计算它的「签名」——按字母表顺序逐个字符看这个状态转移到了哪个组组号序列就是签名。签名相同的状态才允许留在同一个组里否则拆开。直到某一轮分组数量不再变化此时每组内部的状态都是等价的每组保留一个代表即可。std::vectorint minimizeDFA(const DFA dfa, const std::vectorchar alphabet) { int n dfa.n; std::vectorint group(n); int groupCount 2; for (int i 0; i n; i) { group[i] dfa.accept[i] ? 1 : 0; } while (true) { std::vectorint newGroup(n, -1); int newGroupCount 0; for (int gid 0; gid groupCount; gid) { std::mapstd::vectorint, int sigToId; for (int i 0; i n; i) { if (group[i] ! gid) continue; std::vectorint sig; sig.reserve(alphabet.size()); for (char c : alphabet) { auto it dfa.trans[i].find(c); int to (it dfa.trans[i].end()) ? -1 : it-second; sig.push_back(to -1 ? -1 : group[to]); } if (!sigToId.count(sig)) { sigToId[sig] newGroupCount; } newGroup[i] sigToId[sig]; } } if (newGroupCount groupCount) break; group std::move(newGroup); groupCount newGroupCount; } return group; }这个实现的特点是把拆组动作一次性完成遍历每个旧组按签名把组内状态落到不同的新组。终止条件是组数不变。严谨性在于签名里包含了 -1 的组号缺边的状态和跳到死状态的状态在签名上一致符合 DFA 行为的等价判定。复杂度和字母表大小、状态数相关对小规模的词法规则完全够用状态上千时再考虑 Hopcroft 分治优化。4.4 一次跑通全流程的实现骨架把前面几段拼起来主流程如下。假设 Parser 和 NFA 构建已经完成DFA 结构体需要包含状态数、转移行、接受标记。struct DFA { int n 0; std::vectorstd::mapchar, int trans; // 每个状态一行字符到目标状态 std::vectorbool accept; }; DFA buildDFA(const Fragment root) { DFA dfa; std::mapNfaSet, int setToId; std::vectorNfaSet allSets; NfaSet start epsilonClosure({root.start}); setToId[start] 0; allSets.push_back(start); for (size_t id 0; id allSets.size(); id) { std::mapchar, NfaSet rawMove; for (int st : allSets[id]) { for (const auto t : statesPool[st].next) { if (t.ch ! EPS) rawMove[t.ch].insert(t.to); } } std::mapchar, int row; for (const auto kv : rawMove) { NfaSet target epsilonClosure(kv.second); if (!setToId.count(target)) { setToId[target] (int)allSets.size(); allSets.push_back(target); } row[kv.first] setToId[target]; } dfa.trans.push_back(row); bool isAccept false; for (int st : allSets[id]) { if (st root.accept) isAccept true; } dfa.accept.push_back(isAccept); } dfa.n (int)allSets.size(); return dfa; }buildDFA 里最关键的一步是rawMove先收集原始目标集再统一做闭包。如果每来一条边就做一次闭包同一个字符的多条出边会各自形成子集出现重复的 DFA 状态状态数虚高。dfa.trans的行用std::mapchar, int而不是固定长度数组是为了避免按 256 个 ASCII 码全展开。真实场景如果遇不到某个字符行里就没有这一列匹配时用 find 查找即可。全流程调用长这样int main() { std::string pattern ab|bc*; Parser parser(pattern); Node* ast parser.parse(); Fragment root buildNFA(ast); DFA dfa buildDFA(root); std::vectorchar alphabet; for (const auto row : dfa.trans) for (const auto kv : row) alphabet.push_back(kv.first); std::sort(alphabet.begin(), alphabet.end()); alphabet.erase(std::unique(alphabet.begin(), alphabet.end()), alphabet.end()); std::vectorint minGroup minimizeDFA(dfa, alphabet); int minStates 0; for (int g : minGroup) minStates std::max(minStates, g 1); std::cout minimal states: minStates std::endl; delete ast; return 0; }字母表的收集用了排序去重保证每个字符在签名里只出现一次顺序稳定。这里我特意在最小化前打印了一次状态数和分组数这是调试时最便宜的验证手段如果最小化后状态数比手工推算的少大概率是等价判断写宽了如果多了大概率是有的转移没走到落在了死状态。5. 避坑五个高频翻车点与排查习惯5.1 解析与构造阶段的三次翻车第一个翻车点出在量词作用范围。现象输入a|b*测试字符串ab竟然匹配成功或者反过来b*明明只能匹配 b却匹配了 a。原因有人在 parseRepeat 里遇到量词后直接回调 parseAlternation导致*把整个a|b包住了等价于(a|b)*。解决严格保持函数层级parseRepeat 只对 parseAtom 的返回值施加量词。如果一个量词后面跟着括号那是 parseAtom 里括号分支先去解析括号内部量词包住的是括号解析的结果而不是反向吞掉外层表达式。第二个翻车点出在 ε-闭包的收敛性。现象DFA 转移表里总缺边一个子集明明能走到别的状态表里却没有对应转移。原因闭包只扫描了一层 ε 边就返回。NFA 里 ε 边经常串成长链比如(ab)*的 a 片段接受态到 b 片段起始、星号内环到外环多层 ε 边需要迭代或显式栈处理。解决闭包用栈循环到栈空或者在结果集合不再变大时停止。血的教训是别在闭包里只做一层 for 循环就返回那是错的最经典的一种写法。第三个翻车点出在字符类和转义。现象[a-z]被当成了四个普通字符\.被当成「任意字符」通配符。原因解析时没识别方括号边界转义字符里的反斜杠被丢弃后.按正则语义变成了统配。解决parseAtom 里单独写[分支区间解析存入 CharClass 节点转义时无条件吃掉下一个字符作为字面量。字符类里如果出现\d这类预设集合要提前决定是展开成 0-9 还是单独建一个节点我一般建议展开因为 NFA 构造阶段最简单。5.2 转换与最小化阶段的两个隐蔽问题第四个翻车点藏在最小化的签名计算里。现象最小化后状态数和最小化前几乎一样明显应该合并的状态没被合并。原因某个状态在字母表某个字符下没有出边代码里直接跳过导致签名里少一个元素另一个状态有出边但走向死状态两个行为等价的状态签名对不上。解决所有缺失转移统一记成 -1并且签名计算时必须把 -1 也放进去。这样缺边的状态和走到死状态的状态在签名上完全一致才能被正确合并。第五个翻车点和大字符集有关。现象处理[\u4e00-\u9fff]这类区间时NFA 构造给每个码元都建一条边DFA 状态数爆炸内存百分比飙升。原因char 只有 256 个取值Unicode 码点动辄几万个把每个码元当作独立一列既不现实也没必要。解决先压缩字符区间收集所有转移边界把连续且目标相同的字符合并成一列NFA 构造时也不逐码元建边而是给区间建边转 DFA 时同一区间的转移统一处理。对一个中文字符集转移列数能从几万压到个位数这是真正上了生产环境才需要的东西。6. 进阶把 DFA 画出来验证再谈最长匹配与字符区间压缩6.1 用 Graphviz 输出 DFA 图眼睛先过一遍写完最小化逻辑第一件事不是急着做匹配器而是把 DFA 导成 dot 格式用 Graphviz 渲染出来肉眼检查。导出的代码很简单遍历每个 DFA 状态和它的转移行输出形如s0 - s1 [labela];的边接受态节点加双圈属性。拿a|b*来说你应该看到两个状态起始状态 0通过 a 到接受态通过 b 回到自身。如果画出来多了状态或者出现 u 形边最小化多半有 bug。我习惯把正则和状态数一起写在图里保存成 PNG 后归档方便以后对照。匹配器本体建议单独写一个函数不依赖最小化代码。输入一行文本和一个初始状态按字符查转移表查不到就返回失败。走到接受态且字符耗尽时返回成功。这一步能快速验证最小化正确性跑一组合法串和非法串和手写预期的结果逐条比对。6.2 词法分析的正确姿势最长匹配与字符区间压缩匹配器只要「能接受」就行但词法分析器要的是最长的那个接受串。比如关键字if和标识符规则都匹配if词法分析必须优先报if关键字遇到iffy时必须匹配整个iffy作为标识符不能停在if上。正确写法是在扫描过程中记录最近一次到达接受态的位置只有遇到无法转移的字符才回退到最近接受位置。这个习惯我每次写词法分析都会用简单可靠。size_t lastAcceptPos 0; int cur dfa.startState; for (size_t i 0; i text.size(); i) { auto it dfa.trans[cur].find(text[i]); if (it dfa.trans[cur].end()) break; cur it-second; if (dfa.accept[cur]) lastAcceptPos i 1; } // text[0..lastAcceptPos) 才是真正匹配到的词素这段代码的精髓在于匹配失败时不是立刻报错而是用 lastAcceptPos 回退。很多新手翻车在「遇到接受态就立刻返回」词法分析结果永远是第一个匹配而不是最长匹配。字符区间压缩是最后一个技巧。转移表按字符建列遇到大字母表会浪费大量内存。做法是收集所有转移里出现过的字符边界对相邻字符且目标相同的区间合并。比如数字0-9都转移到同一状态只需要记录区间[0,9]而不是十列。压缩后匹配时按区间二分查找时间几乎不变内存指数下降。这套东西写在最小化之后属于优化阶段别在前面的正确性验证没通过时就急着做。这几年我写的每一个自动机工具都遵守一个习惯每写完一段先打印状态数跑固定用例再往后走。状态数对不上就停下来查不要攒着问题一起调。这个习惯帮我省了大量排查时间希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
