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

Квантификаторы – с виду очень простая, но на самом деле очень хитрая штука.

Необходимо очень хорошо понимать, как именно происходит поиск, если конечно мы хотим искать что-либо сложнее чем /\d+/.

Для примера рассмотрим задачу, которая часто возникает в типографике – заменить в тексте кавычки вида "..." (их называют «английские кавычки») на «кавычки-ёлочки»: «...».

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

Соответствующее регулярное выражение может выглядеть так: /".+"/g, то есть мы ищем кавычку, после которой один или более произвольный символ, и в конце опять кавычка.

Однако, если попробовать применить его на практике, даже на таком простом случае…

var reg = /".+"/g;

var str = 'a "witch" and her "broom" is one';

alert( str.match(reg) ); // "witch" and her "broom"

…Мы увидим, что оно работает совсем не так, как задумано!

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

Это как раз тот случай, когда жадность – причина всех зол.

Жадный поиск

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

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

Это общие слова, гораздо понятнее будет, если мы проследим, что именно он делает для регэкспа ".+".

Первый символ шаблона – это кавычка ".

Движок регулярных выражений пытается сопоставить её на 0-й позиции в строке, но там находится символ a, поэтому на 0-й позиции соответствия явно нет.

Далее он переходит на 1ю позицию в исходной строке и, наконец, обнаруживает кавычку на 2-й позиции:
Кавычка найдена, далее движок проверяет, есть ли соответствие для остальной части паттерна.

В данном случае следующий символ шаблона: . (точка). Она обозначает «любой символ», так что следующая буква строки 'w' вполне подходит:
Далее «любой символ» повторяется, так как стоит квантификатор .+. Движок регулярных выражений берёт один символ за другим, до тех пор, пока у него это получается.

В данном случае это означает «до конца строки»:
Итак, текст закончился, движок регулярных выражений больше не может найти «любой символ», он закончил повторения для .+ и переходит к следующему символу шаблона.

Следующий символ шаблона – это кавычка. Её тоже необходимо найти, чтобы соответствие было полным. А тут – беда, ведь поисковый текст завершился!

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

Иными словами, он сокращает текущее совпадение на один символ:

Это называется «фаза возврата» или «фаза бэктрекинга» (backtracking – англ.).

Теперь .+ соответствует почти вся оставшаяся строка, за исключением одного символа, и движок регулярных выражений ещё раз пытается подобрать соответствие для остатка шаблона, начиная с оставшейся части строки.

Если бы последним символом строки была кавычка '"', то на этом бы всё и закончилось. Но последний символ 'e', так что совпадения нет.
…Поэтому движок уменьшает число повторений .+ ещё на один символ:

Кавычка '"' не совпадает с 'n'. Опять неудача.
Движок продолжает отступать, он уменьшает количество повторений точки '.' до тех пор, пока остаток паттерна, то есть в данном случае кавычка '"', не совпадёт:
Совпадение получено. Дальнейший поиск по оставшейся части строки is one новых совпадений не даст.

Возможно, это не совсем то, что мы ожидали.

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

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

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

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

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

Его можно включить, если поставить знак вопроса '?' после квантификатора, так что он станет таким: *? или +? или даже ?? для '?'.

Чтобы не возникло путаницы – важно понимать: обычно ? сам является квантификатором (ноль или один). Но если он стоит после другого квантификатора (или даже после себя), то обретает другой смысл – в этом случае он меняет режим его работы на ленивый.

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

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

var str = 'a "witch" and her "broom" is one';

alert( str.match(reg) ); // witch, broom

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

Первый шаг – тот же, кавычка '"' найдена на 2-й позиции:
Второй шаг – тот же, находим произвольный символ '.':
А вот дальше – так как стоит ленивый режим работы +, то движок не повторит точку (произвольный символ) ещё раз, а останавливается на достигнутом и пытается проверить, есть ли соответствие остальной части шаблона, то есть '"':

Если бы остальная часть шаблона на данной позиции совпала, то совпадение было бы найдено. Но в данном случае – нет, символ 'i' не равен '"'.
Движок регулярных выражений увиличивает количество повторений точки на одно и пытается найти соответствие остатку шаблона ещё раз:

Опять неудача. Тогда поисковой движок увеличивает количество повторений ещё и ещё…
Только на пятом шаге поисковой движок наконец находит соответствие для остатка паттерна:
Так как поиск происходит с флагом g, то он продолжается с конца текущего совпадения, давая ещё один результат:

В примере выше продемонстрирована работа ленивого режима для +?. Квантификаторы +? и ?? ведут себя аналогично – «ленивый» движок увеличивает количество повторений только в том случае, если для остальной части шаблона на данной позиции нет соответствия.

Ленивость распространяется только на тот квантификатор, после которого стоит ?.

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

Например:

alert( "123 456".match(/\d+ \d+?/g) ); // 123 4

Подшаблон \d+ пытается найти столько цифр, сколько возможно (работает жадно), так что он находит 123 и останавливается, поскольку символ пробела ' ' не подходит под \d.
Далее в шаблоне пробел, он совпадает.
Далее в шаблоне идёт \d+?.

Квантификатор указан в ленивом режиме, поэтому он находит одну цифру 4 и пытается проверить, есть ли совпадение с остатком шаблона.

Но после \d+? в шаблоне ничего нет.

Ленивый режим без необходимости лишний раз квантификатор не повторит.

Так как шаблон завершился, то искать дальше, в общем-то нечего. Получено совпадение 123 4.
Следующий поиск продолжится с 5, но ничего не найдёт.

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

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

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

Альтернативный подход

В данном конкретном случае, возможно искать строки в кавычках, оставаясь в жадном режиме, с использованием регулярного выражения "[^"]+":

var reg = /"[^"]+"/g;

var str = 'a "witch" and her "broom" is one';

alert( str.match(reg) ); // witch, broom

Регэксп "[^"]+" даст правильные результаты, поскольку ищет кавычку '"', за которой идут столько не-кавычек (исключающие квадратные скобки), сколько возможно.

Так что вторая кавычка автоматически прекращает повторения [^"]+ и позволяет найти остаток шаблона ".

Эта логика ни в коей мере не заменяет ленивые квантификаторы!

Она просто другая. И то и другое бывает полезно.

Давайте посмотрим пример, когда нужен именно такой вариант, а ленивые квантификаторы не подойдут.

Например, мы хотим найти в тексте ссылки вида <a href="..." class="doc">, с любым содержанием href.

Какое регулярное выражение для этого подойдёт?

Первый вариант может выглядеть так: /<a href=".*" class="doc">/g.

Проверим его:

var str = '...<a href="link" class="doc">...';
var reg = /<a href=".*" class="doc">/g;

// Сработало!
alert( str.match(reg) ); // <a href="link" class="doc">

А если в тексте несколько ссылок?

var str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
var reg = /<a href=".*" class="doc">/g;

// Упс! Сразу две ссылки!
alert( str.match(reg) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

На этот раз результат неверен.

Жадный .* взял слишком много символов.

Соответствие получилось таким:

          <a href="....................................." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">
        

Модифицируем шаблон – добавим ленивость квантификатору .*?:

var str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
var reg = /<a href=".*?" class="doc">/g;

// Сработало!
alert( str.match(reg) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

Теперь всё верно, два результата:

          <a href="....." class="doc">    <a href="....." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">
        

Почему теперь всё в порядке – для внимательного читателя, после объяснений, данных выше в этой главе, должно быть полностью очевидно.

Поэтому не будем останавливаться здесь на деталях, а попробуем ещё пример:

var str = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
var reg = /<a href=".*?" class="doc">/g;

// Неправильное совпадение!
alert( str.match(reg) ); // <a href="link1" class="wrong">... <p style="" class="doc">

Совпадение – не ссылка, а более длинный текст.

Получилось следующее:

Найдено совпадение <a href=".
Лениво ищем .*?, после каждого символа проверяя, есть ли совпадение остальной части шаблона.

Подшаблон .*? будет брать символы до тех пор, пока не найдёт class="doc">.

В данном случае этот поиск закончится уже за пределами ссылки, в теге <p>, вообще не имеющем отношения к <a>.

Получившееся совпадение:

          <a href="..................................." class="doc">
<a href="link1" class="wrong">... <p style="" class="doc">
        

Итак, ленивость нам не помогла.

Необходимо как-то прекратить поиск .*, чтобы он не вышел за пределы кавычек.

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

Правильный вариант: [^"]*. Этот шаблон будет брать все символы до ближайшей кавычки, как раз то, что требуется.

Рабочий пример:

var str1 = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
var str2 = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
var reg = /<a href="[^"]*" class="doc">/g;

// Работает!
alert( str1.match(reg) ); // null, совпадений нет, и это верно
alert( str2.match(reg) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

Итого

Квантификаторы имеют два режима работы:

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

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

Задачи

Совпадение для /d+? d+/

Что будет при таком поиске, когда сначала стоит ленивый, а потом жадный квантификаторы?

"123 456".match(/\d+? \d+/g) ); // какой результат?

Результат: 123 456.

Ленивый \d+? будет брать цифры до пробела, то есть 123. После каждой цифры он будет останавливаться, проверять – не пробел ли дальше? Если нет – брать ещё цифру, в итоге возьмёт 123.

Затем в дело вступит \d+, который по-максимуму возьмёт дальнейшие цифры, то есть 456.

Различие между "[^"]" и ".?"

Регулярные выражения "[^"]*" и ".*?" – при выполнении одинаковы?

Иначе говоря, существует ли такая строка, на которой они дадут разные результаты? Если да – дайте такую строку.

Они очень похожи и, да, почти одинаковы. Оба ищут от одной кавычки до другой.

Различие здесь в символе точка '.'. Как мы помним, точка '.' обозначает любой символ, кроме перевода строки.

А [^"] – это *любой символ, кроме кавычки '"'.

Получается, что первый регэксп "[^"]*" найдёт закавыченные строки с \n внутри, а второй регэксп ".*?" – нет.

Вот пример:

alert( '"многострочный \n текст"'.match(/"[^"]*"/) ); // найдёт

alert( '"многострочный \n текст"'.match(/".*?"/) ); // null (нет совпадений)

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

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

          var re = ..ваш регэксп..

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

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

Нужно найти начало комментария .

С первого взгляда кажется, что это сделает регулярное выражение  – квантификатор сделан ленивым, чтобы остановился, достигнув -->.

Однако, точка в JavaScript – любой символ, кроме конца строки. Поэтому такой регэксп не найдёт многострочный комментарий.

Всё получится, если вместо точки использовать полностю «всеядный» [\s\S].

Итого:

var re = /<!--[\s\S]*?-->/g;

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>'

В этой задаче можно считать, что тег начинается с <, заканчивается > и может содержать внутри любые символы, кроме < и >.

Но хотя бы один символ внутри тега должен быть: <> – не тег.

Начнём поиск с <, затем один или более произвольный символ, но до закрывающего «уголка»: .+?>.

Проверим, как работает этот регэксп:

var re = /<.+?>/g;

var str = '<> <a href="/"> <input type="radio" checked> <b>';

alert( str.match(re) ); // <> <a href="/">, <input type="radio" checked>, <b>

Результат неверен! В качестве первого тега регэксп нашёл подстроку <> <a href="/">, но это явно не тег.

Всё потому, что .+? – это «любой символ (кроме \n), повторяющийся один и более раз до того, как оставшаяся часть шаблона совпадёт (ленивость)».

Поэтому он находит первый <, затем есть «всё подряд» до следующего >.

Первое совпадение получается как раз таким:

          <.............>
<> <a href="/"> <input type="radio" checked> <b>
        

Правильным решением будет использовать <[^>]+>:

var re = /<[^>]+>/g

var str = '<> <a href="/"> <input type="radio" checked> <b>';

alert( str.match(re) ); // <a href="/">, <input type="radio" checked>, <b>

Это же решение автоматически позволяет находится внутри тега символу \n, который в класс точка . не входит.

Карта учебника