Очередные подробности реализации выражение

А question that I answered получил мне интересно:Очередные подробности реализации выражение

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

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

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

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

источник

2009-05-09 Tom

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

@Gumbo: Действительно, они ... это своего рода причина для моего вопроса. Мне интересно узнать о конкретной реализации, потому что на самом деле небезопасно предполагать использование DFA (из-за этих дополнительных возможностей). – Tom

Используйте источник, Люк (http://svn.python.org/view/python/trunk/Lib/re.py?view=markup). На самом деле это выглядит достаточно хорошо документированным. –

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

Вот ссылка на C code.

Похоже, что библиотека основана на рекурсивном обратном отслеживании при неправильном пути.

alt text

Регулярное выражение и размер текста п
стоит? ^п^п, совпадающим с ^п

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

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

источник

2009-05-09 23:03:17 Unknown

(Я понимаю, что этот комментарий задерживается) Мне нравится ваше объяснение, кроме того, что я не думаю, что последняя часть верна относительно соответствия «cat | catdog». Используя «cat | catdog», в результате получается «cat», и в результате «catdog | cat» создает «catdog». В сущности, порядок имеет значение. Происходит две вещи. Прежде всего, 'findall' находит только совпадающие совпадения. Поэтому вы не должны ожидать «cat» и «catdog». Во-вторых, если бы я реализовал это, я думаю, что легко сказать, что NFA можно преобразовать в DFA, и поэтому у вас будет «c -> a -> * t * -> d -> o -> * g *", где звездочки обозначают конечное состояние. – Tom

(продолжение ...): Таким образом, «t» является конечным состоянием, и я чувствую, что поиск всегда должен просто возвращать «кошку», потому что это настолько далеко, насколько нужно, чтобы найти совпадение. Тем не менее, ваш ответ был полезным, и я собираюсь принять его (несколько месяцев спустя :-). – Tom

DFA - это не идеальный подход. Соответствие '[ab] * b [ab]^n' требует памяти' O (2^n) 'с помощью DFA, но может выполняться в линейном времени и в памяти с использованием NFA. –

Там нет «гарантирует эффективность» на Python УЭ не больше, чем на любой другой части языка (стандартная библиотека C++ s является единственным стандартом широко распространенный язык я знаю, что пытается установить такие стандарты - но нет стандартов, даже в C++, указывая, что, скажем, умножение двух ints должно занимать постоянное время или что-то в этом роде); и нет никакой гарантии, что большие оптимизации не будут применяться в любое время.

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

источник

2009-05-10 21:01:56

Matching regular expressions with backreferences is NP-hard, который не менее NP-Complete. Это в основном означает, что это так сложно, как любая проблема, с которой вы, вероятно, столкнетесь, и большинство компьютерных ученых считают, что в худшем случае может потребоваться экспоненциальное время.Если бы вы могли сопоставить такие «регулярные» выражения (которые на самом деле не так, в техническом смысле) в полиномиальное время, вы можете выиграть a million bucks.

источник

2009-10-28 04:24:21

Очередные подробности реализации выражение

ответ

Смежные вопросы