Regex 引擎如何为正则表达式生成 NFA？
How do Regex engines generate NFAs for regular expressions?
你可以看到正则表达式 ^(a+)+$
创建了以下 NFA：
我的问题是：从正则表达式创建这个 NFA 的过程是什么？
他们没有。
大多数正则表达式引擎不创建 NFA，而是通过 回溯。
回溯是一个 re-visiting 你做出的每一个决定的过程，撤销它，并尝试另一个选择直到某些东西起作用，这很快就会变得低效。引擎通常不够智能，无法消除相似的路径，并且某些模式的性能可能呈指数级增长。
可以在 Runaway Regular Expressions: Catastrophic Backtracking 中找到很好的解释。
在输入 aaaaaaaaaaaaX 的 ^(a+)+$ 示例中，引擎将尝试所有组合：
aaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaa a a- ...
aa aaaaaaaaaaa aaaaaaaaaaa- ...
a a aaaa aaaa aa
...很多。
您链接到的 OWASP 文章演示了真正的 denial-of-service 攻击，但解释纯粹是理论上的 - 这并不是攻击的实际运作方式。
可以更好地实现匹配正则表达式：关于该主题的规范文章是 Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)，其中还包含您问题的答案，并解释了如何构建适当的 NFA 并有效地匹配模式。
采用这种方法的一个引擎是 RE2, the regular expression library of golang. RE2 does build a NFA, and its performance is much better in general, but there are trade-offs: 。
例如，RE2 can quickly discover there is no match on ^(((a+)+)+)+$, while other flavors time out.
另请参阅：
- Stack Exchange Network Status - Outage Postmortem - July 20, 2016 - 堆栈溢出是如何因为无辜的外观模式而导致反应迟钝的
\s+$（真的）。
- Backtracking in Regular Expressions - Microsoft Docs（以前称为 MSDN）的一个很好的解释。
你可以看到正则表达式 ^(a+)+$
创建了以下 NFA：
我的问题是：从正则表达式创建这个 NFA 的过程是什么？
他们没有。
大多数正则表达式引擎不创建 NFA，而是通过 回溯。
回溯是一个 re-visiting 你做出的每一个决定的过程，撤销它，并尝试另一个选择直到某些东西起作用，这很快就会变得低效。引擎通常不够智能，无法消除相似的路径，并且某些模式的性能可能呈指数级增长。
可以在 Runaway Regular Expressions: Catastrophic Backtracking 中找到很好的解释。
在输入 aaaaaaaaaaaaX 的 ^(a+)+$ 示例中，引擎将尝试所有组合：
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa- ...
aaaaaaaaaaaaaaaaaaaaaaaa- ...
aaaaaaaaaaaa
...很多。
您链接到的 OWASP 文章演示了真正的 denial-of-service 攻击，但解释纯粹是理论上的 - 这并不是攻击的实际运作方式。
可以更好地实现匹配正则表达式：关于该主题的规范文章是 Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)，其中还包含您问题的答案，并解释了如何构建适当的 NFA 并有效地匹配模式。
采用这种方法的一个引擎是 RE2, the regular expression library of golang. RE2 does build a NFA, and its performance is much better in general, but there are trade-offs:
例如，RE2 can quickly discover there is no match on ^(((a+)+)+)+$, while other flavors time out.
另请参阅：
- Stack Exchange Network Status - Outage Postmortem - July 20, 2016 - 堆栈溢出是如何因为无辜的外观模式而导致反应迟钝的
\s+$（真的）。 - Backtracking in Regular Expressions - Microsoft Docs（以前称为 MSDN）的一个很好的解释。