发布于 由admin

C++实现自定义Regex引擎：利用NFA/DFA进行模式匹配与性能优化

好的，没问题。

C++ 自定义 Regex 引擎：利用 NFA/DFA 进行模式匹配与性能优化

大家好，今天我们来聊聊如何用 C++ 构建一个自定义的正则表达式引擎。我们将深入探讨 NFA（非确定有限自动机）和 DFA（确定有限自动机）在模式匹配中的应用，并讨论一些性能优化的策略。

1. 正则表达式引擎概述

一个正则表达式引擎主要负责两件事：

  1. 解析正则表达式: 将输入的正则表达式字符串转换为内部表示，方便后续处理。
  2. 模式匹配: 使用内部表示在目标文本中查找匹配的子串。

常见的正则表达式引擎实现方式有两种：

  • 回溯 (Backtracking): 这种方法基于正则表达式直接进行匹配，在遇到不匹配时会回溯到之前的状态，尝试其他的匹配路径。 优点是实现简单，支持的特性丰富。 缺点是性能可能较差，特别是对于复杂的正则表达式和较长的目标文本，容易出现“灾难性回溯” (catastrophic backtracking) 的问题。
  • 有限自动机 (Finite Automata): 这种方法将正则表达式转换为有限自动机，然后利用自动机进行匹配。 优点是匹配速度快，时间复杂度是线性的。 缺点是实现相对复杂，可能需要消耗较多的内存。

今天我们主要讨论基于有限自动机的方式，并且会从 NFA 开始，最终优化到 DFA。

2. 正则表达式语法和抽象语法树 (AST)

首先，我们要定义一个简单的正则表达式语法，并实现一个能够将正则表达式字符串解析成抽象语法树 (AST) 的解析器。 让我们先定义我们支持的简单语法：

  • 字符 (Character): a, b, c, …
  • 连接 (Concatenation): ab, abc, …
  • 或 (Alternation): a|b, a|b|c, …
  • 重复 (Kleene Star): a*, (ab)*, …
  • 括号 (Grouping): (a), (a|b), …

下面是用 C++ 表示 AST 节点的代码：

#include <iostream>
#include <string>
#include <vector>

enum class NodeType {
    CHARACTER,
    CONCATENATION,
    ALTERNATION,
    KLEENE_STAR,
    GROUP
};

class ASTNode {
public:
    NodeType type;
    char character;
    std::vector<ASTNode*> children;

    ASTNode(NodeType type) : type(type), character(0) {}
    ASTNode(NodeType type, char character) : type(type), character(character) {}

    ~ASTNode() {
        for (ASTNode* child : children) {
            delete child;
        }
    }
};

// 辅助函数，用于打印 AST 结构
void printAST(ASTNode* node, int indent = 0) {
    for (int i = 0; i < indent; ++i) {
        std::cout << "  ";
    }

    switch (node->type) {
        case NodeType::CHARACTER:
            std::cout << "CHARACTER: " << node->character << std::endl;
            break;
        case NodeType::CONCATENATION:
            std::cout << "CONCATENATION" << std::endl;
            break;
        case NodeType::ALTERNATION:
            std::cout << "ALTERNATION" << std::endl;
            break;
        case NodeType::KLEENE_STAR:
            std::cout << "KLEENE_STAR" << std::endl;
            break;
        case NodeType::GROUP:
            std::cout << "GROUP" << std::endl;
            break;
    }

    for (ASTNode* child : node->children) {
        printAST(child, indent + 1);
    }
}

// 简单的解析器示例 (仅支持连接和字符)
ASTNode* parseRegex(const std::string& regex) {
    ASTNode* root = new ASTNode(NodeType::CONCATENATION);
    for (char c : regex) {
        ASTNode* charNode = new ASTNode(NodeType::CHARACTER, c);
        root->children.push_back(charNode);
    }
    return root;
}

int main() {
    std::string regex = "abc";
    ASTNode* ast = parseRegex(regex);
    printAST(ast);

    delete ast; // 释放内存

    return 0;
}

这个例子只是一个非常简化的解析器，只支持连接和字符。 一个完整的正则表达式解析器需要处理所有语法规则，并且需要处理优先级和结合性。 这通常使用递归下降解析器或者其他的解析器生成器来实现。 由于解析器的实现比较复杂，我们这里只提供一个简单的示例，重点放在后续的 NFA/DFA 构建和匹配上。

3. NFA (非确定有限自动机)

NFA 是一种状态机，它由以下几个部分组成：

  • 状态集合 (States)
  • 输入字母表 (Alphabet)
  • 转移函数 (Transition Function): δ(state, input) -> 状态集合
  • 起始状态 (Start State)
  • 接受状态集合 (Accepting States)

与 DFA 相比，NFA 的转移函数可以返回一个状态集合，这意味着在同一个状态下，对于同一个输入，NFA 可以转移到多个不同的状态。 此外，NFA 还允许 ε-转移 (epsilon transition)，即不消耗任何输入就可以进行状态转移。

3.1 NFA 的表示

我们可以用 C++ 来表示 NFA：

#include <iostream>
#include <vector>
#include <set>
#include <map>

class NFAState {
public:
    int id;  // 状态ID
    bool isAccepting; // 是否是接受状态

    NFAState(int id) : id(id), isAccepting(false) {}
};

class NFA {
public:
    std::vector<NFAState*> states;
    std::map<std::pair<int, char>, std::set<int>> transitions; // 转移函数: (state_id, input_char) -> set of state_ids
    int startStateId;

    NFA(int startStateId) : startStateId(startStateId) {}

    ~NFA() {
        for (NFAState* state : states) {
            delete state;
        }
    }

    // 添加状态
    NFAState* addState() {
        NFAState* newState = new NFAState(states.size());
        states.push_back(newState);
        return newState;
    }

    // 添加转移
    void addTransition(int fromStateId, char input, int toStateId) {
        transitions[{fromStateId, input}].insert(toStateId);
    }

    // 添加 epsilon 转移
    void addEpsilonTransition(int fromStateId, int toStateId) {
        addTransition(fromStateId, '', toStateId); // 使用 '' 表示 epsilon 转移
    }

    // 打印 NFA 结构
    void printNFA() {
        std::cout << "NFA:" << std::endl;
        std::cout << "  Start State: " << startStateId << std::endl;
        std::cout << "  States:" << std::endl;
        for (const auto& state : states) {
            std::cout << "    State " << state->id << (state->isAccepting ? " (Accepting)" : "") << std::endl;
        }
        std::cout << "  Transitions:" << std::endl;
        for (const auto& transition : transitions) {
            std::cout << "    (" << transition.first.first << ", ";
            if (transition.first.second == '') {
                std::cout << "epsilon";
            } else {
                std::cout << transition.first.second;
            }
            std::cout << ") -> {";
            for (int toStateId : transition.second) {
                std::cout << toStateId << " ";
            }
            std::cout << "}" << std::endl;
        }
    }
};

3.2 从正则表达式构建 NFA (Thompson 构造法)

Thompson 构造法是一种将正则表达式转换为 NFA 的经典算法。 它为每种正则表达式语法规则定义了相应的 NFA 构造方法。

  • 字符 (Character) c:

    --> (state) --c--> (state) -->

  • 连接 (Concatenation) AB: 将 A 的 NFA 和 B 的 NFA 连接起来，A 的接受状态通过 ε-转移连接到 B 的起始状态。

  • 或 (Alternation) A|B: 创建一个新的起始状态和一个新的接受状态，然后从新的起始状态分别通过 ε-转移连接到 A 和 B 的起始状态，A 和 B 的接受状态通过 ε-转移连接到新的接受状态。

  • *重复 (Kleene Star) `A`**: 创建一个新的起始状态和一个新的接受状态，然后从新的起始状态通过 ε-转移连接到 A 的起始状态和新的接受状态，A 的接受状态通过 ε-转移连接到 A 的起始状态和新的接受状态。

下面是用 C++ 实现 Thompson 构造法的代码：

#include <iostream>
#include <vector>
#include <set>
#include <map>

// 前面定义的 NFAState 和 NFA 类省略...

// Thompson 构造法
NFA* constructNFA(ASTNode* astNode) {
    if (astNode->type == NodeType::CHARACTER) {
        NFA* nfa = new NFA(0);
        NFAState* startState = nfa->addState();
        NFAState* acceptState = nfa->addState();
        acceptState->isAccepting = true;
        nfa->addTransition(startState->id, astNode->character, acceptState->id);
        return nfa;
    } else if (astNode->type == NodeType::CONCATENATION) {
        if (astNode->children.empty()) {
            // 空连接，创建一个接受状态
            NFA* nfa = new NFA(0);
            NFAState* startState = nfa->addState();
            startState->isAccepting = true;
            return nfa;
        }

        NFA* nfa = constructNFA(astNode->children[0]);
        for (size_t i = 1; i < astNode->children.size(); ++i) {
            NFA* nextNFA = constructNFA(astNode->children[i]);
            // 连接两个 NFA
            for (NFAState* state : nfa->states) {
                if (state->isAccepting) {
                    nfa->addEpsilonTransition(state->id, nextNFA->startStateId + nfa->states.size());
                    state->isAccepting = false; // 设置为非接受状态
                }
            }

            // 合并 nextNFA 的状态和转移到 nfa
            int offset = nfa->states.size();
            for (NFAState* state : nextNFA->states) {
                NFAState* newState = nfa->addState();
                newState->isAccepting = state->isAccepting;
            }

            for (const auto& transition : nextNFA->transitions) {
                nfa->addTransition(transition.first.first + offset, transition.first.second, *transition.second.begin() + offset); // 假设每个转移只有一个目标状态
            }
            delete nextNFA;
        }
        return nfa;
    } else {
        // 其他情况 (ALTERNATION, KLEENE_STAR, GROUP) 未实现
        std::cerr << "Unsupported AST Node Type." << std::endl;
        return nullptr;
    }
}

int main() {
    std::string regex = "abc";
    ASTNode* ast = parseRegex(regex);
    NFA* nfa = constructNFA(ast);

    if (nfa) {
        nfa->printNFA();
        delete nfa;
    }

    delete ast;

    return 0;
}

这个例子只实现了字符和连接的 Thompson 构造。 其他操作符的构造过程类似，需要根据其对应的 NFA 结构进行实现。

3.3 NFA 的匹配

NFA 的匹配过程需要维护一个当前状态集合，表示 NFA 当前可能处于的所有状态。对于每个输入字符，我们需要计算从当前状态集合出发，经过该字符能够到达的所有状态，并将结果作为新的当前状态集合。 此外，我们还需要在每次移动后，计算当前状态集合的 ε-闭包 (epsilon closure)，即从当前状态集合中的每个状态出发，经过 ε-转移能够到达的所有状态。

#include <iostream>
#include <vector>
#include <set>
#include <map>

// 前面定义的 NFAState 和 NFA 类省略...

// 计算 epsilon 闭包
std::set<int> epsilonClosure(const NFA& nfa, const std::set<int>& states) {
    std::set<int> closure = states;
    std::vector<int> stack(states.begin(), states.end());

    while (!stack.empty()) {
        int stateId = stack.back();
        stack.pop_back();

        for (const auto& transition : nfa.transitions) {
            if (transition.first.first == stateId && transition.first.second == '') { // epsilon 转移
                for (int toStateId : transition.second) {
                    if (closure.find(toStateId) == closure.end()) {
                        closure.insert(toStateId);
                        stack.push_back(toStateId);
                    }
                }
            }
        }
    }

    return closure;
}

// NFA 匹配
bool matchNFA(const NFA& nfa, const std::string& text) {
    std::set<int> currentStates = {nfa.startStateId};
    currentStates = epsilonClosure(nfa, currentStates);

    for (char c : text) {
        std::set<int> nextStates;
        for (int stateId : currentStates) {
            for (const auto& transition : nfa.transitions) {
                if (transition.first.first == stateId && transition.first.second == c) {
                    for (int toStateId : transition.second) {
                        nextStates.insert(toStateId);
                    }
                }
            }
        }
        currentStates = epsilonClosure(nfa, nextStates);
    }

    // 检查是否存在接受状态
    for (int stateId : currentStates) {
        for (const auto& state : nfa.states) {
            if (state->id == stateId && state->isAccepting) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    std::string regex = "abc";
    ASTNode* ast = parseRegex(regex);
    NFA* nfa = constructNFA(ast);

    if (nfa) {
        nfa->printNFA();
        std::string text = "abcdefg";
        bool matched = matchNFA(*nfa, text);

        if (matched) {
            std::cout << "Text '" << text << "' matches the regex '" << regex << "'" << std::endl;
        } else {
            std::cout << "Text '" << text << "' does not match the regex '" << regex << "'" << std::endl;
        }

        delete nfa;
    }

    delete ast;

    return 0;
}

4. DFA (确定有限自动机)

DFA 是一种特殊的 NFA，它的转移函数对于每个状态和每个输入字符都返回一个唯一的状态。 DFA 没有 ε-转移。 这意味着 DFA 在匹配过程中，当前状态始终是唯一的，从而避免了 NFA 中需要维护状态集合和计算 ε-闭包的开销。

4.1 从 NFA 转换到 DFA (子集构造法)

子集构造法是一种将 NFA 转换为 DFA 的经典算法。 它的基本思想是：DFA 的每个状态对应于 NFA 的一个状态集合。

算法步骤如下：

  1. 计算 NFA 的起始状态的 ε-闭包，作为 DFA 的起始状态。
  2. 对于 DFA 的每个未标记状态，计算从该状态出发，经过每个输入字符能够到达的 NFA 状态集合，并计算这些状态集合的 ε-闭包。 如果计算出的 ε-闭包已经存在于 DFA 中，则创建一个新的 DFA 状态，并将转移添加到 DFA 中。
  3. 重复步骤 2，直到 DFA 中没有未标记的状态。
  4. DFA 的接受状态是那些包含 NFA 接受状态的 DFA 状态。
#include <iostream>
#include <vector>
#include <set>
#include <map>

// 前面定义的 NFAState 和 NFA 类省略...

class DFAState {
public:
    int id;
    std::set<int> nfaStateIds; // 对应的 NFA 状态集合
    bool isAccepting;

    DFAState(int id, const std::set<int>& nfaStateIds) : id(id), nfaStateIds(nfaStateIds), isAccepting(false) {}
};

class DFA {
public:
    std::vector<DFAState*> states;
    std::map<std::pair<int, char>, int> transitions; // 转移函数: (state_id, input_char) -> state_id
    int startStateId;

    DFA(int startStateId) : startStateId(startStateId) {}

    ~DFA() {
        for (DFAState* state : states) {
            delete state;
        }
    }

    // 添加状态
    DFAState* addState(const std::set<int>& nfaStateIds) {
        DFAState* newState = new DFAState(states.size(), nfaStateIds);
        states.push_back(newState);
        return newState;
    }

    // 添加转移
    void addTransition(int fromStateId, char input, int toStateId) {
        transitions[{fromStateId, input}] = toStateId;
    }

     // 打印 DFA 结构
    void printDFA() {
        std::cout << "DFA:" << std::endl;
        std::cout << "  Start State: " << startStateId << std::endl;
        std::cout << "  States:" << std::endl;
        for (const auto& state : states) {
            std::cout << "    State " << state->id << " (NFA States: ";
            for (int nfaStateId : state->nfaStateIds) {
                std::cout << nfaStateId << " ";
            }
            std::cout << ")" << (state->isAccepting ? " (Accepting)" : "") << std::endl;
        }
        std::cout << "  Transitions:" << std::endl;
        for (const auto& transition : transitions) {
            std::cout << "    (" << transition.first.first << ", " << transition.first.second << ") -> " << transition.second << std::endl;
        }
    }
};

// 子集构造法
DFA* constructDFA(const NFA& nfa) {
    std::map<std::set<int>, int> stateMap; // 用于记录 DFA 状态和对应的 ID

    DFA* dfa = new DFA(0);
    std::set<int> startStateIds = epsilonClosure(nfa, {nfa.startStateId});
    DFAState* startState = dfa->addState(startStateIds);
    stateMap[startStateIds] = startState->id;

    std::vector<int> unmarkedStates = {startState->id};

    while (!unmarkedStates.empty()) {
        int dfaStateId = unmarkedStates.back();
        unmarkedStates.pop_back();
        DFAState* dfaState = dfa->states[dfaStateId];

        // 找到所有输入字符
        std::set<char> alphabet;
        for (const auto& transition : nfa.transitions) {
            if (transition.first.second != '') { // 排除 epsilon 转移
                alphabet.insert(transition.first.second);
            }
        }

        for (char input : alphabet) {
            std::set<int> nextNFAStateIds;
            for (int nfaStateId : dfaState->nfaStateIds) {
                for (const auto& transition : nfa.transitions) {
                    if (transition.first.first == nfaStateId && transition.first.second == input) {
                        for (int toStateId : transition.second) {
                            nextNFAStateIds.insert(toStateId);
                        }
                    }
                }
            }
            nextNFAStateIds = epsilonClosure(nfa, nextNFAStateIds);

            if (nextNFAStateIds.empty()) {
                continue; // 没有转移
            }

            int nextDFAStateId;
            if (stateMap.find(nextNFAStateIds) == stateMap.end()) {
                // 创建新的 DFA 状态
                DFAState* nextDFAState = dfa->addState(nextNFAStateIds);
                stateMap[nextNFAStateIds] = nextDFAState->id;
                nextDFAStateId = nextDFAState->id;
                unmarkedStates.push_back(nextDFAStateId);
            } else {
                nextDFAStateId = stateMap[nextNFAStateIds];
            }

            dfa->addTransition(dfaStateId, input, nextDFAStateId);
        }
    }

    // 标记接受状态
    for (DFAState* state : dfa->states) {
        for (int nfaStateId : state->nfaStateIds) {
            for (const auto& nfaState : nfa.states) {
                if (nfaState->id == nfaStateId && nfaState->isAccepting) {
                    state->isAccepting = true;
                    break;
                }
            }
            if (state->isAccepting) break;
        }
    }

    return dfa;
}

int main() {
    std::string regex = "abc";
    ASTNode* ast = parseRegex(regex);
    NFA* nfa = constructNFA(ast);

    if (nfa) {
        DFA* dfa = constructDFA(*nfa);
        if (dfa) {
            dfa->printDFA();
            delete dfa;
        }
        delete nfa;
    }

    delete ast;

    return 0;
}

4.2 DFA 的匹配

DFA 的匹配过程非常简单，从起始状态开始，对于每个输入字符，根据转移函数转移到下一个状态。 如果最终到达的状态是接受状态，则匹配成功。

#include <iostream>
#include <vector>
#include <set>
#include <map>

// 前面定义的 DFAState 和 DFA 类省略...

// DFA 匹配
bool matchDFA(const DFA& dfa, const std::string& text) {
    int currentStateId = dfa.startStateId;

    for (char c : text) {
        auto transition = dfa.transitions.find({currentStateId, c});
        if (transition == dfa.transitions.end()) {
            return false; // 没有转移
        }
        currentStateId = transition->second;
    }

    // 检查是否是接受状态
    for (const auto& state : dfa.states) {
        if (state->id == currentStateId && state->isAccepting) {
            return true;
        }
    }

    return false;
}

int main() {
     std::string regex = "abc";
    ASTNode* ast = parseRegex(regex);
    NFA* nfa = constructNFA(ast);

    if (nfa) {
        DFA* dfa = constructDFA(*nfa);
        if (dfa) {
            dfa->printDFA();

            std::string text = "abcdefg";
            bool matched = matchDFA(*dfa, text);

            if (matched) {
                std::cout << "Text '" << text << "' matches the regex '" << regex << "'" << std::endl;
            } else {
                std::cout << "Text '" << text << "' does not match the regex '" << regex << "'" << std::endl;
            }

            delete dfa;
        }
        delete nfa;
    }

    delete ast;

    return 0;
}

5. 性能优化

  • DFA 最小化: 使用 Hopcroft 算法或者其他 DFA 最小化算法，可以减少 DFA 的状态数量，从而减少内存消耗和提高匹配速度。
  • 延迟 DFA 构建: 在实际应用中，可以将 DFA 的构建过程延迟到第一次匹配时进行。 如果正则表达式很少使用，则可以避免构建 DFA 的开销。
  • 缓存 DFA: 将构建好的 DFA 缓存起来，以便下次使用。 可以使用 LRU (Least Recently Used) 缓存策略来管理 DFA 缓存。
  • 特殊情况优化: 对于一些简单的正则表达式，可以直接使用字符串查找算法 (如 Knuth-Morris-Pratt 算法或 Boyer-Moore 算法) 进行匹配，而无需构建 NFA/DFA。
  • SIMD 指令: 可以使用 SIMD (Single Instruction Multiple Data) 指令来并行处理多个字符，从而提高匹配速度。
  • 代码生成: 可以将正则表达式编译成机器码，从而获得更高的执行效率。

6. 总结

我们学习了如何用 C++ 构建一个自定义的正则表达式引擎，从正则表达式语法解析到AST，再到NFA的Thompson构造法，以及NFA转换到DFA的子集构造法，最后DFA进行匹配。并讨论了一些性能优化策略。虽然只是一个简单的示例，但它涵盖了正则表达式引擎的核心概念。希望通过今天的讨论，大家能够对正则表达式引擎的实现有更深入的理解。

更多IT精英技术系列讲座，到智猿学院

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注