简介：这是一份以C++写就的正则表达式转最小化DFA源码，面向编译原理课程学习者、自动机算法爱好者及需要完成词法分析实验的学生。代码共1000余行，按正则表达式解析、NFA构造、子集构造法转DFA、DFA最小化四个阶段组织；实现中大量使用状态表、集合与栈等结构处理字符集、闭包和状态转移，覆盖了从理论模型到可运行程序的完整链路。资源为单个cpp文件，以rar压缩包提供，体积仅7KB，无多余依赖，便于直接阅读、编译调试或作为课程设计改造基础；读者可对照代码逐步追踪NFA到DFA的状态变化，也能借此复习自动机理论中的关键结论，甚至直接作为编译原理大作业的可运行起点。目前已有191人学习下载，适合需要结合实例动手验证编译原理知识点的人群。

1. 正则表达式转最小化 DFA：C++ 跑通这条链路到底图什么

写词法分析器、做自定义 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 和 accept，start 用 ε 跳过整个片段或进入片段，片段接受态用 ε 回到片段起始或跳到 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::vector<Transition> next; }; static std::vector<NFAState> 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::set<int>; NfaSet epsilonClosure(const NfaSet& s) { NfaSet result = s; std::vector<int> 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::vector<int> minimizeDFA(const DFA& dfa, const std::vector<char>& alphabet) { int n = dfa.n; std::vector<int> group(n); int groupCount = 2; for (int i = 0; i < n; i++) { group[i] = dfa.accept[i] ? 1 : 0; } while (true) { std::vector<int> newGroup(n, -1); int newGroupCount = 0; for (int gid = 0; gid < groupCount; gid++) { std::map<std::vector<int>, int> sigToId; for (int i = 0; i < n; i++) { if (group[i] != gid) continue; std::vector<int> 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::vector<std::map<char, int>> trans; // 每个状态一行，字符到目标状态 std::vector<bool> accept; }; DFA buildDFA(const Fragment& root) { DFA dfa; std::map<NfaSet, int> setToId; std::vector<NfaSet> allSets; NfaSet start = epsilonClosure({root.start}); setToId[start] = 0; allSets.push_back(start); for (size_t id = 0; id < allSets.size(); id++) { std::map<char, 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::map<char, 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::map<char, 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::vector<char> 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::vector<int> 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 [label="a"];的边，接受态节点加双圈属性。拿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]而不是十列。压缩后匹配时按区间二分查找，时间几乎不变，内存指数下降。这套东西写在最小化之后，属于优化阶段，别在前面的正确性验证没通过时就急着做。

这几年我写的每一个自动机工具都遵守一个习惯：每写完一段，先打印状态数，跑固定用例，再往后走。状态数对不上就停下来查，不要攒着问题一起调。这个习惯帮我省了大量排查时间，希望帮到你。

本文还有配套的精品资源，点击获取