Детали реализации регулярного выражения

A вопрос, на который я ответил, заставлял меня задаваться вопросом:

Как регулярные выражения реализованы в Python? Какие гарантии эффективности существуют? Является ли реализация "стандартом" или она может быть изменена?

Я думал, что регулярные выражения будут реализованы как DFA, и поэтому они очень эффективны (требуется не более одного сканирования входной строки). Лоуренс Гонсалвес поднял интересный момент, что не все регулярные выражения Python являются регулярными. (Его пример равен r "(a +) b\1", который соответствует некоторому числу a, a b, а затем тому же числу a, что и раньше). Это явно не может быть реализовано с помощью DFA.

Итак, повторим: каковы детали реализации и гарантии регулярных выражений Python?

Было бы неплохо, если бы кто-то мог дать какое-то объяснение (в свете реализации) относительно того, почему регулярные выражения "cat | catdog" и "catdog | cat" приводят к различным результатам поиска в строке "catdog" ", как упоминалось в вопросе на который я ссылался ранее.

Ответ 1

Модуль Python re был основан на PCRE, но перешел к их собственной реализации.

Вот ссылка на C-код.

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

Регулярное выражение и размер текста n
a ⁿ a ⁿ согласующий a ⁿ

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

http://swtch.com/~rsc/regexp/regexp1.html

Ответ 2

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

Сегодня Ф. Лунд (первоначально ответственный за внедрение RE-модуля Python и т.д.), представляя Unladen Swallow в Pycon Italia, упомянул, что одним из направлений, которые они будут изучать, является компиляция регулярных выражений непосредственно в промежуточный код LLVM ( а не их собственный байт-код, который будет интерпретироваться в режиме ad-hoc) - поскольку обычный код Python также скомпилирован в LLVM (в скоро появляющемся выпуске Unladen Swallow), RE и его окружающий код Python могли бы быть оптимизированы вместе, даже довольно агрессивно. Я сомневаюсь, что что-то вроде этого будет очень близко к "готовому к производству" очень скоро, хотя; -).

Ответ 3

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