从零实现一个正则表达式引擎：NFA/DFA构造与匹配算法

日常开发中调用 RegExp 是再普通不过的事，但很少有人关心它内部到底发生了什么。一个正则表达式从字符串变成能高效匹配的自动机，中间要经过词法分析、语法分析、Thompson构造、子集构造、DFA最小化等一系列经典算法。本文用纯前端JavaScript从零实现一个支持 |、*、+、?、.、() 的正则引擎，不依赖任何库，完整展示从模式字符串到DFA匹配的每一步。

一、正则表达式的形式化定义
先把语法规则定清楚。我们支持的文法如下：

text
regex       := alternation
alternation := concat ('|' concat)*
concat      := repeat*
repeat      := atom ('*' | '+' | '?')*
atom        := '(' regex ')' | CHAR | '.'
这是标准的正则文法，alternation 处理选择，concat 处理连接，repeat 处理重复，atom 是基本单元。文法本身是LL(1)的，适合递归下降解析。

二、词法分析：从字符串到Token流
词法分析器的任务是把模式字符串拆成有意义的Token。需要处理转义字符——\. 应该被识别为字面量点号，而不是通配符。

javascript
function tokenize(pattern) {
  const tokens = [];
  let i = 0;
  const isMeta = ch => '|*+?().'.includes(ch);

  while (i < pattern.length) {
    const ch = pattern[i];
    if (ch === '\\') {
      i++;
      if (i >= pattern.length) throw new Error('末尾不能有反斜杠');
      tokens.push({ type: 'CHAR', value: pattern[i] });
      i++;
    } else if (isMeta(ch)) {
      tokens.push({ type: ch });
      i++;
    } else {
      tokens.push({ type: 'CHAR', value: ch });
      i++;
    }
  }
  tokens.push({ type: 'EOF' });
  return tokens;
}
Token类型有三种：CHAR（字面量字符）、元字符（|、*、+、?、(、)、.）、EOF（结束标记）。转义字符在词法阶段就被消解，后续语法分析不需要再处理反斜杠。

三、语法分析：递归下降构建AST
语法分析器直接按照上面的文法写递归下降，每个非终结符对应一个函数。

javascript
function parse(tokens) {
  let pos = 0;
  const peek = () => tokens[pos];
  const next = () => tokens[pos++];
  const expect = type => {
    const tok = next();
    if (tok.type !== type) throw new Error(`期望 ${type}，实际 ${tok.type}`);
    return tok;
  };

  function parseAlternation() {
    let node = parseConcat();
    while (peek().type === '|') {
      next();
      node = { type: 'alternation', left: node, right: parseConcat() };
    }
    return node;
  }

  function parseConcat() {
    const nodes = [];
    while (!['|', ')', 'EOF'].includes(peek().type)) {
      nodes.push(parseRepeat());
    }
    if (nodes.length === 0) return { type: 'empty' };
    return nodes.reduce((left, right) => ({ type: 'concat', left, right }));
  }

  function parseRepeat() {
    let node = parseAtom();
    while (['*', '+', '?'].includes(peek().type)) {
      node = { type: 'repeat', op: next().type, node };
    }
    return node;
  }

  function parseAtom() {
    const tok = peek();
    if (tok.type === '(') {
      next();
      const node = parseAlternation();
      expect(')');
      return node;
    }
    if (tok.type === 'CHAR') { next(); return { type: 'char', value: tok.value }; }
    if (tok.type === '.') { next(); return { type: 'any' }; }
    throw new Error(`意外的 token: ${tok.type}`);
  }

  const ast = parseAlternation();
  if (peek().type !== 'EOF') throw new Error('解析未完成');
  return ast;
}
AST节点有五种：char（字面量）、any（通配符）、concat（连接）、alternation（选择）、repeat（重复）、empty（空串）。其中 concat 通过 reduce 构造左结合的二叉树，保证 abc 被解析为 ((a·b)·c) 而不是 (a·(b·c))——虽然对于连接操作两者语义等价，但统一的结合方向能简化后续处理。

四、Thompson构造法：AST → NFA
Thompson构造法的核心思想是：每个AST节点对应一个NFA片段（fragment），片段有唯一的入口状态和出口状态，片段之间通过ε转移连接。

javascript
class NFA {
  constructor() {
    this.states = 0;
    this.transitions = {};  // { from: { symbol: [to...] } }
    this.start = 0;
    this.accept = new Set();
  }

  addState() { return this.states++; }

  addTransition(from, symbol, to) {
    if (!this.transitions[from]) this.transitions[from] = {};
    if (!this.transitions[from][symbol]) this.transitions[from][symbol] = [];
    this.transitions[from][symbol].push(to);
  }

  static fromAST(ast) {
    const nfa = new NFA();
    const { start, accept } = nfa.build(ast);
    nfa.start = start;
    nfa.accept.add(accept);
    return nfa;
  }

  build(node) {
    switch (node.type) {
      case 'empty': {
        const s = this.addState();
        return { start: s, accept: s };
      }
      case 'char': {
        const s = this.addState(), e = this.addState();
        this.addTransition(s, node.value, e);
        return { start: s, accept: e };
      }
      case 'any': {
        const s = this.addState(), e = this.addState();
        this.addTransition(s, 'ANY', e);
        return { start: s, accept: e };
      }
      case 'concat': {
        const L = this.build(node.left);
        const R = this.build(node.right);
        this.addTransition(L.accept, 'ε', R.start);
        return { start: L.start, accept: R.accept };
      }
      case 'alternation': {
        const s = this.addState(), e = this.addState();
        const L = this.build(node.left);
        const R = this.build(node.right);
        this.addTransition(s, 'ε', L.start);
        this.addTransition(s, 'ε', R.start);
        this.addTransition(L.accept, 'ε', e);
        this.addTransition(R.accept, 'ε', e);
        return { start: s, accept: e };
      }
      case 'repeat': {
        const inner = this.build(node.node);
        const s = this.addState(), e = this.addState();
        this.addTransition(s, 'ε', inner.start);
        this.addTransition(s, 'ε', e);
        if (node.op === '*') {
          this.addTransition(inner.accept, 'ε', inner.start);
          this.addTransition(inner.accept, 'ε', e);
        } else if (node.op === '+') {
          this.addTransition(inner.accept, 'ε', inner.start);
          this.addTransition(inner.accept, 'ε', e);
          // 注意：+ 的 s 不应直接连到 e，需去掉 s→e 这条
          // 修正：+ 的语义是至少一次
        } else if (node.op === '?') {
          this.addTransition(inner.accept, 'ε', e);
        }
        return { start: s, accept: e };
      }
    }
  }
}
这里有一个需要修正的细节：+ 的语义是「至少一次」，所以不能有 s → e 的直接ε转移。上面代码中 + 分支虽然加了 s → e 又试图修正，但逻辑混乱。正确的 + 构造是：

javascript
case 'repeat': {
  const inner = this.build(node.node);
  if (node.op === '*') {
    const s = this.addState(), e = this.addState();
    this.addTransition(s, 'ε', inner.start);
    this.addTransition(s, 'ε', e);
    this.addTransition(inner.accept, 'ε', inner.start);
    this.addTransition(inner.accept, 'ε', e);
    return { start: s, accept: e };
  }
  if (node.op === '+') {
    const s = this.addState(), e = this.addState();
    this.addTransition(s, 'ε', inner.start);
    this.addTransition(inner.accept, 'ε', inner.start);
    this.addTransition(inner.accept, 'ε', e);
    return { start: s, accept: e };
  }
  if (node.op === '?') {
    const s = this.addState(), e = this.addState();
    this.addTransition(s, 'ε', inner.start);
    this.addTransition(s, 'ε', e);
    this.addTransition(inner.accept, 'ε', e);
    return { start: s, accept: e };
  }
}
* 允许零次，所以 s → e 直接连通；+ 要求至少一次，所以 s → e 不存在，必须经过 inner；? 允许零次或一次，s → e 连通，inner 只走一次。

五、子集构造法：NFA → DFA
NFA的ε转移让匹配时存在不确定性——同一个输入可能激活多个状态。子集构造法把NFA的「状态集合」当作DFA的「单个状态」，消除了不确定性。

javascript
function subsetConstruction(nfa) {
  const epsilonClosure = states => {
    const stack = [...states], closure = new Set(states);
    while (stack.length) {
      const s = stack.pop();
      for (const t of (nfa.transitions[s]?.['ε'] || [])) {
        if (!closure.has(t)) { closure.add(t); stack.push(t); }
      }
    }
    return closure;
  };

  const move = (states, symbol) => {
    const result = new Set();
    for (const s of states) {
      for (const t of (nfa.transitions[s]?.[symbol] || [])) result.add(t);
    }
    return result;
  };

  const alphabet = new Set();
  for (const s in nfa.transitions) {
    for (const sym in nfa.transitions[s]) {
      if (sym !== 'ε') alphabet.add(sym);
    }
  }

  const setKey = set => [...set].sort((a, b) => a - b).join(',');
  const hasAccept = set => [...set].some(s => nfa.accept.has(s));

  const startSet = epsilonClosure([nfa.start]);
  const dfaStates = [startSet];
  const stateMap = new Map([[setKey(startSet), 0]]);
  const transitions = {};
  const accept = new Set();
  if (hasAccept(startSet)) accept.add(0);

  const queue = [startSet];
  while (queue.length) {
    const current = queue.shift();
    const currentId = stateMap.get(setKey(current));

    for (const symbol of alphabet) {
      const moved = move(current, symbol);
      if (moved.size === 0) continue;
      const closure = epsilonClosure(moved);
      const key = setKey(closure);

      let targetId;
      if (stateMap.has(key)) {
        targetId = stateMap.get(key);
      } else {
        targetId = dfaStates.length;
        stateMap.set(key, targetId);
        dfaStates.push(closure);
        if (hasAccept(closure)) accept.add(targetId);
        queue.push(closure);
      }

      if (!transitions[currentId]) transitions[currentId] = {};
      transitions[currentId][symbol] = targetId;
    }
  }

  return { states: dfaStates.length, transitions, start: 0, accept };
}
这段代码是引擎的核心。epsilonClosure 用深度优先遍历计算ε闭包，move 计算某个状态集合经过指定符号能到达的状态集合，两者组合构成子集构造的每一步。用一个队列驱动工作列表算法，直到不再产生新的DFA状态。

setKey 把状态集合序列化为字符串作为Map的键，这是子集构造中避免重复状态的标准做法。hasAccept 检查集合中是否包含NFA的接受状态——只要有，对应的DFA状态就是接受状态。

六、DFA匹配引擎
有了DFA，匹配就变成了一次线性扫描。

javascript
function match(dfa, input) {
  let state = dfa.start;
  for (const ch of input) {
    const trans = dfa.transitions[state];
    if (!trans) return false;
    let next = trans[ch];
    if (next === undefined) next = trans['ANY'];
    if (next === undefined) return false;
    state = next;
  }
  return dfa.accept.has(state);
}
ANY 是通配符 . 的转移符号。如果当前状态没有对应字符的转移，就尝试 ANY。两个都没有则匹配失败。扫描结束后，检查最终状态是否在接受集合中。

七、完整代码与测试
把上面的部分串起来：

javascript
function compile(pattern) {
  const tokens = tokenize(pattern);
  const ast = parse(tokens);
  const nfa = NFA.fromAST(ast);
  const dfa = subsetConstruction(nfa);
  return { ast, nfa, dfa };
}

function test(pattern, input) {
  return match(compile(pattern).dfa, input);
}

// 测试
console.log(test('a(b|c)*', 'a'));      // true
console.log(test('a(b|c)*', 'abc'));    // true
console.log(test('a(b|c)*', 'abcb'));   // true
console.log(test('a(b|c)*', 'b'));      // false
console.log(test('a+b', 'aaab'));       // true
console.log(test('a?b', 'b'));          // true
console.log(test('a?b', 'ab'));         // true
console.log(test('a.c', 'abc'));        // true
console.log(test('a.c', 'ac'));         // false
全部通过。

八、可视化NFA与DFA状态转移
调试正则引擎时，能看到自动机的结构比盲猜有效得多。下面这个函数把NFA渲染成文本形式的状态转移表：

javascript
function dumpNFA(nfa) {
  const lines = [];
  lines.push(`起始状态: ${nfa.start}`);
  lines.push(`接受状态: ${[...nfa.accept].join(', ')}`);
  lines.push('转移表:');
  for (const from in nfa.transitions) {
    for (const sym in nfa.transitions[from]) {
      for (const to of nfa.transitions[from][sym]) {
        lines.push(`  ${from} --${sym}--> ${to}`);
      }
    }
  }
  return lines.join('\n');
}

function dumpDFA(dfa) {
  const lines = [];
  lines.push(`起始状态: ${dfa.start}`);
  lines.push(`接受状态: ${[...dfa.accept].join(', ')}`);
  lines.push('转移表:');
  for (const from in dfa.transitions) {
    for (const sym in dfa.transitions[from]) {
      lines.push(`  ${from} --${sym}--> ${dfa.transitions[from][sym]}`);
    }
  }
  return lines.join('\n');
}
以 a(b|c)* 为例，NFA有若干状态，经过子集构造后DFA的状态数通常远少于NFA。你可以直接在浏览器控制台调用 dumpNFA(compile('a(b|c)*').nfa) 观察结构。

九、性能分析与优化方向
当前实现是纯解释执行，每次 compile 都会重新走一遍全部流程。如果要在生产环境中使用，有几个明确的优化方向：

DFA最小化。子集构造产生的DFA可能存在等价状态，用Hopcroft算法可以把状态数压到理论最小。Hopcroft算法的核心是按接受/非接受状态初始划分，然后不断细化划分直到稳定。

状态缓存。同一个模式字符串的编译结果应该缓存起来。用一个 Map<pattern, DFA> 做memoization，避免重复编译。

惰性子集构造。对于大型正则，一次性构造完整DFA可能内存爆炸。惰性DFA（Lazy DFA）在匹配过程中按需计算状态转移，用LRU缓存淘汰不常用的状态。这是RE2和Rust regex库的核心策略。

字符类优化。当前实现把每个字符当作独立的转移符号。对于 [a-z] 这类字符类，应该合并为一个转移符号，否则字母表大小会膨胀到256，子集构造的复杂度急剧上升。

子串匹配支持。当前 match 只做全串匹配。如果要支持子串查找（类似 String.prototype.search），有两种做法：在DFA外面包一层循环，对每个起始位置尝试匹配；或者在NFA层面添加一个 .* 前缀，让引擎自动跳过前导字符。

十、总结
从模式字符串到DFA，中间经历了词法分析、递归下降解析、Thompson构造、子集构造四个阶段。每一步都有明确的数学基础：正则文法定义了语法的边界，Thompson构造给出了从语法树到自动机的构造性证明，子集构造证明了NFA和DFA的等价性。这套流程不仅是正则引擎的实现路径，也是编译原理中自动机理论的经典应用。

代码本身不长，核心逻辑加起来不到200行，但覆盖了编译器前端的大部分基础概念。把这套实现跑通之后，再去看RE2或Rust regex的源码，会发现它们在架构上遵循的是同一套思路，只是在工程细节上做了大量优化——惰性构造、字符类压缩、SIMD加速、内存池管理。理解了这个最小内核，那些优化手段就不再神秘。