35、C++项目实战：正则表达式引擎

正则表达式，说白了就是一套描述字符串模式的规则。很多初学者觉得它很神秘，好像能自动理解“邮箱格式”、“电话号码”这些概念。其实底层没那么玄乎——就是一个状态机在跑。

我个人习惯把正则引擎分成两类：NFA（非确定有限自动机）和DFA（确定有限自动机）。今天我们要手撸的，是一个简化版的NFA引擎。为什么选NFA？因为它更容易支持回溯、捕获组这些高级特性。我在项目中遇到过几次，用DFA做词法分析时，想加个反向引用，结果发现得重写整个引擎……嗯，从那以后我就对NFA情有独钟了。

核心架构：从字符串到状态机

一个正则引擎的工作流程，其实就三步：

  1. 解析：把正则字符串变成抽象语法树（AST）
  2. 编译：把AST转换成NFA状态图
  3. 执行：用输入字符串去跑这个状态图

你想想看，这跟编译器的前端是不是很像？词法分析、语法分析、代码生成。只不过我们生成的不是机器码，而是一张“状态跳转表”。

核心要点：正则引擎的本质，就是“模式 → 状态机 → 匹配”的流水线。理解了这个，你就抓住了90%的脉络。

正则引擎核心流程 步骤1：解析 正则字符串 → AST 步骤2：编译 AST → NFA状态图 步骤3：执行 输入 → 状态跳转 → 匹配 输入: "abc123" 模式: "[a-z]+\\d+" 输出: 匹配结果 & 捕获组

第一步：解析器——把字符串变成树

解析器要处理的东西其实不多。最基本的元素就这几个：

  • 字面量字符：比如 'a'、'b'、'1'，直接匹配自身
  • 元字符：'.' 匹配任意字符，'*' 重复零次或多次，'+' 重复一次或多次
  • 分组：用 '(' 和 ')' 包裹的子表达式
  • 字符类：比如 '[a-z]' 匹配小写字母

我建议用递归下降解析法。为什么？因为正则的语法结构天然就是递归的——分组里可以嵌套分组，就像括号表达式一样。我曾经试过用栈来手写，结果处理嵌套时把自己绕进去了……后来老老实实换了递归，代码反而更清晰。

// 简化的AST节点定义
struct RegexNode {
    enum Type { LITERAL, DOT, STAR, PLUS, GROUP, CHAR_CLASS };
    Type type;
    char ch;                // 字面量字符
    char range_start;       // 字符类起始
    char range_end;         // 字符类结束
    std::vector<RegexNode> children;  // 子节点（用于分组）
};

小技巧：解析时遇到 '\\' 转义符，记得把下一个字符当作字面量处理。比如 '\\d' 要解析成“数字”节点，而不是字母'd'。这个坑我踩过好几次。

第二步：编译器——把树变成状态图

NFA的核心思想是：每个节点对应一个状态，状态之间通过“边”连接。边上有“消耗字符”的条件，或者干脆是ε（空）边——不消耗字符就能跳转。

举个例子，模式 "ab" 的NFA长这样：

状态0 --'a'--> 状态1 --'b'--> 状态2（接受态）

模式 "a|b" 呢？就需要分叉了：

        --'a'--> 状态2
状态0 <           > 状态3（接受态）
        --'b'--> 状态4

这里状态0到状态2、状态0到状态4之间，其实是通过ε边连接的。说白了，ε边就是“免费传送门”，让你不花任何代价就能跳到另一个分支。

编译的核心算法：Thompson构造法。它用递归的方式，把每个AST节点转换成一小段NFA片段，然后用ε边把它们拼起来。这个方法简单、正确、容易实现。

// NFA状态定义
struct NFAState {
    int id;
    std::map<char, std::vector<int>> transitions;  // 字符 → 目标状态列表
    std::vector<int> epsilon_transitions;           // ε边
    bool is_accept = false;                         // 是否为接受态
};

// 编译AST到NFA（伪代码）
NFAState compile(const RegexNode& node) {
    switch (node.type) {
        case LITERAL:
            // 创建两个状态，用字符边连接
            break;
        case STAR:
            // 创建ε环，实现零次或多次重复
            break;
        case GROUP:
            // 递归编译子节点，然后串联
            break;
        // ... 其他情况
    }
}

注意：实现STAR（'*'）时，一定要处理好ε环的终止条件。否则你的引擎会陷入无限循环——状态在ε边上跳来跳去，永远不消耗字符。我曾经debug了一整个下午，才发现是ε边的去重没做。

第三步：执行器——跑状态机

有了NFA状态图，匹配就变成了一个“状态集模拟”的过程。为什么是状态集？因为NFA是非确定的——同一个字符可能跳到多个状态。所以我们要同时跟踪所有可能的状态。

算法很简单：

  1. 从起始状态开始，先走完所有ε边，得到初始状态集
  2. 对于输入字符串的每个字符，计算当前状态集经过该字符后能到达的所有状态
  3. 每步都要扩展ε边（这叫ε闭包）
  4. 如果某个状态是接受态，恭喜，匹配成功
bool match(const std::string& text, const NFA& nfa) {
    std::set<int> current_states = epsilon_closure({nfa.start_state});
    
    for (char c : text) {
        std::set<int> next_states;
        for (int s : current_states) {
            // 查找字符c能跳到的状态
            auto it = nfa.states[s].transitions.find(c);
            if (it != nfa.states[s].transitions.end()) {
                for (int target : it->second) {
                    next_states.insert(target);
                }
            }
        }
        // 扩展ε闭包
        current_states = epsilon_closure(next_states);
    }
    
    // 检查是否有接受态
    for (int s : current_states) {
        if (nfa.states[s].is_accept) return true;
    }
    return false;
}

性能优化：如果你只需要匹配（不需要捕获组），可以把NFA转成DFA。DFA每个字符只跳一个状态，速度飞快。代价是构建DFA的时间更长，而且可能产生状态爆炸。我个人习惯：小规模匹配用NFA，大规模文本扫描用DFA。

避坑指南：我踩过的那些雷

做这个项目时，有几个坑让我印象特别深：

  • 回溯陷阱：NFA匹配时，如果遇到多个分支，要决定先走哪条。走错了就得回溯。极端情况下，比如 "a*a*a*a*a*b" 匹配 "aaaaaaaaac"，回溯次数会爆炸。解决办法是加一个“匹配次数上限”，或者改用DFA。
  • 空匹配：模式 "a*" 可以匹配空字符串。如果你的引擎遇到空匹配就卡住，记得在循环里检查“是否消耗了字符”。没消耗就强制前进一位。
  • 字符类边界：'[a-z]' 和 '[^a-z]' 的取反逻辑，别忘了处理。还有 ']' 本身作为字面量时，要放在字符类的开头。

扩展思考：还能加什么？

这个基础引擎做完后，你可以给它加一些“高级功能”：

功能 实现思路 难度
捕获组 在NFA状态上记录“分组开始/结束”标记，匹配时保存位置 中等
反向引用 匹配时动态生成新的NFA片段，引用之前捕获的内容 困难
零宽断言 在NFA中引入“环视”边，匹配但不消耗字符 较难
懒惰匹配 修改回溯策略，优先走最短路径 中等

我个人觉得，捕获组是最值得加的。因为很多实际场景——比如提取日志中的IP地址、解析URL参数——都需要知道“匹配到了什么”，而不是仅仅“有没有匹配到”。

好了，关于正则表达式引擎的核心实现，就聊到这里。代码量其实不大，核心逻辑也就两三百行。但这里面涉及到的状态机、递归、回溯这些思想，在编译器、协议解析、甚至游戏AI里都能看到。嗯，值得你花一个周末好好撸一遍。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →