看得见的算法

正则表达式通常被视为一个“黑盒”：你输入规则和文本，它告诉你是否匹配。但内部发生了什么？为什么有时候它会慢得要死？

为了直观地理解 NFA (非确定性有限自动机) 的并行（或回溯）特性，我编写了一个简单的交互式演示。

交互演示

支持: a-z, 0-9, . (任意), |, *, +, ?, ()
NFA 状态图可视化
点击“编译”生成图表

演示说明

  1. 编译：点击“编译并重置”，JS 脚本会将正则表达式转换为 NFA 图。
  2. 初始状态：NFA 从起始节点开始，自动通过所有的 $\epsilon$ (Split) 边，计算出初始的状态集合。
  3. 步进 (Step)：每点击一次“下一步”，引擎读入一个字符。
    • 引擎检查当前集合中所有的状态。
    • 如果某个状态能接受这个字符，就转移到下一个状态。
    • 新的状态再次通过 $\epsilon$ 边扩散。
    • 形成新的状态集合。
  4. 并行特性：你会注意到，在某些时刻（比如匹配 (b|c)* 时），状态集合里可能同时有多个状态。这就好比量子力学中的“叠加态”，NFA 同时在尝试多条路径。

这就是为什么 NFA 引擎（如 RE2）能保证线性时间复杂度的原因：它不需要回溯，它只是维护了一个有限的状态集合。