Худший Анализ случая для Регулярных выражений

Question

Существуют ли какие-либо инструменты, которые будут принимать определенное регулярное выражение и возвращать сценарий наихудшего случая с точки зрения количества операций, требуемых для определенного числа символов, с которыми сопоставляется регулярное выражение?

Так что дляНапример, учитывая (f|a)oo.*[ ]baz, сколько шагов может пройти движок, чтобы соответствовать 100 символам?

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

Я понимаю, что это будет во многом зависеть от используемого двигателя и реализации - но я не знаю, насколько это распространено.Поэтому, если это характерно для многих языков (делая мой вопрос слишком расплывчатым), я бы особенно заинтересовался Perl и Python.

Answer 1

Отладчик в Regexbuddy показывает, сколько шагов двигатель сделает, чтобы завершить сопоставление или нет в данном примере Подробнее о катастрофическом возврате и отладке регулярных выражений .

PS: Это не бесплатно, но они предлагают 3-месячную гарантию возврата денег.

Answer 2

Обратите внимание, что это зависит от двигателя . Хотя теория регулярных выражений основана на теории прямых автоматов, большинство двигателей не являются строгими переводами этих теорий. По этой причине, например, некоторые двигатели работают в экспоненциальном времени, а строгая обработка NFA - нет.

Answer 3

Вы можете получить то, что ищете, например, используя re.compile с re.DEBUG.См. отличный ответ из Python Hidden Features Вики сообщества для подробного объяснения.