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）来实现，有几层考量：

1. 学习深度：使用 C++ 手动管理内存和构建图结构（NFA/DFA本质是图），能让你透彻理解自动机中状态、转移边等核心概念的内存表示和生命周期，这是使用高级封装库无法获得的体验。
2. 控制力与性能：自己实现的引擎，你可以精确控制匹配算法（如回溯或状态机驱动）、内存布局，针对特定模式进行优化，这在追求极致性能的场景（如网络入侵检测、实时日志分析）中是关键。
3. 可移植性与依赖：最终生成的是一套纯 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::variant<CharType, CharRange, Epsilon>; // 前向声明 class State; // 转移边 struct Edge { std::shared_ptr<State> target; // 使用智能指针管理状态生命周期 TransitionCondition condition; }; // 状态 class State { public: int id; bool isAccepting; std::vector<Edge> outgoingEdges; State(int stateId, bool accepting = false) : id(stateId), isAccepting(accepting) {} void addEdge(std::shared_ptr<State> target, TransitionCondition cond) { outgoingEdges.push_back({std::move(target), cond}); } }; // 有穷自动机（这里特指NFA） class FiniteAutomaton { public: std::shared_ptr<State> startState; std::shared_ptr<State> acceptState; // 对于Thompson构造法，我们通常维护一个唯一的接受状态 FiniteAutomaton(std::shared_ptr<State> start, std::shared_ptr<State> accept) : startState(std::move(start)), acceptState(std::move(accept)) {} }; } // namespace RegexToFA

这里有几个关键点：

• 使用了std::variant来优雅地表示多种转移条件，避免了复杂的类继承体系。
• 使用std::shared_ptr<State>来管理状态对象的所有权。因为一个状态可能被多个转移边指向（如图中的汇合点），共享所有权是合适的选择。
• FiniteAutomaton类目前只保存了开始状态和接受状态的引用，实际上整个 NFA 是通过状态之间的指针链接起来的图。

3.2 实现 Thompson 构造法

Thompson 构造法为四种基本操作提供构造规则：

1. 基本字符（c）：构造两个状态，通过一条标有字符 ‘c’ 的边连接。
2. 连接（AB）：将自动机 A 的接受状态和自动机 B 的开始状态通过 ε 边连接。
3. 选择（A|B）：创建新的开始和接受状态，从新开始状态用 ε 边连接到 A 和 B 的开始状态；从 A 和 B 的接受状态用 ε 边连接到新接受状态。
4. 闭包（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_ptr<State> createState(bool accepting = false) { return std::make_shared<State>(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调用parseConcatenation，parseConcatenation调用parseClosure，parseClosure调用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 << " rankdir=LR;\n"; // 从左到右布局 oss << " node [shape = circle];\n"; std::set<int> visitedStates; std::queue<std::shared_ptr<State>> 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_t<decltype(arg)>; if constexpr (std::is_same_v<T, CharType>) { label = std::string(1, arg); // 对特殊字符进行转义，方便DOT显示 if (arg == '\"') label = "\\\""; else if (arg == '\\') label = "\\\\"; } else if constexpr (std::is_same_v<T, CharRange>) { label = std::string("[") + arg.start + "-" + arg.end + "]"; } else if constexpr (std::is_same_v<T, 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，循环引用也会导致内存泄漏，因为引用计数无法归零。
• 排查与解决：
  1. 使用弱指针打破循环：对于已知可能形成循环的边（如闭包中“接受状态→开始状态”的边），可以考虑使用std::weak_ptr。但在自动机构造过程中，判断哪些边会形成循环并不简单。
  2. 更实用的方案：将自动机视为整体管理。不要孤立地管理每个State。可以创建一个AutomatonBuilder或NFA类，内部使用std::vector<std::unique_ptr<State>>集中管理所有状态的生命周期。转移边只存储状态的索引（int）或原始指针（State*），这些指针的生命周期由外部的vector保证。这是工业级编译器（如LLVM）中常见的做法，它避免了智能指针在复杂图结构中的开销和循环引用问题。

问题2：解析复杂正则表达式时失败或结果错误

• 现象：对于a|b*c这样的表达式，构造出的 NFA 逻辑不对。
• 原因：运算符优先级处理错误。正则表达式中，闭包（*）优先级最高，其次是连接（隐式并置），最后是选择（|）。我们的递归下降解析器通过函数调用层级（parseAlternation -> parseConcatenation -> parseClosure -> parseAtom）天然实现了优先级。问题往往出在“连接”的识别上。
• 排查技巧：
  1. 添加详细日志：在每个parseXXX函数入口和退出时，打印当前解析的字符位置和即将构造的内容。这能帮你看清解析器的“思考过程”。
  2. 测试基础单元：单独测试constructFromChar，然后测试parseAtom对单个字符和括号的解析，再逐步测试连接、选择、闭包。
  3. 可视化对比：对于有疑问的正则表达式，手动绘制或查找标准的 Thompson NFA 图，与你程序生成的 DOT 图进行对比，差异点就是 bug 所在。

问题3：生成的DOT图无法渲染或布局混乱

• 现象：dot命令报错，或生成的图片重叠严重。
• 原因：DOT 语言格式错误或节点/边属性设置不当。
• 解决：
  1. 检查特殊字符转义：我们已经在toDOT函数中对双引号和反斜杠进行了转义。但如果正则表达式包含\n,\t等，需要更完善的转义逻辑。一个简单的方法是，对于非打印字符，用其ASCII码表示，如label=\"\\n\"。
  2. 简化图形：对于复杂的 NFA，可以尝试在 DOT 文件中使用rankdir=TB（从上到下布局），或者为关键状态子图添加subgraph和rank=same等布局提示。
  3. 使用其他可视化工具：如果 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 都无法比拟的。