正则表达式引擎的实现原理:从 Thompson NFA 到 Pike VM 的高性能模式匹配

正则表达式是每个工程师的日常工具。我们用它做日志解析、输入验证、代码搜索,几乎无处不在。但很少有人深入思考:当我们调用 regex.MatchString() 时,底层究竟发生了什么?本文将从形式语言理论出发,逐步构建一个完整的正则表达式引擎,从 Thompson 的 NFA 构造法到 Pike VM——这种被 RE2 和 Go 标准库采用的并行 NFA 模拟技术,以及如何在 Rust 中从零实现它。

一、问题的本质:从模式到状态机

正则表达式的理论基础可以追溯到 1956 年,Kleene 在自动机理论中证明了正则表达式与有限自动机等价。这意味着任何正则表达式都可以转换为一个有限状态自动机(FA),反之亦然。

正则表达式的核心操作只有三种:

  • 连接(Concatenation):ab 表示匹配 a 后跟匹配 b
  • 选择(Alternation):a|b 表示匹配 a 或匹配 b
  • 闭包(Kleene Star):a* 表示匹配零个或多个 a

一个完整的正则引擎需要处理以下语法元素:

  • . 通配符(匹配任意字符)
  • * + ? 量词(零或多、一或多、零或一)
  • [...] 字符类
  • (...) 分组
  • (a|b) 选择
  • ^ $ 边界锚点
  • {m,n} 区间量词

引擎的实现路径一般为:正则表达式字符串 → Token 流(词法分析)→ AST(语法分析)→ NFA(Thomson 构造)→ 模拟执行或 DFA 编译 → 匹配结果。

二、词法分析与语法分析

首先将正则表达式字符串解析为抽象语法树(AST)。这是编译原理的标准前端。

#[derive(Debug, Clone)]
pub enum Regex {
    Empty,                    // ε 空
    Char(char),               // 单字符
    CharClass(Vec<(char, char)>), // 字符类 [a-z]
    AnyChar,                  // .
    Concat(Vec<Regex>),       // 连接
    Alt(Box<Regex>, Box<Regex>), // 选择 |
    Star(Box<Regex>),         // *
    Plus(Box<Regex>),         // +
    Optional(Box<Regex>),     // ?
    Group(Box<Regex>),        // 分组 ()
}

解析器的核心是一个简单的递归下降解析器:

pub struct Parser {
    chars: Vec<char>,
    pos: usize,
}

impl Parser {
    pub fn parse(&mut self) -> Result<Regex, String> {
        self.parse_alt()
    }

    fn parse_alt(&mut self) -> Result<Regex, String> {
        let mut left = self.parse_concat()?;
        while self.peek() == Some('|') {
            self.advance();
            let right = self.parse_concat()?;
            left = Regex::Alt(Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    fn parse_concat(&mut self) -> Result<Regex, String> {
        let mut parts = Vec::new();
        while self.peek().map_or(false, |c| c != '|' && c != ')') {
            parts.push(self.parse_quantified()?);
        }
        if parts.is_empty() {
            Ok(Regex::Empty)
        } else if parts.len() == 1 {
            Ok(parts.into_iter().next().unwrap())
        } else {
            Ok(Regex::Concat(parts))
        }
    }

    fn parse_quantified(&mut self) -> Result<Regex, String> {
        let base = self.parse_atom()?;
        match self.peek() {
            Some('*') => { self.advance(); Ok(Regex::Star(Box::new(base))) }
            Some('+') => { self.advance(); Ok(Regex::Plus(Box::new(base))) }
            Some('?') => { self.advance(); Ok(Regex::Optional(Box::new(base))) }
            _ => Ok(base),
        }
    }

    fn parse_atom(&mut self) -> Result<Regex, String> {
        match self.peek() {
            Some('(') => {
                self.advance();
                let inner = self.parse()?;
                if self.peek() == Some(')') { self.advance(); }
                Ok(Regex::Group(Box::new(inner)))
            }
            Some('[') => self.parse_char_class(),
            Some('.') => { self.advance(); Ok(Regex::AnyChar) }
            Some('\\') => self.parse_escape(),
            Some(c) => { self.advance(); Ok(Regex::Char(c)) }
            None => Ok(Regex::Empty),
        }
    }
}

至此,形如 (a|b)*c+d 的模式串被转换为一棵 AST。接下来进入核心编译阶段。

三、Thompson 构造法:AST 到 NFA

1968 年,Ken Thompson 在他的经典论文 "Programming Techniques: Regular expression search algorithm" 中提出了一种递归构造方法,即为每一种正则表达式语法规则生成对应的小型 NFA 片段(fragment),然后通过 ε-转移(epsilon transitions)将它们拼接起来。

NFA 片段的抽象表示:

#[derive(Debug, Clone)]
pub enum State {
    Split(usize, usize),        // ε 分裂:两个分支目标
    CharClass(Vec<(char, char)>, usize), // 字符类匹配 + 目标
    Any(usize),                 // . 通配 + 目标
    Match,                      // 接受状态
}

pub struct NFA {
    pub states: Vec<State>,
}

Thompson 构造的核心特征是每个片段恰好有一个出口状态。对于空表达式 ε,我们生成一个指向出口的 ε-转移。对于选择 E1|E2,一个 Split 状态有两个分支分别指向两个子片段的入口。

pub fn ast_to_nfa(ast: &Regex, nfa: &mut NFA, output: &mut FragmentOutput) -> (usize, usize) {
    // 返回 (entry_state, exit_state_index_placeholder)
    match ast {
        Regex::Empty => {
            let s = nfa.add_state(State::Split(OUT_UNSET, OUT_UNSET));
            (s, s) // 两者暂时都指向自身稍后修补
        }
        Regex::Char(c) => {
            let s = nfa.add_state(State::CharClass(vec![(*c, *c)], OUT_UNSET));
            (s, s)
        }
        Regex::AnyChar => {
            let s = nfa.add_state(State::Any(OUT_UNSET));
            (s, s)
        }
        Regex::Concat(parts) => {
            let mut entry = 0;
            let mut prev_exit = 0;
            for (i, part) in parts.iter().enumerate() {
                let (e, x) = ast_to_nfa(part, nfa);
                if i == 0 { entry = e; }
                else { patch(nfa, prev_exit, e); }
                prev_exit = x;
            }
            (entry, prev_exit)
        }
        Regex::Alt(left, right) => {
            let s = nfa.add_state(State::Split(OUT_UNSET, OUT_UNSET));
            let (e1, x1) = ast_to_nfa(left, nfa);
            let (e2, x2) = ast_to_nfa(right, nfa);
            nfa.states[s] = State::Split(e1, e2);
            let x = nfa.add_state(State::Split(OUT_UNSET, OUT_UNSET));
            patch(nfa, x1, x);
            (s, x)
        }
        Regex::Star(inner) => {
            let s = nfa.add_state(State::Split(OUT_UNSET, OUT_UNSET));
            let (e, x) = ast_to_nfa(inner, nfa);
            nfa.states[s] = State::Split(e, OUT_UNSET); // 第二个分支稍后设为出口
            let exit = nfa.add_state(State::Split(OUT_UNSET, OUT_UNSET));
            nfa.states[s] = State::Split(e, exit); // 修正:跳过重入
            patch(nfa, x, s);         // 匹配后回到开头
            (s, exit)
        }
        // ... Plus 和 Optional 类似
        _ => unimplemented!(),
    }
}

这里有一个关键技巧——出口修补(patch)。许多构造中出口在创建时并不确定,我们记录一个占位符(OUT_UNSET),在后续知道真正的出口时回填。实际上更高效的做法是使用弗兰(fragment)结构体,记录一组等修补的出口:

pub struct Fragment {
    pub start: usize,
    pub out: Vec<usize>, // 尚未连接出口的状态列表
}

pub fn patch(nfa: &mut NFA, out: &[usize], target: usize) {
    for &s in out {
        match &mut nfa.states[s] {
            State::Split(_, ref mut b) if *b == OUT_UNSET => *b = target,
            State::CharClass(_, ref mut t) if *t == OUT_UNSET => *t = target,
            State::Any(ref mut t) if *t == OUT_UNSET => *t = target,
            _ => {}
        }
    }
}

Thompson 构造法生成的 NFA 具有几个优美性质:每个状态最多有 2 个出边、ε 转移的存在使得片段拼接变得简单、总状态数是 O(n)(n 为正则表达式长度)。

四、子集构造法:NFA 到 DFA

NFA 模拟虽然常用,但其非确定性意味着每一步可能需要跟踪大量可能的活跃状态。另一种思路是子集构造法(Subset Construction):将 NFA 的每个状态子集映射为一个 DFA 状态。

pub fn nfa_to_dfa(nfa: &NFA, start: usize) -> DFA {
    let mut dfa = DFA::new();
    let mut unmarked = VecDeque::new();

    let start_set = epsilon_closure(nfa, &[start]);
    let start_id = dfa.add_state(start_set.clone(), is_match(&nfa, &start_set));
    unmarked.push_back(start_id);

    while let Some(dfa_state_id) = unmarked.pop_front() {
        for c in ALPHABET.chars() {
            let next_set = epsilon_closure(
                &nfa,
                &move_on_char(&nfa, dfa.states[dfa_state_id].nfa_set, c)
            );
            if next_set.is_empty() { continue; }

            let next_id = dfa.get_or_add_state(next_set, is_match(&nfa, &next_set));
            dfa.set_transition(dfa_state_id, c, next_id);

            if !dfa.states[next_id].marked {
                dfa.states[next_id].marked = true;
                unmarked.push_back(next_id);
            }
        }
    }
    dfa
}

其中 epsilon_closure 计算从给定状态集出发通过 ε-转移可达的所有状态:

fn epsilon_closure(nfa: &NFA, states: &[usize]) -> Vec<usize> {
    let mut set = Vec::with_capacity(states.len());
    let mut stack: Vec<usize> = states.iter().copied().collect();
    let mut in_set = HashSet::new();

    while let Some(s) = stack.pop() {
        if in_set.insert(s) {
            set.push(s);
            match &nfa.states[s] {
                State::Split(a, b) => {
                    if *a != OUT_UNSET { stack.push(*a); }
                    if *b != OUT_UNSET { stack.push(*b); }
                }
                _ => {}
            }
        }
    }
    set.sort();
    set
}

警告:子集构造法的最坏情况是状态数爆炸。 正则表达式 (a|b)*a(a|b){n} 生成的 NFA 有 O(n) 个状态,但对应的 DFA 可能有 2^n 个状态。这就是为什么 RE2 和 Go 的 regexp 包选择了 Pike VM 方案。

五、Hopcroft 算法:DFA 最小化

当我们确实需要 DFA(例如性能关键的场景),可以将 DFA 最小化。Hopcroft 算法的时间复杂度为 O(n log n):

pub fn minimize_dfa(dfa: &mut DFA) {
    // 1. 初始划分:接受状态 vs 非接受状态
    let mut partitions: Vec<Vec<usize>> = vec![
        dfa.states.iter().enumerate()
            .filter(|(_, s)| !s.accepting).map(|(i, _)| i).collect(),
        dfa.states.iter().enumerate()
            .filter(|(_, s)| s.accepting).map(|(i, _)| i).collect(),
    ];
    partitions.retain(|p| !p.is_empty());

    let mut worklist: VecDeque<(char, usize)> = VecDeque::new();
    for c in ALPHABET.chars() {
        for &p_idx in 0..partitions.len() {
            worklist.push_back((c, p_idx));
        }
    }

    while let Some((c, target_idx)) = worklist.pop_front() {
        for (p_idx, partition) in partitions.iter_mut().enumerate() {
            let (with_c, without_c): (Vec<usize>, Vec<usize>) = partition.iter()
                .copied()
                .partition(|&s| dfa.states[s].transitions.get(&c)
                    .map_or(false, |&t| partitions[target_idx].binary_search(&t).is_ok()));

            if !with_c.is_empty() && !without_c.is_empty() {
                let new_idx = partitions.len();
                partitions.push(with_c);
                *partition = without_c;

                for ch in ALPHABET.chars() {
                    worklist.push_back((ch, new_idx));
                    worklist.push_back((ch, p_idx));
                }
            }
        }
    }
}

最小化后的 DFA 对于给定的正则语言是唯一的(同构意义下),这为优化和验证提供了保证。

六、Pike VM:并行 NFA 模拟

Russ Cox 在 2007 年的论文 "Regular Expression Matching: the Virtual Machine Approach" 中介绍了 Pike VM —— 一种受 Thompson threaded NFA 启发的现代方法。它也是被 Go 标准库 regexp 和 Google RE2 采用的引擎核心。

核心思想

Pike VM 维护一个线程列表(clist 和 nlist),其中每个线程是 (线程ID, 当前输入位置)。每一步:

  1. 对 CLIST(当前活跃线程)中的每个线程,执行其状态的指令
  2. 将产生的新线程收集到 NLIST
  3. 交换 CLIST 和 NLIST,进入下一轮

关键优化在于去重:同一 PC(program counter)位置的多个线程只保留一个。

编译为 VM 指令集

NFA 被编译为字节码:

#[derive(Debug, Clone)]
pub enum Inst {
    Char(char),           // 匹配单个字符
    CharClass(Vec<(char, char)>), // 匹配字符类
    Any,                  // 匹配任意字符
    Match,                // 匹配成功
    Jump(usize),          // 无条件跳转
    Split(usize, usize),  // 分裂为两个线程
    Save(usize),          // 保存匹配位置(用于捕获组)
}

pub struct VM {
    pub insts: Vec<Inst>,
    pub capturing_groups: usize,
}

编译过程是直接对 AST 的递归遍历:

fn compile_ast(ast: &Regex, prog: &mut Program) -> Result<(), String> {
    match ast {
        Regex::Char(c) => {
            prog.insts.push(Inst::Char(*c));
        }
        Regex::AnyChar => {
            prog.insts.push(Inst::Any);
        }
        Regex::CharClass(ranges) => {
            prog.insts.push(Inst::CharClass(ranges.clone()));
        }
        Regex::Concat(parts) => {
            for part in parts {
                compile_ast(part, prog)?;
            }
        }
        Regex::Alt(left, right) => {
            let split_idx = prog.insts.len();
            prog.insts.push(Inst::Split(0, 0)); // 占位
            let left_idx = prog.insts.len();
            compile_ast(left, prog)?;
            let jmp_idx = prog.insts.len();
            prog.insts.push(Inst::Jump(0)); // 占位
            let right_idx = prog.insts.len();
            compile_ast(right, prog)?;
            let end_idx = prog.insts.len();

            prog.insts[split_idx] = Inst::Split(left_idx, right_idx);
            prog.insts[jmp_idx] = Inst::Jump(end_idx);
        }
        Regex::Star(inner) => {
            let loop_start = prog.insts.len();
            prog.insts.push(Inst::Split(0, 0)); // 占位
            compile_ast(inner, prog)?;
            prog.insts.push(Inst::Jump(loop_start));
            let exit = prog.insts.len();
            prog.insts[loop_start] = Inst::Split(loop_start + 1, exit);
        }
        Regex::Plus(inner) => {
            let loop_start = prog.insts.len();
            compile_ast(inner, prog)?;
            prog.insts.push(Inst::Split(loop_start, prog.insts.len() + 1));
        }
        Regex::Optional(inner) => {
            let split_idx = prog.insts.len();
            prog.insts.push(Inst::Split(0, 0));
            compile_ast(inner, prog)?;
            let exit = prog.insts.len();
            prog.insts[split_idx] = Inst::Split(split_idx + 1, exit);
        }
        Regex::Empty => {}
        Regex::Group(inner) => {
            // 分组处理:保存匹配起止位置
            if prog.capturing_groups > 0 {
                prog.insts.push(Inst::Save(GROUP_START));
                compile_ast(inner, prog)?;
                prog.insts.push(Inst::Save(GROUP_END));
            } else {
                compile_ast(inner, prog)?;
            }
        }
    }
    Ok(())
}

VM 执行引擎

struct Thread {
    pc: usize,
    saves: Vec<Option<usize>>, // 捕获组保存点
}

pub struct PikeVM {
    prog: Program,
}

impl PikeVM {
    pub fn new(pattern: &str) -> Result<Self, String> {
        let tokens = tokenize(pattern)?;
        let mut parser = Parser { chars: tokens, pos: 0 };
        let ast = parser.parse()?;
        let mut prog = Program { insts: Vec::new(), capturing_groups: count_groups(&ast) };
        compile_ast(&ast, &mut prog)?;
        prog.insts.push(Inst::Match);
        Ok(PikeVM { prog })
    }

    pub fn is_match(&self, text: &str) -> bool {
        self.run_match(text, false).is_some()
    }

    pub fn find<'a>(&self, text: &'a str) -> Option<(usize, usize)> {
        // 从每个位置尝试匹配
        for start in 0..=text.len() {
            if let Some(end) = self.run_match(&text[start..], true) {
                return Some((start, start + end));
            }
        }
        None
    }

    fn run_match(&self, text: &str, anchored: bool) -> Option<usize> {
        let bytes = text.as_bytes();
        let mut clist: Vec<Thread> = Vec::new();
        let mut nlist: Vec<Thread> = Vec::new();
        let mut visited: HashSet<usize> = HashSet::with_capacity(self.prog.insts.len());

        let mut t = Thread { pc: 0, saves: vec![None; self.prog.capturing_groups * 2] };
        clist.push(t);

        let mut matched_end: Option<usize> = None;

        for i in 0..=bytes.len() {
            visited.clear();
            nlist.clear();

            for th in &clist {
                match &self.prog.insts[th.pc] {
                    Inst::Match => {
                        matched_end = Some(i);
                    }
                    Inst::Char(c) => {
                        if i < bytes.len() && bytes[i] == *c as u8 {
                            nlist.push(Thread { pc: th.pc + 1, saves: th.saves.clone() });
                        }
                    }
                    Inst::Any => {
                        if i < bytes.len() {
                            nlist.push(Thread { pc: th.pc + 1, saves: th.saves.clone() });
                        }
                    }
                    Inst::CharClass(ranges) => {
                        if i < bytes.len() {
                            let b = bytes[i] as char;
                            if ranges.iter().any(|(lo, hi)| b >= *lo && b <= *hi) {
                                nlist.push(Thread { pc: th.pc + 1, saves: th.saves.clone() });
                            }
                        }
                    }
                    Inst::Split(addrs1, addrs2) => {
                        if visited.insert(*addrs1) {
                            nlist.push(Thread { pc: *addrs1, saves: th.saves.clone() });
                        }
                        if visited.insert(*addrs2) {
                            nlist.push(Thread { pc: *addrs2, saves: th.saves.clone() });
                        }
                    }
                    Inst::Jump(target) => {
                        if visited.insert(*target) {
                            nlist.push(Thread { pc: *target, saves: th.saves.clone() });
                        }
                    }
                    Inst::Save(group_id) => {
                        let mut new_saves = th.saves.clone();
                        new_saves[*group_id] = Some(i);
                        nlist.push(Thread { pc: th.pc + 1, saves: new_saves });
                    }
                }
            }

            if matched_end.is_some() {
                return matched_end;
            }

            std::mem::swap(&mut clist, &mut nlist);
        }
        matched_end
    }
}

Pike VM 的关键优化

  1. 线程去重:使用 HashSet<pc> 确保同一个 PC 不会在同一轮执行中被处理多次,将最坏情况从指数级降低到线性。

  2. 延迟克隆:使用 Arc<Vec<...>> 和 copy-on-write 语义来避免克隆保存状态。

  3. Longest Match First:对于左最左最长匹配语义,PC 位置较小的线程优先执行(对应最左匹配)。

  4. 预编译字符类索引:对于 [a-z] 等常见字符类,生成位图实现 O(1) 判断。

七、完整的 Rust 实现示例

以下是一个精简但功能完整的 Pike VM 引擎,支持常用正则运算符:

use std::collections::{HashSet, VecDeque};

const OUT_UNSET: usize = usize::MAX;

#[derive(Debug, Clone)]
pub enum Re {
    Empty,
    Char(char),
    CharClass(Vec<(char, char)>),
    Any,
    Concat(Vec<Re>),
    Alt(Box<Re>, Box<Re>),
    Star(Box<Re>),
    Plus(Box<Re>),
    Optional(Box<Re>),
    Group(Box<Re>),
}

#[derive(Debug, Clone)]
pub enum Inst {
    Char(char),
    CharClass(Vec<(char, char)>),
    Any,
    Match,
    Jump(usize),
    Split(usize, usize),
    Save(usize),
}

pub struct Program {
    pub insts: Vec<Inst>,
}

pub struct VmEngine {
    prog: Program,
}

impl VmEngine {
    pub fn compile(pattern: &str) -> Result<Self, String> {
        let mut parser = Parser { input: pattern.chars().collect(), pos: 0 };
        let ast = parser.parse_expr()?;
        let mut prog = Program { insts: Vec::new() };
        Self::emit(&ast, &mut prog)?;
        prog.insts.push(Inst::Match);
        Ok(VmEngine { prog })
    }

    fn emit(ast: &Re, prog: &mut Program) -> Result<(), String> {
        match ast {
            Re::Empty => {}
            Re::Char(c) => prog.insts.push(Inst::Char(*c)),
            Re::CharClass(r) => prog.insts.push(Inst::CharClass(r.clone())),
            Re::Any => prog.insts.push(Inst::Any),
            Re::Concat(parts) => {
                for p in parts { Self::emit(p, prog)?; }
            }
            Re::Alt(left, right) => {
                let split_pc = prog.insts.len();
                prog.insts.push(Inst::Split(0, 0));
                Self::emit(left, prog)?;
                let jmp_pc = prog.insts.len();
                prog.insts.push(Inst::Jump(0));
                let right_pc = prog.insts.len();
                Self::emit(right, prog)?;
                let end_pc = prog.insts.len();
                prog.insts[split_pc] = Inst::Split(split_pc + 1, right_pc);
                prog.insts[jmp_pc] = Inst::Jump(end_pc);
            }
            Re::Star(inner) => {
                let start_pc = prog.insts.len();
                prog.insts.push(Inst::Split(0, 0));
                Self::emit(inner, prog)?;
                prog.insts.push(Inst::Jump(start_pc));
                prog.insts[start_pc] = Inst::Split(start_pc + 1, prog.insts.len());
            }
            Re::Plus(inner) => {
                let start_pc = prog.insts.len();
                Self::emit(inner, prog)?;
                prog.insts.push(Inst::Split(start_pc, prog.insts.len() + 1));
            }
            Re::Optional(inner) => {
                let split_pc = prog.insts.len();
                prog.insts.push(Inst::Split(0, 0));
                Self::emit(inner, prog)?;
                prog.insts[split_pc] = Inst::Split(split_pc + 1, prog.insts.len());
            }
            Re::Group(inner) => Self::emit(inner, prog)?,
        }
        Ok(())
    }

    pub fn matches(&self, text: &str) -> bool {
        let bytes = text.as_bytes();
        let mut current_pcs: Vec<usize> = vec![0];
        let mut next_pcs: Vec<usize> = Vec::new();
        let mut seen: HashSet<usize> = HashSet::new();

        for &b in bytes.iter().chain(std::iter::once(&0)) {
            seen.clear();
            next_pcs.clear();

            for &pc in &current_pcs {
                match &self.prog.insts[pc] {
                    Inst::Char(c) => {
                        if *c as u8 == b && pc + 1 < self.prog.insts.len() {
                            self.add_thread(&mut next_pcs, &mut seen, pc + 1);
                        }
                    }
                    Inst::Any => {
                        if b != 0 && pc + 1 < self.prog.insts.len() {
                            self.add_thread(&mut next_pcs, &mut seen, pc + 1);
                        }
                    }
                    Inst::CharClass(ranges) => {
                        let ch = b as char;
                        if b != 0 && ranges.iter().any(|(lo, hi)| ch >= *lo && ch <= *hi) {
                            self.add_thread(&mut next_pcs, &mut seen, pc + 1);
                        }
                    }
                    Inst::Match => return true,
                    Inst::Split(a, c) => {
                        self.add_thread(&mut next_pcs, &mut seen, *a);
                        self.add_thread(&mut next_pcs, &mut seen, *c);
                    }
                    Inst::Jump(target) => {
                        self.add_thread(&mut next_pcs, &mut seen, *target);
                    }
                    _ => {
                        if pc + 1 < self.prog.insts.len() {
                            self.add_thread(&mut next_pcs, &mut seen, pc + 1);
                        }
                    }
                }
            }

            std::mem::swap(&mut current_pcs, &mut next_pcs);
            if current_pcs.is_empty() { return false; }
        }
        false
    }

    fn add_thread(&self, list: &mut Vec<usize>, seen: &mut HashSet<usize>, pc: usize) {
        // 展开所有跳转和分裂,避免递归
        let mut stack = vec![pc];
        while let Some(p) = stack.pop() {
            if seen.insert(p) {
                match &self.prog.insts.get(p) {
                    Some(Inst::Jump(t)) => stack.push(*t),
                    Some(Inst::Split(a, c)) => { stack.push(*c); stack.push(*a); }
                    Some(Inst::Match) => { list.push(p); return; }
                    Some(_) => list.push(p),
                    None => list.push(p),
                }
            }
        }
    }
}

八、性能分析与工程权衡

方法 编译时间 匹配时间 空间复杂度 支持反向引用
Pike VM O(n) O(mn) O(n) 否
回溯(DFA/PCRE 默认) O(n) O(2^n) 最坏 O(n) 是
纯 DFA O(n log n) O(m) O(2^n) 可能 否
混合(RE2/Go) O(n) O(mn) O(n) 否

m = 输入长度, n = 正则表达式长度

Pike VM 的优势:

  1. 确定性时间保证:O(mn) 时间,不会出现回溯的指数爆炸
  2. 线性空间:不会遇到 DFA 的状态爆炸
  3. 安全抗 DoS:不受 ReDoS(正则拒绝服务攻击)威胁
  4. 实现简洁:比 DFA 引擎更易正确实现

Pike VM 的局限:

  1. 不支持反向引用(如 (a+)\1)——这是最难解决的问题,已被计算理论证明不属于正则语言
  2. 最坏情况不如纯 DFA 快
  3. 捕获组信息传递带来额外开销

九、生产级正则引擎的进阶话题

一个真正可用的正则引擎还需要处理以下问题:

1. Unicode 支持

现代正则引擎需要支持 Unicode 字符类(如 \p{L} 匹配任意字母)和字素簇匹配(\X)。实现时需要基于 Unicode 字符数据库生成大范围字符类表。

2. 自动 DFA 加速

RE2 和 regexp2(.NET)使用混合策略:短正则和常见前缀使用 DFA 快速扫描,大段匹配失败时退出回 Pike VM。

3. 前缀提取优化

从正则表达式中提取字面字符串前缀(如 /hello.*world/ 中的 hello),先使用 Aho-Corasick 快速定位候选位置,再用 VM 精确匹配。

4. 跨线程安全

VM 执行引擎本身无状态(指令集不变,线程数据在栈上),天然支持并发匹配。

十、总结

回顾正则表达式引擎的发展历程:

  • 1956 Kleene 证明正则表达式与 FA 等价
  • 1968 Thompson 发表 NFA 构造法(ed 编辑器中的实现)
  • 1973 Thompson 将 NFA 模拟实现为 grep
  • 1986 回溯引擎统治 PCRE(Perl/Python)
  • 1999 Laurantho 发表 "Regular Expression Matching Can Be Simple And Fast",介绍 Pike VM
  • 2007 Russ Cox 发表三篇论文确立 Pike VM 的工业标准地位
  • 2010+ Go 和 RE2 采用 Pike VM,彻底解决 ReDoS 问题

正则引擎的核心矛盾是:表达力 vs 性能 vs 安全性。回溯引擎用牺牲安全性换取表达力,DFA 用可能的状态爆炸换取确定性性能,Pike VM 在两者之间找到了最优平衡点。

当你在下一个项目中选择正则表达式引擎时,记住:如果不需要反向引用,Pike VM 类型(RE2、Go regexp、Rust regex crate)是几乎总是更好的选择。它不仅是"能用",更是工业级系统中安全性的基石——避免了 DoS 可能通过复杂正则表达式被攻击的风险。

参考资源:
- Russ Cox 的三篇经典论文:Regular Expression Matching Can Be Simple And Fast
- Ken Thompson (1968), "Programming Techniques: Regular expression search algorithm"
- regex crate 源码 —— Rust 社区对 Pike VM 的优秀实现

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论
立即
投稿

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部