Определить, является ли регулярное выражение экспоненциальным

Question

Эта статья показывает, что существует некоторое регулярное выражение O (2 ^ n) при возврате. Пример (x+x+)+y. При попытке сопоставить строку, такую ​​как xxxx ... p, она на некоторое время возвращается назад, прежде чем выяснить, что она не может соответствовать.

Есть ли способ обнаружить такое регулярное выражение?

спасибо

Answer 1

Если ваш механизм регулярных выражений демонстрирует экспоненциальное поведение во время выполнения для (x + x +) + y, то оно нарушено , поскольку DFA или NFA могут распознать этот шаблон за линейное время:

echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" | egrep "(x+x+)+y"
echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy" | egrep "(x+x+)+y"

оба отвечают сразу.

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

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

Вы должны на самом деле прочитать превосходную серию статей Расса Кокса о реализации регулярных выражений (и патологическом поведении возврата): http://swtch.com/~rsc/regexp/

Чтобы ответить на ваш вопрос о разрешимости: вы не можете. Потому что для * regexpr нет возврата. Каждая реализация имеет свои собственные стратегии для экспоненциального роста их алгоритма в определенных случаях и не распространяется на другие. Здесь может быть одно правило и катастрофическое для него.

UPDATE:

Например, одна реализация может содержать оптимизатор, который может использовать алгебраические преобразования для упрощения регулярных выражений перед их выполнением: (x+x+)+y - это то же самое, что и xxx*y, что не должно быть проблемой для любого средства отслеживания. Но тот же оптимизатор не распознает следующее выражение, и проблема снова возникает. Здесь кто-то описал, как создать регулярное выражение, которое обманывает оптимизатор Perl:

http://perlgeek.de/blog-en/perl-tips/in-search-of-an-exponetial-regexp.html

Answer 2

Нет, я так не думаю, но вы можете использовать эти рекомендации:

• Если он содержит два квантификатора с открытым концом на верхнем уровне и они вложены, то это может быть O (2 ^ n).
• Если он не содержит двух таких квантификаторов, то я думаю, что это не может быть O (2 ^ n).

Квантификаторы, которые могут вызвать это: *, + и {k,}.

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

Answer 3

Вы можете обнаружить и отклонить вложенные повторы, используя синтаксический анализатор регулярных выражений, который соответствует высоте звезды из 1. Я только что написал модуль для вычисления и отклонения начальных высот> 1 с использованием анализатора регулярных выражений из npm.

$ node safe.js '(x+x+)+y'
false
$ node safe.js '(beep|boop)*'
true
$ node safe.js '(a+){10}'
false
$ node safe.js '\blocation\s*:[^:\n]+\b(Oakland|San Francisco)\b'
true

Answer 4

Любое регулярное выражение без обратных ссылок может быть сопоставлено в линейное время, хотя многие движки регулярных выражений в реальном мире так не делают (по крайней мере, многие механизмы регулярных выражений, которые подключены к средам выполнения языка программирования, поддерживают обратные ссылки не переходить на более эффективную модель выполнения, когда нет обратных ссылок).

Нет простого способа узнать, сколько времени потребует регулярное выражение с обратными ссылками.