Принцип поиска в регулярных выражениях

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

Первое о чём стоит сказать - это то что существует 2 больших механизма поиска совпадений:

1. НКА - недетерминированный конечный автомат, механизм поиска основан на возвратах. Также важной особенностью является то что подвыражения в регулярном выражении проверяются независимо друг от друга. Поскольку НКА управляется регулярным выражением, автор выражения может определять ход дальнейших событий.
2. ДКА - детерминированный конечный автомат, каждый символ в строке проверяется не более одного раза. Т.е. выражение проверяя следующие символы отбрасывает заведомо ложные совпадения и перестает их проверять.

Теперь необходимо определить с каким механизмом имеем дело мы. Для этого существует ряд экспериментов которые помогут нам определить механизм.

Итак вот тесты:

1. Поддерживает ли механизм минимальные квантификаторы? (минимальный квантификатор записывается выражением *? или +? или ??, ? - признак минимального квантификатора)
2. Примените выражение ‼nfa|nfa not‼ к строке "nfa not". Совпала только первое слово "nfa"?
3. Примените выражение ‼X(.+)+X‼ к строке "=XX====================". вы зависли или выражение выполнялось очень долго?

Если на все эти вопросы вы ответили положительно значит перед вами Традиционный механизм НКА, В противном случае скорее всего это или гибрид или ДКА.

Для обоих механизмов поиска существуют общие правила:

• Предпочтение отдаётся более раннему совпадению
• Стандартные квантификаторы * + ? {m,n} работают максимально.

Первое правило гласит о том, что для совпадения не имеет значение где оно было найдено предпочтение получит 1ое совпадение.
Выражение ‼он‼ к фразе "такого конца он не ожидал", приведёт к 2м совпадениям, что может быть весьма не приятно.
Второе правило гласит о том, что квантификатор стремиться захватить максимальное количество совпадений, позже он может отступить, но первоначально будет найдено максимальное количество.
‼[а-я]+а(\s|$)‼ к фразе "такого конца он не ожидал. алая роза". Что произойдет? Группа [а-я] будет совпадать с любым словом в фразе, но квантификатор + готов отступить на столько символов что бы появилось место для символа "а" + добавляется дополнительная проверка (\s|$) что бы "а" стояла именно в конце слова. Так для сова "такого" сначала происходит полное совпадение, далее выражение видит что требуется наличие обязательного символа "а" и квантификатор начинает отступать с "о" на "г", с "г" на "о", с "о" на "к", с "к" на "а", и тогда он обнаруживает в этом слове совпадение "та" но следующего обязательного символа не находится, вместо него там буква "к" поэтому слово "такого" исключается из совпадений.

Как уже говорилось ВОЗВРАТ - краеугольный камень в механизме НКА. Механизм последовательно рассматривает все компоненты, и когда приходится выбирать между вариантами, механизм выбирает 1 вариант и сохраняет другой, что бы к нему можно было вернуться в случае провала первого.
В случае многих выборов механизм работает по принципу "последний пришел первый ушел".

Очень важной частью понимания работы поиска является принцип Максимальных и Минимальных квантификаторов. Это очень важно. И в будущем поможет их более осознано использовать.

1. Во всех механизмах как НКА так и в ДКА используются Максимальные квантификаторы
2. Механизм ДКА не поддерживает Минимальные квантификаторы.

Вот пара примеров по использованию квантификаторов:

И он прокричал: "а ну стой негодник", на что последовал ответ "а ты догони".

Задача найти фразы в кавычках.

Выражение типа ‼".*"‼ вернёт нам немного не то что хочется а именно; ("а ну стой негодник", на что последовал ответ "а ты догони").

Но мы то хотели именно фразы в кавычках. Поэтому можно модифицировать выражение в такое ‼"[^"]*"‼ в результате к нам вернётся 2 совпадения ("а ну стой негодник", "а ты догони")

Точно такого же результата можно было добиться используя минимальные квантификаторы. Выражение типа ‼".*?"‼ вернёт нам точно такие же 2 совпадения ("а ну стой негодник", "а ты догони").

А как быть когда у нас не один символ выступает скобкой а скажем html тег <b></b> здесь символьный класс и максимальный квантификатор уже не помогут. Решением будет использовать минимальный квантификатор. Фраза будет той же самой но с тегами: И он прокричал: <b>"а ну стой негодник"</b>, на что последовал ответ <b>"а ты догони"</b>.

Выражение вида ‼<b>.*?</b>‼ прекрасно справиться с этой задачей.

Но как быть если у нас есть фраза типа И он прокричал: <b>"а ну стой негодник", на что последовал ответ <b>"а ты догони"</b>.

Предыдущее выражение вернёт нам <b>"а ну стой негодник", на что последовал ответ <b>"а ты догони"</b>.,а нас это не устраивает. Что бы найти совпадение в этой фразе придётся постараться. ‼<b>((?!<b>).)*?</b>‼. Здесь используется негативная опережающая проверка. Если не открывающий тег то любой символ.

Можно переделать данное выражение и на максимальный квантификатор. Совпадение не измениться ‼<b>((?!</?b>).)*</b>‼

Описанное выше нужно очень хорошо понимать.

Помимо максимальных и минимальных квантификаторов существует ещё 2 понятия в принципе действия которых необходимо разобраться. Это Атомарная группировка и Захватывающие квантификаторы.
Суть Атомарной группировки сводиться к следующему: При выходе за пределы конструкции все сохраненные состояния удаляться, а весь текст совпавший внутри группировки считается неизменяемой единицей.
Суть Захватывающего квантификатора сводиться к следующему: Квантификатор работает так же как и максимальный, но никогда не отдает своё совпадение для образования общего совпадения.

Говоря о НКА механизме необходимо отметить как осуществляется конструкция выбора. Для НКА - упорядоченный выбор, т.е. механизм выполняет поиск в соответствии с перечисленной конструкцией выбора. Если совпадёт 1ое выражение остальные даже не будут рассматриватья.
В механизме ДКА - конструкция выбора максимальна. Т.е. не зависимо от порядка следования механизм попытается найти максимально длинное совпадение.

Итак оба механизма должны отображать одинаковые совпадения, но приходят они к этому по разному.
Механизм ДКА - более быстрый и не требует особого знания регулярных выражений.
Механизм НКА - можно более точно настроить но при этом требуются более глубокие знания регулярных выражений.
Так же мной упоминались гибриды. Это такие механизмы в которых при отсутствии минимальных квантификаторов и обратных ссылок используется механизм ДКА, а в случае их использования будет применен механизм НКА.