导致时间和内存消耗过大的病态正则表达式？

Question

什么是导致许多解析器（包括时间和内存）崩溃的病态正则表达式？哪些解析器？标准越基础，非恶意用户使用可能性越大，加分项。可以发布实际的时间和内存数据以及解析器版本。 （我记得在PERL中过多的回溯或向后查找断言会导致这种情况，或者至少曾经如此。还有其他原因吗？）

- smci

---

你在考虑回溯，几乎任何基于NFA的正则表达式引擎都可以被欺骗进入准无限回溯状态，如果你能控制主题和模式。基于DFA的引擎不需要进行回溯，因此它们不会遭受这种陷阱。下一个问题的答案是“因为DFA通常无法支持NFA所支持的功能。” - Ven'Tatsu

Answer 1

本文内容翻译自文章正则表达式匹配可以简单快速（但在Java、Perl、PHP、Python、Ruby等语言中较慢）的第一个示例:

perl -e '$n=29; ("a" x $n) =~ (("a?" x $n).("a" x $n))'

在我的系统上需要40多秒。然后使用$n++进行指数级增长的乐趣...

- Eric Strom

---

每个正则表达式引擎都没有对此进行优化，这很奇怪。将 a?a? 简化为 a{,2} 是如此基础，以至于在课程中都会教授。 - Glenn Maynard

合成的例子，但跨语言比较有用的文章。 - smci

Answer 2

从Russ Cox的精彩文章中得知：$ perl -e '("a" x 100000) =~ /^(ab?)*$/;'。这显然会导致段错误。 文章中还有更多类似的情况。

- MAK

---

Python和GNU grep对此没有问题。re.match(r'^(ab?)*$', 'a'*10000000) - Glenn Maynard

这并没有影响我的perl 5.10.1安装，并且在codepad上运行良好，而该平台使用的是5.8版本。http://codepad.org/hFlqUWk8 - Eric Strom

@Glenn Maynard，GNU grep是基于DFA的，它不会在这个设置上失败，因为这个例子针对的是基于NFA的引擎的常见弱点。 - Ven'Tatsu

@Ven'Tatsu：谢谢，如果您列出哪些工具是基于NFA的，哪些是基于DFA的，那将会很有帮助。 - smci

@ErikHaliewicz，你曲解了我的话。我并没有说所有基于 NFA 的引擎都无法处理这些表达式，只不过这种情况比较常见而已。你是正确的，问题出在回溯上，但我具体回答的是 GNU grep 为什么不会失败。GNU grep 使用 DFA，DFA 通常不需要回溯，因为永远不存在一个备选状态可以回溯到。 - Ven'Tatsu

Answer 3

我经常使用这个正则表达式来匹配 PHP 或 JavaScript 源代码中的字符串：

~'(\\.|[^'])*'|"(\\.|[^"])*"~s

而且它几乎总是在一个非常长的字符串上失败（大约50000个字符长度就足够了）。

- Thai

---

这里使用了 ~ 分隔符，因为它包含两种类型的引号；尝试将其转换为 Python 正则表达式进行测试，但转义让我感到疯狂。有人能够转换它吗？ - smci

我主要使用了Tim Peters的这种方法进行转换，除了s修饰符（点匹配每个字符？）...我怀疑这会使情况变得更糟。 - smci

这个海报提高了您的正则表达式的效率，去看看吧！ - smci