VC++实现正则表达式到NFA转换：Thompson构造法工程实践

1. 项目概述从正则表达式到有穷自动机的工程实践在文本处理、编译器前端设计乃至安全扫描等领域正则表达式Regular Expression, Regex都是我们手中一把锋利的瑞士军刀。但你是否想过当你写下a(b|c)*d这样一段模式时计算机底层是如何一步步理解并执行匹配的这背后正是“有穷自动机”Finite Automaton在默默工作。今天我们不谈枯燥的理论而是聚焦于一个具体的工程实现如何在经典的 VC 开发环境中亲手搭建一座从正则表达式字符串描述到有穷自动机内存数据结构的桥梁。这个项目的核心价值在于“解析”与“实现”。它不仅仅是理解“正则引擎是如何工作的”这一理论问题更是解决“如果我需要为一个特定场景定制匹配规则甚至优化匹配性能我该如何从最底层构建自己的工具”这一实践问题。无论是希望深入理解编译原理的同学还是需要在C项目中嵌入高性能、可定制的文本匹配模块的开发者这个实例都能提供一条清晰的路径。我们将使用 VC 作为实现平台一方面是因为其成熟的 IDE 和调试环境对复杂数据结构的构建非常友好另一方面在 Windows 平台进行原生开发时这套技术栈具有直接的实用价值。2. 核心原理与设计思路拆解2.1 为什么需要有穷自动机正则表达式对人类来说是直观的文本模式但对计算机而言它需要被转化为一系列确定的状态和转移条件才能执行。有穷自动机就是这样一个计算模型。它就像一个迷宫里面有若干个房间状态房间之间有门状态转移门上贴着通行条件输入字符。我们从入口初态开始根据输入的字符串一个字符一个字符地选择门走如果能走到指定的出口终态就说明字符串匹配成功。有穷自动机主要分为两类不确定的有穷自动机NFA和确定的有穷自动机DFA。NFA 允许从一个状态在接收同一输入字符时转移到多个可能的下一个状态不确定性甚至可以不消耗输入字符就发生转移ε-转移。DFA 则要求每个状态对每个可能的输入字符有且只有一条转移路径。NFA 更贴近正则表达式的直观结构易于从正则表达式构造而 DFA 的运行效率更高因为每一步都没有选择困难症。因此一个完整的正则引擎通常的构造路径是正则表达式 → NFA → DFA → 最小化 DFA → 最终匹配程序。我们的实例将重点实现前两步即正则表达式到 NFA 的构造。2.2 我们的技术选型VC 与自建数据结构选择 VC这里主要指使用 Visual Studio 进行 C 开发而非其他高级语言或现成库如std::regex来实现有几层考量学习深度使用 C 手动管理内存和构建图结构NFA/DFA本质是图能让你透彻理解自动机中状态、转移边等核心概念的内存表示和生命周期这是使用高级封装库无法获得的体验。控制力与性能自己实现的引擎你可以精确控制匹配算法如回溯或状态机驱动、内存布局针对特定模式进行优化这在追求极致性能的场景如网络入侵检测、实时日志分析中是关键。可移植性与依赖最终生成的是一套纯 C 代码不依赖特定的运行时库除了 C 标准库可以轻松集成到各种项目中。在数据结构设计上核心是状态State和转移边Edge。一个简单的设计如下State 类包含一个唯一ID一个标记是否为接受状态终态的布尔量以及一个转移边的列表。Edge 类包含一个指向目标状态的指针以及一个转移条件。这个条件可以是一个具体的字符Char一个字符范围CharRange或者是特殊的 ε代表空转移。我们将采用“Thompson 构造法”作为从正则表达式到 NFA 的算法。它的核心思想是递归将复杂的正则表达式视为由基本单元单字符、连接、选择、闭包通过运算符组合而成并为每个基本单元构造一个小的 NFA 片段然后按照运算符的语义将这些小片段像搭积木一样组合成最终的 NFA。3. 核心数据结构与算法实现3.1 定义自动机核心类我们首先在头文件中定义核心的数据结构。为了清晰和管理方便我们将所有内容放在一个命名空间内比如RegexToFA。// RegexToFA.h #pragma once #include memory #include vector #include set #include variant namespace RegexToFA { // 转移条件类型单字符、字符范围、空转移(epsilon) using CharType char; // 简单起见用 char struct CharRange { CharType start; CharType end; }; struct Epsilon {}; using TransitionCondition std::variantCharType, CharRange, Epsilon; // 前向声明 class State; // 转移边 struct Edge { std::shared_ptrState target; // 使用智能指针管理状态生命周期 TransitionCondition condition; }; // 状态 class State { public: int id; bool isAccepting; std::vectorEdge outgoingEdges; State(int stateId, bool accepting false) : id(stateId), isAccepting(accepting) {} void addEdge(std::shared_ptrState target, TransitionCondition cond) { outgoingEdges.push_back({std::move(target), cond}); } }; // 有穷自动机这里特指NFA class FiniteAutomaton { public: std::shared_ptrState startState; std::shared_ptrState acceptState; // 对于Thompson构造法我们通常维护一个唯一的接受状态 FiniteAutomaton(std::shared_ptrState start, std::shared_ptrState accept) : startState(std::move(start)), acceptState(std::move(accept)) {} }; } // namespace RegexToFA这里有几个关键点使用了std::variant来优雅地表示多种转移条件避免了复杂的类继承体系。使用std::shared_ptrState来管理状态对象的所有权。因为一个状态可能被多个转移边指向如图中的汇合点共享所有权是合适的选择。FiniteAutomaton类目前只保存了开始状态和接受状态的引用实际上整个 NFA 是通过状态之间的指针链接起来的图。3.2 实现 Thompson 构造法Thompson 构造法为四种基本操作提供构造规则基本字符c构造两个状态通过一条标有字符 ‘c’ 的边连接。连接AB将自动机 A 的接受状态和自动机 B 的开始状态通过 ε 边连接。选择A|B创建新的开始和接受状态从新开始状态用 ε 边连接到 A 和 B 的开始状态从 A 和 B 的接受状态用 ε 边连接到新接受状态。闭包A*创建新的开始和接受状态。添加四条 ε 边新开始→A开始 A接受→新接受 新开始→新接受零次匹配 A接受→A开始循环。我们在RegexToFA.cpp中实现一个ThompsonConstructor类。// RegexToFA.cpp #include RegexToFA.h #include stack #include cassert namespace RegexToFA { class ThompsonConstructor { int nextStateId 0; public: // 辅助函数生成新状态 std::shared_ptrState createState(bool accepting false) { return std::make_sharedState(nextStateId, accepting); } // 1. 构造基本字符 FiniteAutomaton constructFromChar(CharType c) { auto start createState(); auto accept createState(true); start-addEdge(accept, c); return {start, accept}; } // 2. 构造连接 A · B FiniteAutomaton constructConcatenation(FiniteAutomaton A, FiniteAutomaton B) { // 将A的接受状态与B的开始状态用ε边连接并取消A接受状态的接受属性 A.acceptState-isAccepting false; A.acceptState-addEdge(B.startState, Epsilon{}); // 新的接受状态是B的接受状态 return {A.startState, B.acceptState}; } // 3. 构造选择 A | B FiniteAutomaton constructAlternation(FiniteAutomaton A, FiniteAutomaton B) { auto newStart createState(); auto newAccept createState(true); // 原接受状态不再是接受状态 A.acceptState-isAccepting false; B.acceptState-isAccepting false; // 添加四条ε边 newStart-addEdge(A.startState, Epsilon{}); newStart-addEdge(B.startState, Epsilon{}); A.acceptState-addEdge(newAccept, Epsilon{}); B.acceptState-addEdge(newAccept, Epsilon{}); return {newStart, newAccept}; } // 4. 构造闭包 A* FiniteAutomaton constructClosure(FiniteAutomaton A) { auto newStart createState(); auto newAccept createState(true); A.acceptState-isAccepting false; // 添加四条ε边 newStart-addEdge(A.startState, Epsilon{}); // 进入A newStart-addEdge(newAccept, Epsilon{}); // 跳过A零次 A.acceptState-addEdge(newAccept, Epsilon{}); // A结束 A.acceptState-addEdge(A.startState, Epsilon{}); // A循环 return {newStart, newAccept}; } }; } // namespace RegexToFA注意这里的实现为了清晰直接修改了输入参数FiniteAutomaton对象内部状态的属性如isAccepting。在实际更完整的实现中你可能需要更谨慎地处理状态复用和拷贝问题或者采用函数式风格返回全新的自动机。这里我们假设构造过程是顺序的且每个基本单元都是新创建的。3.3 正则表达式语法解析与驱动有了基础构造块我们需要一个解析器Parser来读取正则表达式字符串如a(b|c)*d并根据运算符优先级闭包 连接 选择将其转化为一系列构造操作。这通常涉及将中缀表达式转换为后缀表达式逆波兰表示法或者使用递归下降解析。这里我们实现一个简化的、支持括号、|选择、*闭包和隐式连接并置的递归下降解析器作为驱动。我们增加一个constructFromRegex的入口函数。// 在 RegexToFA.h 中增加声明 FiniteAutomaton constructFromRegex(const std::string regexStr); // 在 RegexToFA.cpp 中实现 namespace { // 辅助解析类封装 ThompsonConstructor 和字符串迭代 class RegexParser { ThompsonConstructor constructor; std::string::const_iterator pos; std::string::const_iterator end; // 解析原子项字符、括号表达式 FiniteAutomaton parseAtom() { if (pos end) { throw std::runtime_error(Unexpected end of regex); } char c *pos; if (c () { pos; // 跳过 ( auto autoM parseAlternation(); // 解析括号内的表达式最高级是选择 if (pos end || *pos ! )) { throw std::runtime_error(Missing )); } pos; // 跳过 ) return autoM; } else if (c \\) { // 简单转义只处理下一个字符 pos; if (pos end) throw std::runtime_error(Escape at end of string); c *pos; return constructor.constructFromChar(c); } else if (c | || c ) || c *) { // 这些字符在原子项中不合法但闭包处理会在上层处理 throw std::runtime_error(std::string(Unexpected character: ) c); } else { // 普通字符 pos; return constructor.constructFromChar(c); } } // 解析闭包原子项后面可能跟着 * FiniteAutomaton parseClosure() { auto autoM parseAtom(); while (pos ! end *pos *) { pos; // 跳过 * autoM constructor.constructClosure(std::move(autoM)); } return autoM; } // 解析连接由一系列闭包项连接而成 FiniteAutomaton parseConcatenation() { // 至少解析一个项 auto autoM parseClosure(); // 继续解析后续的项直到遇到选择符或结尾 while (pos ! end *pos ! | *pos ! )) { auto nextAutoM parseClosure(); autoM constructor.constructConcatenation(std::move(autoM), std::move(nextAutoM)); } return autoM; } // 解析选择最高优先级由一系列连接项用 | 连接 FiniteAutomaton parseAlternation() { auto autoM parseConcatenation(); while (pos ! end *pos |) { pos; // 跳过 | auto rightAutoM parseConcatenation(); autoM constructor.constructAlternation(std::move(autoM), std::move(rightAutoM)); } return autoM; } public: RegexParser(const std::string str) : pos(str.begin()), end(str.end()) {} FiniteAutomaton parse() { return parseAlternation(); // 表达式开始于选择层级 } }; } // namespace namespace RegexToFA { FiniteAutomaton constructFromRegex(const std::string regexStr) { RegexParser parser(regexStr); return parser.parse(); } } // namespace RegexToFA这个解析器虽然简单但清晰地展示了递归下降的思想parseAlternation调用parseConcatenationparseConcatenation调用parseClosureparseClosure调用parseAtom形成了一个从低到高的优先级链条。隐式连接是通过在parseConcatenation中循环调用parseClosure来实现的。4. 可视化与调试将 NFA 打印为 DOT 语言构建出的 NFA 是一个复杂的内存图结构仅通过调试器查看指针很不直观。一个极佳的调试方法是将其输出为 Graphviz DOT 语言格式然后生成图片。我们在FiniteAutomaton类中添加一个方法。// 在 FiniteAutomaton 类声明中添加 std::string toDOT() const; // 实现 std::string FiniteAutomaton::toDOT() const { std::ostringstream oss; oss digraph NFA {\n; oss rankdirLR;\n; // 从左到右布局 oss node [shape circle];\n; std::setint visitedStates; std::queuestd::shared_ptrState q; q.push(startState); while (!q.empty()) { auto state q.front(); q.pop(); if (visitedStates.count(state-id)) continue; visitedStates.insert(state-id); // 节点形状接受状态为双圈 if (state-isAccepting) { oss state-id [shape doublecircle];\n; } else { oss state-id [shape circle];\n; } for (const auto edge : state-outgoingEdges) { auto target edge.target; std::string label; std::visit([label](auto arg) { using T std::decay_tdecltype(arg); if constexpr (std::is_same_vT, CharType) { label std::string(1, arg); // 对特殊字符进行转义方便DOT显示 if (arg \) label \\\; else if (arg \\) label \\\\; } else if constexpr (std::is_same_vT, CharRange) { label std::string([) arg.start - arg.end ]; } else if constexpr (std::is_same_vT, Epsilon) { label ε; } }, edge.condition); oss state-id - target-id [label\ label \];\n; if (!visitedStates.count(target-id)) { q.push(target); } } } oss }\n; return oss.str(); }将输出的字符串保存为.dot文件使用 Graphviz 的dot命令如dot -Tpng nfa.dot -o nfa.png即可生成直观的状态转移图这是验证构造是否正确的最有力工具。5. 实例运行与效果验证现在我们编写一个简单的main函数来测试整个流程。// main.cpp #include RegexToFA.h #include iostream #include fstream int main() { try { std::string regex; std::cout Enter a simple regex (support (), |, *, concat, e.g., a(b|c)*d): ; std::getline(std::cin, regex); auto nfa RegexToFA::constructFromRegex(regex); std::cout NFA constructed successfully!\n; std::cout Start State ID: nfa.startState-id std::endl; std::cout Accept State ID: nfa.acceptState-id std::endl; // 输出DOT格式 std::string dotStr nfa.toDOT(); std::ofstream dotFile(nfa.dot); dotFile dotStr; dotFile.close(); std::cout DOT file saved as nfa.dot. Use dot -Tpng nfa.dot -o nfa.png to visualize.\n; } catch (const std::exception e) { std::cerr Error: e.what() std::endl; return 1; } return 0; }测试示例 输入正则表达式a(b|c)*d程序运行后会生成nfa.dot文件。使用 Graphviz 渲染后你将得到一张清晰的 NFA 状态图。你可以看到从开始状态出发经过字符 ‘a’进入一个复杂的子图来处理(b|c)*最后通过字符 ‘d’ 到达接受状态。图中的 ε 边清晰地展示了 Thompson 构造法如何组合各个部分。5.1 常见问题与排查技巧实录在实际编码和测试过程中你几乎一定会遇到以下几个典型问题问题1内存访问冲突或泄漏现象程序在运行时崩溃Access Violation或退出后内存泄漏检测工具报警。原因NFA 是一个图状态之间循环引用非常普遍例如闭包构造中的循环 ε 边。如果使用原始指针需要极其复杂的手动生命周期管理即使使用shared_ptr循环引用也会导致内存泄漏因为引用计数无法归零。排查与解决使用弱指针打破循环对于已知可能形成循环的边如闭包中“接受状态→开始状态”的边可以考虑使用std::weak_ptr。但在自动机构造过程中判断哪些边会形成循环并不简单。更实用的方案将自动机视为整体管理。不要孤立地管理每个State。可以创建一个AutomatonBuilder或NFA类内部使用std::vectorstd::unique_ptrState集中管理所有状态的生命周期。转移边只存储状态的索引int或原始指针State*这些指针的生命周期由外部的vector保证。这是工业级编译器如LLVM中常见的做法它避免了智能指针在复杂图结构中的开销和循环引用问题。问题2解析复杂正则表达式时失败或结果错误现象对于a|b*c这样的表达式构造出的 NFA 逻辑不对。原因运算符优先级处理错误。正则表达式中闭包*优先级最高其次是连接隐式并置最后是选择|。我们的递归下降解析器通过函数调用层级parseAlternation - parseConcatenation - parseClosure - parseAtom天然实现了优先级。问题往往出在“连接”的识别上。排查技巧添加详细日志在每个parseXXX函数入口和退出时打印当前解析的字符位置和即将构造的内容。这能帮你看清解析器的“思考过程”。测试基础单元单独测试constructFromChar然后测试parseAtom对单个字符和括号的解析再逐步测试连接、选择、闭包。可视化对比对于有疑问的正则表达式手动绘制或查找标准的 Thompson NFA 图与你程序生成的 DOT 图进行对比差异点就是 bug 所在。问题3生成的DOT图无法渲染或布局混乱现象dot命令报错或生成的图片重叠严重。原因DOT 语言格式错误或节点/边属性设置不当。解决检查特殊字符转义我们已经在toDOT函数中对双引号和反斜杠进行了转义。但如果正则表达式包含\n,\t等需要更完善的转义逻辑。一个简单的方法是对于非打印字符用其ASCII码表示如label\\\n\。简化图形对于复杂的 NFA可以尝试在 DOT 文件中使用rankdirTB从上到下布局或者为关键状态子图添加subgraph和ranksame等布局提示。使用其他可视化工具如果 Graphviz 的dot布局不理想可以尝试neato或fdp等不同的布局引擎。问题4如何扩展以支持更多语法如,?,[a-z]扩展(一次或多次)可以转化为AA*即先构造 A 的自动机再构造 A 的闭包最后连接两者。也可以在constructClosure旁边实现一个constructPlus函数其逻辑与闭包类似只是不添加“从新开始状态直接到新接受状态”的 ε 边即不允许零次。扩展?(零次或一次)可以转化为(A|ε)即 A 和空串的选择。空串的自动机就是开始状态直接通过 ε 边连接到接受状态。扩展字符集[a-z]在parseAtom中识别[然后解析字符范围调用一个新的构造函数如constructFromRange生成一个状态其转移边条件为CharRange{a, z}。扩展转义字符在parseAtom的转义分支\中增加对\d,\w,\s等预定义字符集的处理将它们映射到对应的CharRange或一组Char条件。这个项目从理论到实践的桥梁就此搭建完成。它不仅仅是一个解析器更是一个理解计算模型和编译技术的窗口。你可以在此基础上继续实现 NFA 到 DFA 的转换子集构造法DFA 的最小化Hopcroft 算法最终得到一个可以高效匹配字符串的完整引擎。当你看到自己写的引擎成功匹配复杂模式时那种对底层原理的掌控感是调用任何现成 API 都无法比拟的。