正则引擎如何为正则表达式生成NFA？以^(a+)+$为例解析过程

嘿，这个问题问到点子上了！正则转NFA的核心逻辑基本都是基于Thompson构造法，咱们先从通用流程说起，再一步步拆解^(a+)+$的生成过程，保证你能捋清楚。

正则引擎生成NFA一般分两步走：

1. 词法解析与AST构建 #

首先，引擎会把正则表达式拆分成一个个最小的“原子单元”——比如普通字符（a）、量词（+/*/?）、分组（()）、锚点（^/$）这些，然后把它们组合成一棵抽象语法树（AST）。比如^(a+)+$的AST结构大概是：锚点^ → 带+量词的分组 → 带+量词的a → 锚点$。

2. Thompson构造法构建NFA #

有了AST之后，就从叶子节点开始，用Thompson构造法逐步拼接成完整的NFA。核心规则是：

• 单个字符：生成两个状态，起始状态通过一条标记为该字符的边连接到接受状态。比如a的NFA就是：S1 --a--> S2。
• 连接操作（比如ab）：把前一个NFA的接受状态和后一个NFA的起始状态用ε边（空转移，不需要匹配任何字符）连接起来，形成一个连续的流程。
• 选择操作（比如a|b）：新建一个总起始状态，用ε边分别连到a和b的起始状态；再新建一个总接受状态，a和b的接受状态都用ε边连到这个总接受状态。
• 量词操作：
  • *（0或多次）：新建起始和接受状态，起始→ε→原NFA起始，原NFA接受→ε→接受状态，同时原NFA接受→ε→原NFA起始（循环匹配），起始也可以直接→ε→接受状态（匹配0次）。
  • +（1或多次）：和*类似，但起始不能直接连到接受状态，必须至少走一次原NFA，也就是起始→ε→原NFA起始，原NFA接受→ε→原NFA起始（循环），原NFA接受→ε→接受状态。
  • ?（0或1次）：起始→ε→原NFA起始，起始→ε→接受状态，原NFA接受→ε→接受状态。
• 锚点（^/$）：锚点不会直接生成边，而是给状态加上标记——^标记起始状态为“仅在输入开头激活”，$标记接受状态为“仅在输入结尾时才算有效匹配”。

咱们从内到外一步步构建这个正则的NFA：

第一步：构建最内层的a+ #

1. 先做单个a的NFA：S1 --a--> S2
2. 给a加上+量词，按照+的规则：
   • 新建起始状态S0，接受状态S3
   • S0通过ε边连到S1（进入a的匹配）
   • S2通过ε边连回S1（允许重复匹配a，实现“1或多次”）
   • S2通过ε边连到S3（结束a+的单次匹配）
     此时a+的NFA结构是：

   S0 --ε--> S1 --a--> S2 --ε--> S3
               ^         |
               |---------|
                (ε边循环)
   

第二步：给a+加上外层的+，即(a+)+ #

把刚才的a+看作一个整体NFA（记为NFA-A），起始是S0，接受是S3，现在给它加+量词：

1. 新建外层起始状态S_start，临时接受状态S_end_temp
2. S_start通过ε边连到S0（进入第一个a+的匹配）
3. NFA-A的接受状态S3通过ε边连回S0（允许重复整个a+的匹配，实现外层的“1或多次”）
4. S3通过ε边连到S_end_temp（结束一次a+的匹配）
   这一步后，结构变成：

   S_start --ε--> S0 --ε--> S1 --a--> S2 --ε--> S3 --ε--> S_end_temp
                   ^                                 |
                   |---------------------------------|
                    (ε边循环：重复整个a+)
               ^         |
               |---------|
                (ε边循环：a+内部重复)
   

第三步：加上锚点^和$ #

• 给S_start加上^标记：这个状态只能在输入的第一个字符之前被激活，意味着匹配必须从输入开头开始。
• 给S_end_temp加上$标记：只有当输入的所有字符都被读完（指针走到输入末尾）时，这个状态才算有效的接受状态，也就是匹配必须到输入结尾结束。

最终的NFA结构 #

整理一下，最终的NFA包含这些关键状态和边：

• 起始状态：S_start（绑定^）
• S_start --ε--> S0
• S0 --ε--> S1 --a--> S2 --ε--> S3
• S2 --ε--> S1（a+内部的循环）
• S3 --ε--> S0（外层+的循环，重复整个a+）
• S3 --ε--> S_end（绑定$，最终接受状态）

顺便提一句，这个NFA正是导致ReDoS的根源：当输入是一串a后面跟着一个不匹配的字符（比如aaaaa...x），引擎会尝试所有可能的回溯路径——比如先匹配1个a再循环外层+，再匹配2个a循环外层+……直到所有组合都试过，时间复杂度呈指数级增长。

内容的提问来源于stack exchange，提问作者Ogen