爆炸的病理性正则表达(时间和记忆)？

Question

什么是病态正则表达式,炸毁了许多解析器(包括时间和内存)？哪个解析器？奖励指出正则表达式越基本和标准,非恶意用户可能无辜地想出它.随意发布实际时间和内存数据,以及解析器版本.

(我似乎记得在PERL中过多的后视断言或(EDIT :)回溯据说是这样做的,或者至少曾经是这样.还有其他什么吗？)

Answer 1

改编自文章正则表达式匹配可以简单而快速（但在 Java、Perl、PHP、Python、Ruby...）中的第一个示例：

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

在我的系统上这需要 40 多秒。然后享受$n++指数级增长的乐趣……