导致时间和内存爆炸的病态正则表达式？
什么是会让很多解析器崩溃的复杂正则表达式（无论是时间还是内存）？哪些解析器会受到影响？如果这个正则表达式越简单、越常见，越有可能是一个无心的用户无意中写出来的，那就更好了。欢迎分享实际的时间和内存数据，以及解析器的版本。
（我记得过多的回溯检查或（编辑：）在PERL中的回溯会导致这个问题，或者至少以前是这样。还有其他的吗？）
3 个回答
0
我总是在PHP中使用这个正则表达式来匹配PHP或JavaScript源代码里的字符串：
~'(\\.|[^'])*'|"(\\.|[^"])*"~s
但是当字符串特别长的时候（大约50000个字符），这个方法几乎总是会失败。
3
来自Russ Cox的精彩文章：$ perl -e '("a" x 100000) =~ /^(ab?)*$/;'。这段代码似乎会导致程序崩溃。文章中还有更多相关内容。
4
这段内容是改编自一篇文章的第一个例子，文章的标题是《正则表达式匹配可以简单又快速（但在Java、Perl、PHP、Python、Ruby等语言中很慢）》。你可以在这里查看这篇文章：Regular Expression Matching Can Be Simple And Fast。
perl -e '$n=29; ("a" x $n) =~ (("a?" x $n).("a" x $n))'
在我的系统上，这个操作需要超过40秒的时间。然后再执行 $n++，会让这个过程变得更加有趣……