Регулярное выражение PCRE с экспоненциальным временем работы

Question

Реализация регулярного выражения с использованием рекурсивного обратного трассировки может в некоторых случаях демонстрировать экспоненциальное время работы.

Я пытаюсь найти такое патологическое регулярное выражение для механизма PCRE.

Я пробовал несколько регулярных выражений, которые, как известно, экспоненциальны для регулярных выражений Perl (например, this one), но ни один из них не показывал экспоненциальное время выполнения с PCRE в моих тестах.

Answer 1

В ваших тестах ожидалось, что все регексы не сработают? И когда они потерпели неудачу, вы точно поняли почему? Возможно, совпадения не соответствуют , потому что двигатель regex обнаружил чрезмерное обратное отслеживание. Я не знаю, если это когда-нибудь случится, но попробовать регулярное выражение, которое должно добиться успеха, как этот:

(?i)lorem(?:.|\s)*pri\. 

Использование RegexBuddy, я применил, что регулярное выражение в первом абзаце текста ниже, и в нем подчеркивается целый абзац как и ожидалось. Когда я удалил период в конце абзаца, подсветка погасла, и отладчик сказал, что он отказался после миллиона операций. Не удивительно, но когда я положил период назад и добавил второй абзац, он все равно не удался - слишком много назад.

---

Lorem Ipsum tritani impedit civibus е ПОИ, legimus antiopam нет СЕПГ кво ID everti forensibus maiestatis. Vim ad intellegat следовательно. Te dicam препятствует тому, что есть. Usu prompta alterum conteses no, ut esse fabellas splendide pri.

Ne utroque nominavi moderatius qui, ius at suas velit nihil, vidit blandit facili pri ut. Ad vel offendit reprehendunt, mea ex quem ipsum complectitur. Veri cetero feugait cu usu, в dolor corpora adolescens vim, at sit voluptua placerat sadipscing. Minim admodum compam eos ut, vix ut movet causae tractatos, in pro dicat dicta dolores. Impetus praesent eum no.