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

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

Нужно очень хорошо разбираться, как работает поиск, если планируешь использовать что-то более сложное, чем: /\d+/.

Давайте в качестве примера рассмотрим следующую задачу:

У нас есть текст, в котором нужно заменить все кавычки "..." на «ёлочки» «...», которые используются в типографике многих стран.

Например: "Привет, мир" должно превратиться в «Привет, мир». Некоторые страны предпочитают другие кавычки, вроде „Witam, świat!” (польский) или 「你好,世界」 (китайский), но для нашей задачи давайте выберем «...».

Первое, что нам нужно, это найти строки с кавычками, а затем – мы можем их заменить.

Регулярное выражение вроде /".+"/g (кавычка, какой-то текст, другая кавычка) может выглядеть хорошим решением, но это не так!

Давайте это проверим:

let reg = /".+"/g;

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

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

…Как мы видим, регулярное выражение работает не как задумано!

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

Это можно описать, как «жадность – причина всех зол».

Жадный поиск

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

  • Для каждой позиции в строке
    • Искать совпадение на данной позиции
    • Если нет совпадения, переход к следующей позиции

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

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

    Движок регулярного выражения пытается найти его на нулевой позиции исходной строки a "witch" and her "broom" is one, но там – a, так что совпадения нет.

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

  2. Кавычка замечена, после чего движок пытается найти совпадение для оставшегося шаблона. Смотрит, удовлетворяет ли остаток строки шаблону .+".

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

  3. Затем точка повторяется из-за квантификатора .+. Движок регулярного выражения строит совпадение, принимая символы один за другим, пока это возможно.

    …До каких пор? Точке соответствуют любые символы, так что движок остановится только тогда, когда достигнет конца строки:

  4. Тогда он перестанет повторять .+ и попробует найти следующий символ шаблона. Это кавычка ". Но есть проблема: строка закончилась, больше нет символов!

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

    Другими словами, он сокращает совпадение по квантификатору на один символ:

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

    Если бы тут была кавычка, тогда бы работа закончилась, но последний символ – это 'e', так что он не подходит.

  5. …Поэтому движок уменьшает количество повторений .+ на ещё один символ:

    Кавычка '"'не соответствует 'n'.

  6. Движок продолжает отступать: он уменьшает количество повторений '.' пока оставшийся шаблон (в нашем случае '"') не совпадёт:

  7. Совпадение найдено.

  8. Так что первое совпадение: "witch" and her "broom". Дальнейший поиск продолжается с того места, где закончился предыдущий. В оставшейся строке is one нет кавычек, так что совпадений больше нет.

Это определённо не то, что мы ожидали. Но так оно работает.

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

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

В нашей задаче мы хотим другого. Для чего и создан ленивый квантификатор.

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

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

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

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

Регулярное выражение /".+?"/g работает как задумано, оно находит "witch" и "broom":

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

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

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

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

  1. Первый шаг будет таким же: движок находит начало шаблона '"' на 3-ей позиции:

  2. Следующий шаг аналогичен: он найдёт совпадение для точки '.':

  3. А отсюда поиск продолжится по-другому. Из-за того, что у нас включён ленивый режим для +?, движок не будет пытаться найти совпадение для точки ещё раз, оно остановится и попробует найти совпадение для оставшегося шаблона '"' прямо сейчас:

    Если бы на этом месте была кавычка, то поиск бы закончился, но там находится 'i', то есть совпадения нет.

  4. Тогда движок регулярного выражения увеличит количество повторений для точки и попробует ещё раз:

    Опять неудача. Тогда количество повторений будет увеличено ещё и ещё…

  5. …до тех пор, пока совпадение для оставшегося шаблона не будет найдено:

  6. Следующий поиск начнётся с того места, где закончилось текущее совпадение и у нас будет ещё один результат:

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

Ленивый режим включается только для квантификаторов с ?.

Остальные квантификаторы остаются жадными.

Например:

alert( "123 456".match(/\d+ \d+?/g) ); // 123 4
  1. Шаблон \d+ пытается найти столько цифр, сколько возможно (жадный режим), так что он находит 123 и останавливается, потому что следующим символом будет пробел ' '.

  2. Дальше в шаблоне пробел, так что есть совпадение.

  3. Затем идёт \d+?. Квантификатор находится в ленивом режиме, так что он находит одну цифру 4 и проверяет, есть ли совпадение для оставшегося шаблона с этого места.

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

    Ленивый режим ничего не повторяет без необходимости. Шаблон закончился, как и поиск. Мы получаем 123 4.

  4. Следующий поиск начинается с символа 5.

Оптимизации

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

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

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

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

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

В нашем случаем мы можем найти кавычки без использования ленивого режима с помощью регулярного выражения "[^"]+":

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

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

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

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

Движок регулярного выражения заканчивает поиск [^"], когда встречает закрывающую кавычку.

Обратите внимание, что эта логика не заменяет ленивые квантификаторы!

Просто она работает по-другому. Временами на нужен первый вариант, временами – второй.

Давайте посмотрим пример, в котором ленивый квантификатор не справляется, а этот вариант работает правильно.

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

Какое регулярное выражение нам нужно использовать?

Первой мыслью может быть: /<a href=".*" class="doc">/g.

Давайте проверим:

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

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

Регулярное выражение работает. Но давайте посмотрим, что произойдёт, если в тексте будет много ссылок?

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

// Упс! Две ссылки в одном совпадении!
alert( str.match(reg) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

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

Совпадение будет выглядеть так:

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

Давайте изменим шаблон, сделав квантификатор ленивым .*?:

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let 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">

…Но давайте попробуем его на ещё одном тексте:

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

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

Ну вот, ленивый квантификатор нас подвёл. В совпадении находится не только ссылка, но и текст после неё, включая <p...>.

Почему?

Происходит следующее:

  1. Первым делом регулярное выражение находит начало ссылки <a href=".
  2. Затем оно ищет .*?, берёт один символ (лениво!) и проверяет, есть ли совпадение для " (нет).
  3. Затем берёт другой символ для .*?, и так далее… Пока, наконец, не достигнет " class="doc">.

Но с этим есть проблема: это совпадение находится уже за границей ссылки, в другом теге <p>. Что нам не подходит.

Вот как оно выглядит по отношению к исходному тексту:

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

Итак, в данном случае ленивый режим нам не подходит.

Нам нужен шаблон для поиска <a href="...something..." class="doc">, но и с ленивым и с жадным режимами есть проблема.

Правильным вариантом может стать: href="[^"]*". Он найдёт все символы внутри атрибута href до ближайшей следующей кавычки, как раз то, что нам нужно.

Работающий пример:

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

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

Итого

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

Жадный
По умолчанию движок регулярного выражения пытается повторить квантификатор столько раз, сколько это возможно. Например, \d+ получит все возможные цифры. Когда цифры закончатся или он дойдёт до конца строки, движок продолжит искать совпадение для оставшегося шаблона. Если совпадения не будет, он уменьшит количество повторов (отступит) и попробует снова.
Ленивый
Включается с помощью знака вопроса ? после квантификатора. Движок регулярного выражения пытается найти совпадение для оставшегося шаблона перед каждым повторением квантификатора.

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

Задачи

Какое здесь будет совпадение?

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

Результат будет: 123 4.

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

Тогда второй \d+? возьмёт только одну цифру, потому что этого будет достаточно.

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

let reg = /ваше регулярное выражение/g;

let str = `... <!-- My -- comment
 test --> ..  <!----> ..
`;

alert( str.match(reg) ); // '<!-- My -- comment \n test -->', '<!---->'

Нам нужно найти начало комментария <!--. После этого, весь текст до конца комментария -->.

Первой идеей может быть <!--.*?--> – ленивый квантификатор остановит точку прямо перед -->.

Но точка в JavaScript означает «любой символ, кроме новой строки». Так что многострочные комментарии не будут найдены.

Мы можем использовать [\s\S] вместо точки, чтобы найти «всё»:

let reg = /<!--[\s\S]*?-->/g;

let str = `... <!-- My -- comment
 test --> ..  <!----> ..
`;

alert( str.match(reg) ); // '<!-- My -- comment \n test -->', '<!---->'

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

Пример использования:

let reg = /ваше регулярное выражение/g;

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

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

В этой задаче мы предполагаем, что атрибуты тегов не содержат < и > (и в кавычках тоже), это немного упрощает её решение.

Решением будет <[^<>]+>.

let reg = /<[^<>]+>/g;

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

alert( str.match(reg) ); // '<a href="/">', '<input type="radio" checked>', '<b>'
Карта учебника

Комментарии

перед тем как писать…
  • Если вам кажется, что в статье что-то не так - вместо комментария напишите на GitHub.
  • Для одной строки кода используйте тег <code>, для нескольких строк кода — тег <pre>, если больше 10 строк — ссылку на песочницу (plnkr, JSBin, codepen…)
  • Если что-то непонятно в статье — пишите, что именно и с какого места.