Обнаружьте, если regexp экспоненциален
Это шоу статьи, что существует некоторый regexp, который является O (2^n) при отслеживании в обратном порядке. Пример (x+x+)+y. Когда попытка соответствовать строке как xxxx.. p это собирающийся отслеживать в обратном порядке некоторое время перед числом это, что это не могло соответствовать.
Существует ли способ обнаружить такой regexp?
спасибо
3 ответа
Если ваш механизм регулярных выражений демонстрирует экспоненциальное поведение времени выполнения для (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. Каждая реализация имеет свои собственные стратегии для работы с экспоненциальным ростом своего алгоритма для одних случаев и не распространяется на другие. Одно правило может быть подходящим для здесь и катастрофическим для там.
ОБНОВЛЕНИЕ:
Например, одна реализация может содержать оптимизатор, который может использовать алгебраические преобразования для упрощения регулярных выражений перед их выполнением: (x + x +) + y то же самое a xxx * y , что не должно быть проблемой для любого бэктрекера. Но тот же оптимизатор не распознал бы следующее выражение, и проблема снова возникла. Здесь кто-то описал, как создать регулярное выражение, обманывающее оптимизатор Perl:
http://perlgeek.de/blog-en/perl-tips/in-search-of-an-exponetial-regexp.html
Нет, я так не думаю, но вы можете использовать следующие рекомендации:
- Если он содержит два квантификатора, которые являются открытыми на верхнем уровне, и они вложены, тогда это может быть O (2 ^ n).
- Если он не содержит двух таких кванторов, я думаю, это не может быть O (2 ^ n).
Кванторы, которые могут вызвать это: * , + и {k,} .
Также обратите внимание, что сложность вычисления регулярного выражения в наихудшем случае может сильно отличаться от сложности для типичных строк и что сложность зависит от конкретного механизма регулярных выражений.
Любой регекс без обратных ссылок можно подобрать за линейное время, хотя многие регексовые движки в реальном мире так не делают (по крайней мере, многие регексовые движки, подключенные к среде выполнения языка программирования, поддерживают обратные ссылки и не переключаются на более эффективную модель выполнения, когда обратных ссылок нет).
Не существует простого способа узнать, сколько времени будет потреблять regex с обратными ссылками.