Взрывное патологическое выражение (время и память)?

Question

Что за патологическое регулярное выражение, которое взрывает многие парсеры (как по времени, так и по памяти)? а какие парсеры? Бонусные баллы указывают на то, что регулярное выражение является более базовым и стандартным, и тем более вероятно, что не злонамеренный пользователь может его невинно придумать. Не стесняйтесь размещать фактическое время и данные памяти, а также версию парсера.

(Кажется, я помню, что чрезмерные утверждения за кадром или (EDIT:) обратное отслеживание в PERL, как говорят, делают это или, по крайней мере, раньше. Что-нибудь еще?)

Answer 1

Адаптировано из первого примера в статье Сопоставление регулярных выражений может быть простым и быстрым (но медленным в Java, Perl, PHP, Python, Ruby, ...) :

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

Что занимает более 40 секунд в моей системе.Тогда сделайте $n++ для экспоненциально возрастающего веселья ...

Answer 2

От Расс Кокса отлично статья : $ perl -e '("a" x 100000) =~ /^(ab?)*$/;'. Это очевидно вызывает segfault. Есть еще в статье.

Answer 3

Я всегда использую это регулярное выражение для сопоставления строк в исходном коде PHP или JavaScript в PHP:

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

И это почти всегда приводит к ошибке на очень длинной строке (подойдет около 50000 символов).