Жадные и ленивые квантификаторы в регулярных выражениях

Жадные и ленивые квантификаторы в регулярных выражениях

Здравствуйте!  Продолжаем разговор о квантификаторах в регулярных выражениях, начатый в  прошлом уроке и сегодня рассмотрим что такое жадные квантификаторы и не очень.  На самом деле квантификаторы  хоть с виду очень простая, но местами очень хитрая штука.

И надо очень хорошо понимать, каким образом  происходит поиск.

Давайте для примера разберем вот такой пример  надо  заменить в тексте кавычки вида «…» на «кавычки-ёлочки»: «…».

Для этого надо найти все слова в таких кавычках.

Регулярка может выглядеть примерно  так: /».+»/g.

жадные и ленивые квантификаторы

 

var reg1 = /".+"/g;
var str1 = 'a "bitch" and her "room" is one';

alert( str1.match(reg1) ); // "bitch" and her "room"

То здесь нас ожидает небольшой сюрприз.

Вместо того, чтобы найти два совпадения «witch» и «broom», оно находит одно: «witch» and her «broom».

Это все происходит из-за жадности квантификаторов.

Жадный поиск

Для того чтобы найти совпадение,  обычно используется вот иакой алгоритм:

  • Для позиции в поисковой строке
    • Проверить  есть ли совпадение на данной позиции
    • Сопоставить с ней регулярное выражение, используя квантификаторы.

Это все в общем, давайте разберем все пошагово.

  1. 1-ый символ шаблона – это кавычка «. Движок пытается найти её на 0-й позиции в строке, но там  есть  символ a, поэтому на этой позиции соответствия явно нет. Далее он переходит дальше на  1ю, 2ю позицию в  строке и,  обнаруживает кавычку на 3-й позиции.
  2. После того кавычка была  найдена, далее движок  будет проверять, найдено ли соответствие для остальной части шаблона. В нашем случае следующий символ шаблона это  . (точка). Она находит «любой символ»,  таким образом  буква строки ‘w’ подходит:
  3. Далее «любой символ» повторяется, так как стоит квантификатор .+. Движок регулярных выражений берёт один символ за другим, до тех пор, пока у него это получается.В данном случае это означает «до конца строки»:
  4. Итак, наш  текст закончился,  и движок регулярных выражений больше не сможет найти «любой символ», он закончит повторения для .+ и перейдет к следующему символу шаблона. Следующий символ шаблона – это кавычка. Её также необходимо найти. А тут  просходит следующее  ведь поисковый текст завершился!  И движок понимает, что, наверное, взял  многовато .+ и начинает идти обратно. Другими словами, он сократит текущее совпадение на 1 символ. Это  так называемая называется «фаза возврата». Теперь .+  будет соответствовать почти вся  строка, за исключением 1-го символа, и движок ещё раз пытается подобрать соответствие для остатка шаблона, начиная с оставшейся части строки. Так воь если последний символ строки кавычка ‘»‘, то на этом бы всё и закончилось. Но последний символ ‘e’, так что совпадения нет.
  5. Далее  движок уменьшит число повторений .+ ещё на 1 символ. Кавычка ‘»‘ не  будет совпадать с ‘n’.
  6. Движок продолжит отступать, он уменьшит количество повторений точки ‘.’ до тех пор, пока остаток шаблона, то есть в данном случае кавычка ‘»‘, не совпадет.
  7. Совпадение получено. Дальнейший поиск совпадений не даст.
Читайте также  Паттерны и флаги регулярных выражений

В жадном режиме  движок повторяет квантификатор настолько много раз, пока не будет найдено соответствие.

Таким образом  любой символ .+  будет повторяться максимальное количество раз, что и приведет к длинной строке.

А нам  хотелось,  чтобы каждая строка в кавычках была независимым совпадением? Для этого  нам надо  переключить квантификатор + в «ленивый» режим.

Ленивый режим

Ленивый режим работы квантификаторов –  это противоположность жадному, он дословно означает  «повторять минимальное количество раз».

Для того чтобы включить данный режим просто поставив  знак вопроса ‘?’ после квантификатора: *? или +? или ?? для ‘?’.

Регэксп /».+?»/g работает, как задумано – находит отдельно bitch и room:

var reg1 = /".+?"/g;

var str1 = 'a "bitch" and her "room" is one';

alert( str1.match(reg1) ); // witch, broom

Чтобы в точности понять, как поменялась работа квантификатора, разберём поиск по шагам.

  1. Первый шаг –  кавычка ‘»‘ найдена на 3-й позиции:
  2. Второй шаг – находим произвольный символ ‘.’:
  3. А вот дальше – поскольку стоит ленивый режим работы +, то регэскп не  будет повторять точку (произвольный символ) ещё раз, а остановится на достигнутом и будет  пытаться проверить, есть ли соответствие остальной части шаблона.
  4. Движок  будет увеличивать количество повторений точки на одно и  будет пытаться найти соответствие остатку шаблона ещё раз. Опять осечка. Тогда движок  будет увеличивать количество повторений ещё и ещё…
  5. Только на пятом шаге поисковой движок наконец находит соответствие для остатка паттерна:
  6. Поскольку поиск происходит с флагом g, то он будет  продолжаться с конца текущего совпадения, давая ещё один результат

В примере мы продемонстрировали работу ленивого режима для +?. Квантификаторы +? и ?? ведут себя аналогично.

Читайте также  Классы и спецсимволы регулярных выражений

Следует отметить, что ленивость распространяется только на тот квантификатор, после которого стоит ?.

А вот прочие квантификаторы остаются жадными.

Например:

alert( "678 456".match(/\d+ \d+?/g) ); // 678 4
  1. Шаблон \d+  будет пытаться найти столько цифр, сколько возможно так что он найдет 678 и остановиться, поскольку символ пробела ‘ ‘ не подходит под \d.
  2. Далее в шаблоне пробел, он совпадает.
  3. Далее в шаблоне идёт \d+?. Поскольку квантификатор указан в ленивом режиме, поэтому он найдет цифру 4 и  проверит, есть ли совпадение с остатком шаблона. Но после \d+? в шаблоне ничего не будет.  А поскольку ленивый режим лишний раз квантификатор не  будет повторять.  Так как шаблон завершился, то искать  собственно дальше  нечего.  И мы получим  совпадение 678 4.
  4. Следующий поиск продолжится с 5, но ничего не найдёт.

Итоги

У квантификаторов  есть  2 режима работы:

Жадный
Режим по умолчанию – движок  будет  повторять  его по-максимуму.  А вот когда повторять уже нельзя, например нет больше цифр для \d+, он  будет продолжать  поиск с оставшейся части текста. Если совпадение не найдено – отступит обратно, уменьшив количество повторений.
Ленивый
Если указать после квантификатора символ ? он  будет работать  в ленивом режиме. То есть, он  будет перед каждым повторением проверять совпадение части шаблона на текущей позиции.

Задания

Найти HTML-комментарии

Найдите все HTML-комментарии в тексте:

var re = ..регэксп..

var str = '.. <!-- Мой -- коммент \n тест --> ..  <!----> .. ';

alert( str.match(re) ); // '<!-- Мой -- коммент \n тест -->', '<!---->'

Найти HTML-теги

Создайте регулярное выражение для поиска всех (открывающихся и закрывающихся) HTML-тегов вместе с атрибутами.Пример использования:

var re = /* ваш шаблон */
var str = '<> <a href="/"> <input type="radio" checked> <b>';
alert( str.match(re) ); // '<a href="/">', '<input type="radio" checked>', '<b>'
Плюсануть
Поделиться

Об авторе

admin administrator

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: