病理性正则表达式爆炸(时间和记忆)? [英] Pathological regex that blows up (time & memory)?

问题描述

什么是病态的正则表达式会炸毁许多解析器(在时间和内存方面)?和哪些解析器?奖励积分越基本和标准的正则表达式，非恶意用户就越有可能天真地想出它.请随意发布实际时间和内存数据以及解析器版本.

What's a pathological regex that blows up many parsers (both in time & memory)? and which parsers? Bonus points the more basic and standard the regex is, and the more likely that a non-malicious user might innocently come up with it. Feel free to post actual time and memory data, and parser version.

(我似乎记得在 PERL 中过多的后视断言或()回溯据说会这样做，或者至少曾经是这样做的.还有别的吗?)

(I seem to remember that excessive lookbehind assertions or ()backtracking in PERL are said to do this, or at least used to be. Anything else?)

推荐答案

改编自文章中的第一个示例 正则表达式匹配可以简单快速(但在 Java、Perl、PHP、Python、Ruby 等中速度较慢):

Adapted from the first example in the article 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++ 以指数级增加乐趣...

Which takes 40+ seconds on my system. Then do $n++ for exponentially increasing fun...

这篇关于病理性正则表达式爆炸(时间和记忆)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！