Поведение при сопоставлении
Обновлен: Ноябрь 2007
Обработчик регулярных выражений .NET Framework выполняет поиск с возвратом для регулярных выражений и является реализацией традиционной NFA-машины (недетерминированного конечного автомата), аналогично тем, которые используются в Perl, Python, Emacs и Tcl. Это отличает его от более быстрых, но и более ограниченных DFA-машин (детерминированный конечный автомат), предназначенных только для регулярных выражений и используемых в awk, egrep или lex. Это также отличает его от типовых, но более медленных POSIX NFA-машин.
Три типа обработчиков регулярных выражений
В этом разделе представлены общие сведения о преимуществах и недостатках трех типов обработчиков, а также дано объяснение причин, по которым обработчик платформы .NET Framework реализует обычный алгоритм NFA.
DFA-машины работают с линейной скоростью, поскольку для них не требуется поиск с возвратом (и поэтому они никогда не проверяют один и тот же знак дважды). С их помощью можно обнаружить соответствия максимальной длины. Но поскольку DFA-машина поддерживает только ограниченный режим работы, она не способна сопоставлять шаблон с обратными ссылками. Кроме того, она не создает явные выражения и не способна выделять подвыражения.
Обычные NFA-машины работают по так называемым "жадным" алгоритмам сопоставления с использованием поиска с возвратом, проверяя все возможные расширения регулярного выражения в определенном порядке и принимая первое соответствие. Поскольку обычная NFA-машина создает определенное расширение регулярного выражения для успешного сопоставления, она способна находить соответствия для подвыражений и обратных ссылок. Но поскольку обычная NFA-машина выполняет поиск с возвратом, она может анализировать одно и то же место несколько раз, если к данной позиции ведут несколько логических путей. В результате в наихудшем случае работа может замедляться по экспоненте. Поскольку обычная NFA принимает первое найденное соответствие, другие (возможно, более длинные) соответствия могут остаться необнаруженными.
POSIX NFA-машины похожи на обычные NFA-машины, за исключением того, что они продолжают поиск с возвратом до тех пор, пока не будет найдено наиболее длинное совпадение. В результате POSIX NFA-машина работает медленнее обычной NFA-машины, и при использовании POSIX NFA, изменив порядок поиска, невозможно указать предпочтение короткому совпадению вместо более длинного.
Программисты предпочитают обычные NFA-машины, поскольку они превосходят по мощности обычные DFA или POSIX NFA-машины. Несмотря на то, что в наихудшем случае быстродействие NFA-машин понижается, ими можно управлять так, что поиск соответствий будет проходить по линейному или полиномиальному времени. Добиться этого можно с помощью шаблонов, уменьшающих неоднозначности и ограничивающих количество возвратов.
.Возможности обработчика .NET Framework
В обработчик регулярных выражений .NET Framework были включены лучшие функции NFA-машины, а также полный набор структурных элементов, позволяющий программистам управлять процессом поиска с возвратом. Эти структуры можно использовать для ускорения поиска или для выбора предпочтительных расширений.
Другие функциональные возможности обработчика регулярных выражений.
"Отложенные" кванторы: ??, *?, +?, {n,m}?. Они указывают обработчику вести поиск минимального числа повторений в первую очередь. Обычные "жадные" кванторы наоборот пытаются в первую очередь найти наибольшее число повторений.
Положительный поиск (positive lookahead). Позволяет обработчику возвращаться в начальное место в тексте после сопоставления подвыражения. Эта возможность полезна при осуществлении поиска с одной позиции с помощью нескольких шаблонов.
Отрицательный поиск вперед (negative lookahead). Сопоставление выражения выполняется только в том случае, когда не было обнаружено соответствия подвыражения. Это существенно упрощает поиск, поскольку часто бывает проще описать выражения, не соответствующие правилу, чем само правило. (Например, трудно написать выражение для поиска слов, которые не начинаются с "не".)
Условный поиск. Позволяет обработчику вести поиск с использованием более чем одного альтернативного шаблона, в зависимости от результатов сопоставлений предыдущего подвыражения. Это более действенный вид обратной ссылки, позволяющий, например, искать правые скобки только в случае, если были найдены левые.
Не возвращающееся ("жадное") подвыражение. Гарантирует обработчику, что для подвыражения будет верным только первое соответствие, как будто выражение запускалось независимо от содержащего его выражения. Без этой конструкции поиск в большом выражении с использованием поиска с возвратом может изменить поведение подвыражения.
Поиск совпадений справа налево. Иногда требуется вести поиск справа налево вместо обычного поиска слева направо, а также бывает более эффективно начинать поиск с правой части шаблона, а не с левой.
Положительный и отрицательный поиск назад (lookbehind). Работает аналогично поиску вперед. Поскольку обработчик регулярных выражений позволяет выполнять поиск справа налево, к регулярным выражениям можно применять поиск назад без каких-либо ограничений.