正则表达式引擎的实现原理:从 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, 当前输入位置)。每一步:
- 对 CLIST(当前活跃线程)中的每个线程,执行其状态的指令
- 将产生的新线程收集到 NLIST
- 交换 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 的关键优化
-
线程去重:使用
HashSet<pc>确保同一个 PC 不会在同一轮执行中被处理多次,将最坏情况从指数级降低到线性。 -
延迟克隆:使用
Arc<Vec<...>>和 copy-on-write 语义来避免克隆保存状态。 -
Longest Match First:对于左最左最长匹配语义,PC 位置较小的线程优先执行(对应最左匹配)。
-
预编译字符类索引:对于
[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 ¤t_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 的优势:
- 确定性时间保证:O(mn) 时间,不会出现回溯的指数爆炸
- 线性空间:不会遇到 DFA 的状态爆炸
- 安全抗 DoS:不受 ReDoS(正则拒绝服务攻击)威胁
- 实现简洁:比 DFA 引擎更易正确实现
Pike VM 的局限:
- 不支持反向引用(如
(a+)\1)——这是最难解决的问题,已被计算理论证明不属于正则语言 - 最坏情况不如纯 DFA 快
- 捕获组信息传递带来额外开销
九、生产级正则引擎的进阶话题
一个真正可用的正则引擎还需要处理以下问题:
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 的优秀实现

发表评论 取消回复