php - 爆炸的病态正则表达式(时间和内存)？

Question

什么是破坏许多解析器(时间和内存)的病态正则表达式？哪些解析器？正则表达式越基础和标准，非恶意用户无意中想出它的可能性就越大。请随意发布实际时间和内存数据以及解析器版本。

(我似乎记得在 PERL 中过度的回顾断言或(编辑:)回溯据说可以做到这一点，或者至少曾经是。还有别的吗？)

Answer 1

改编自文章 Regular Expression Matching Can Be Simple And Fast(but is slow in Java, Perl, PHP, Python, Ruby, ...) 中的第一个示例:

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

这在我的系统上需要 40 多秒。然后执行 $n++ 以指数方式增加乐趣...