算法与数据结构 / regex · Unicode 字符模型与一个自研引擎 / 自研引擎:AST 与两条执行路径 待审核 34 / 36
@vega/parsing/regex · 引擎

自研引擎:AST 与两条执行路径

语法速览 里的写法,本仓库从零实现的 @vega/parsing/regex 基本都支持。它内部分两步:pattern 先 parse 成 AST,再交给两条独立引擎——Pike VM(Thompson NFA,线性时间、抗 ReDoS)与回溯引擎(全功能,支持环视与反向引用)。默认自动派发:能线性就走 Pike,含断言或反向引用才回退到回溯。

1 · 三个视图

同一条 pattern 同时给出三样东西:实际匹配结果与走的引擎、parse 出的 AST,以及 AST 编译成的 Pike 字节码。控制流靠 SplitJmp,捕获靠 Save 写槽位,末尾是 Match

含环视、反向引用或原子组的 pattern 无法用单遍 NFA 线性模拟,Pike 编译期会直接抛错,字节码那栏会说明原因——这正是引擎自动切回溯的判据。字符串值属性 \p{RGI_Emoji} 则连解析都不收,那类多码点序列要用原生 v 模式,见 RGI 序列

图 1-1 · 一条 pattern 的匹配结果、AST 与 Pike 字节码三视图,可强制指定引擎观察派发差异。可改 pattern、flags 与输入,或点预设。

注 · 两条引擎共享同一棵 AST,差别只在执行策略:Pike VM 同时推进所有可能的状态、每个输入字符只扫一遍,因此步数与输入长度成正比;回溯引擎逐条尝试、失败就退回上一个分叉点,遇上嵌套量词会炸开成指数级,那是 灾难性回溯 的主题。解析器本身的两种写法见 parser 对照

2 · 参考文献

  1. Russ Cox. Regular Expression Matching Can Be Simple And Fast. Thompson NFA 与 Pike VM 的原理,本引擎线性路径的依据。swtch.com
  2. Russ Cox. Regular Expression Matching: the Virtual Machine Approach. 字节码指令集与 Split / Jmp / Save 的设计出处。swtch.com
  3. Ecma International. ECMA-262: Pattern Semantics. 匹配语义的规范定义,实现行为的对照基准。tc39.es