## Квантификаторы
1. [Жадные и ленивые квантификаторы](https://learn.javascript.ru/regexp-greedy-and-lazy)
### Аннотация
У квантификаторов есть два режима работы:
#### Жадный
По умолчанию движок регулярного выражения пытается повторить квантификатор столько раз, сколько это возможно. Например, `\d+` получит все возможные цифры. Когда цифры закончатся или он дойдёт до конца строки, движок продолжит искать совпадение для оставшегося шаблона. Если совпадения не будет, он уменьшит количество повторов (осуществит возврат) и попробует снова.
> pattern = `/".+"/g`, str = a ***"witch" and her "broom"*** is one
#### Ленивый
Включается с помощью знака вопроса `?` после квантификатора. Движок регулярного выражения пытается найти совпадение для оставшегося шаблона перед каждым повторением квантификатора.
Как мы увидели на примере поиска строк в кавычках, ленивый режим не «панацея» от всех проблем жадного поиска. В качестве альтернативы может выступать «хорошо настроенный» жадный поиск, как в шаблоне `"[^"]+"`.
> pattern = `/".+?"/g`, str = a ***"witch"*** and her ***"broom"*** is one
### Проблематика
На первый взгляд квантификаторы – это просто, но на самом деле это не совсем так.
Нужно очень хорошо разбираться, как работает поиск, если планируем искать что-то сложнее, чем `\d+`.
Давайте в качестве примера рассмотрим следующую задачу:
У нас есть текст, в котором нужно заменить все кавычки `"..."` на «ёлочки» `«...»`, которые используются в типографике многих стран.
Например: `"Привет, мир"` должно превратиться в `«Привет, мир»`. Есть и другие кавычки, вроде `„Witam, świat!”` (польский язык) или `「你好，世界」` (китайский язык), но для нашей задачи давайте выберем `«...»`.
Первое, что нам нужно – это найти строки с кавычками, а затем мы сможем их заменить.
Регулярное выражение вроде /".+"/g (кавычка, какой-то текст, другая кавычка) может выглядеть хорошим решением, но это не так!
Давайте это проверим:
```js run
let regexp = /".+"/g;
let str = 'a "witch" and her "broom" is one';
alert( str.match(regexp) ); // "witch" and her "broom"
```
…Как мы видим, регулярное выражение работает не как задумано!
Вместо того, чтобы найти два совпадения `"witch"` и `"broom"`, было найдено одно: `"witch"` and her `"broom"`.
Причину можно описать, как «жадность – причина всех зол».
## Жадный (greedy) поиск
> a ***"witch" and her "broom"*** is one
Чтобы найти совпадение, движок регулярных выражений работает по следующему алгоритму:
* Для каждой позиции в строке для поиска:
* Попробовать найти совпадение с шаблоном на этой позиции.
* Если нет совпадения, переход к следующей позиции.
Эти общие слова никак не объясняют, почему регулярное выражение работает неправильно, так что давайте разберём подробно, как работает шаблон `".+"`.
1. Первый символ шаблона – это кавычка `"`
Движок регулярного выражения пытается найти его на нулевой позиции исходной строки `a "witch"` and her "broom" is one`, но там – `a`, так что совпадения нет.
Он продолжает: двигается к следующей позиции исходной строки и пытается найти первый символ шаблона там. У него не получается, он двигается дальше и, наконец, находит кавычку на третьей позиции:
2. Кавычка замечена, после чего движок пытается найти совпадение для оставшегося шаблона. Смотрит, удовлетворяет ли остаток строки шаблону `.+"`
В нашем случае следующий символ шаблона: `.` (точка). Она обозначает «любой символ, кроме новой строки», так что следующая буква строки `'w'` подходит.
3. Затем точка повторяется из-за квантификатора `.+.` Движок регулярного выражения добавляет к совпадению один символ за другим
…До каких пор? Точке соответствуют любые символы, так что движок остановится только тогда, когда достигнет конца строки:
4. Тогда он перестанет повторять `.+` и попробует найти следующий символ шаблона. Это кавычка `".` Но есть проблема: строка для поиска закончилась, больше нет символов!
Движок регулярного выражения понимает, что захватил слишком много `.+` и начинает отступать.
Другими словами, он сокращает совпадение по квантификатору на один символ:
Теперь он предполагает, что `.+` заканчивается за один символ до конца строки и пытается сопоставить остаток шаблона для этой позиции.
Если бы тут была кавычка, тогда бы поиск закончился, но последний символ – это `'e'`, так что он не подходит.
5. …Поэтому движок уменьшает количество повторений `.+` ещё на один символ:
Кавычка `'"'` не соответствует `'n'`
6. Движок продолжает возвращаться: он уменьшает количество повторений `'.'`, пока оставшийся шаблон (в нашем случае `'"'`) не совпадёт:
7. Совпадение найдено
8. Так что первое совпадение: `"witch" and her "broom"`. Если у регулярного выражения стоит флаг `g`, то поиск продолжится с того места, где закончился предыдущий. В оставшейся строке `is one` нет кавычек, так что совпадений больше не будет
Это, определённо, не то, что мы ожидали. Но так оно работает.
> В жадном режиме (по умолчанию) квантификатор повторяется столько раз, сколько это возможно
Движок регулярного выражения пытается получить максимальное количество символов, соответствующих `.+`, а затем сокращает это количество символ за символом, если остаток шаблона не совпадает.
В нашей задаче мы хотим другого. И нам поможет ленивый режим квантификатора
## Не жадный или ленивые (lazy) поиск
> a ***"witch"*** and her ***"broom"*** is one
«Ленивый» режим противоположен «жадному». Он означает: «повторять квантификатор наименьшее количество раз».
Мы можем включить его, вставив знак вопроса `'?'` после квантификатора, то есть будет `*?` или `+?` или даже `??` для `'?'`.
Проясним: обычно знак вопроса `?` сам по себе является квантификатором (ноль или один), но, если он добавлен __после другого квантификатора (или даже после самого себя)__, он получает другое значение – он меняет режим совпадения с жадного на ленивый.
Регулярное выражение `/".+?"/g` работает как задумано, оно находит `"witch"` и `"broom"`:
```js run
let regexp = /".+?"/g;
let str = 'a "witch" and her "broom" is one';
alert( str.match(regexp) ); // witch, broom
```
Чтобы лучше понять, что поменялось, давайте рассмотрим процесс поиска шаг за шагом.
1. Первый шаг будет таким же: движок находит начало шаблона `'"'` на 3-ей позиции:
2. Следующий шаг аналогичен: он найдёт совпадение для точки '.':
3. А отсюда поиск продолжится по-другому. Из-за того, что у нас включён ленивый режим для +?, движок не будет пытаться найти совпадение для точки ещё раз, оно остановится и попробует найти совпадение для оставшегося шаблона `'"'` прямо сейчас:
Если бы на этом месте была кавычка, то поиск бы закончился, но там находится 'i', то есть совпадения нет.
4. Тогда движок регулярного выражения увеличит количество повторений для точки и попробует ещё раз:
Опять неудача. Тогда количество повторений будет увеличено ещё и ещё…
5. …До тех пор, пока совпадение для оставшегося шаблона не будет найдено:
6. Следующий поиск начнётся с того места, где закончилось текущее совпадение и у нас будет ещё один результат:
В этом примере мы увидели, как ленивый режим работает для `+?`. Квантификаторы `*?` и `??` работают аналогичным образом – движок регулярного выражения увеличит количество совпадений, только если не сможет найти совпадение для оставшегося шаблона на текущей позиции.
> Ленивый режим включается только для квантификаторов с `?`
Остальные квантификаторы остаются жадными.
### Еще пример greedy vs lazy search
Строка = `"123 456"` и регулярный паттерн `\d+ \d+?` выдаст при поиске по строке следующий результат: `123 4`. Почему?
1. Шаблон `\d+` пытается найти столько цифр, сколько возможно (жадный режим), так что он находит `123` и останавливается, потому что следующим символом будет пробел `' '`
2. Дальше в шаблоне пробел и в строке тоже, так что есть совпадение.
3. Затем идёт `\d+?`. Квантификатор находится в ленивом режиме, так что он находит одну цифру `4` и проверяет, есть ли совпадение для оставшегося шаблона с этого места.
…Но в шаблоне `\d+?` больше ничего нет.
Ленивый режим ничего не повторяет без необходимости. Шаблон закончился, заканчивается и поиск. Мы получаем `123 4`.
### Альтернативный подход реализации ленивого поиска
С регулярными выражениями часто есть несколько путей добиться одного и того же результата.
В нашем случаем мы можем найти кавычки без использования ленивого режима с помощью регулярного выражения `"[^"]+"`:
> a ***"witch"*** and her ***"broom"*** is one
Регулярное выражение `"[^"]+"` получит нужный результат, потому что оно ищет кавычку `"`, за которой следует один или несколько символов «не-кавычек» `[^"]`, а затем – закрывающая кавычка.
Движок регулярного выражения набирает, сколько может `[^"]+` пока не встречает закрывающую кавычку, на которой останавливается.
Обратите внимание, что эта логика не заменяет ленивые квантификаторы!
Просто она работает по-другому. Временами нужен один вариант, временами – другой.
***Давайте посмотрим пример, в котором ленивый квантификатор не справляется, а этот вариант работает правильно.***
Например, мы хотим найти ссылки вида ``, с произвольным `href`.
Какое регулярное выражение нам нужно использовать?
Первой мыслью может быть: `//g`.
Давайте проверим:
```js run
let str = '......';
let regexp = //g;
// Работает!
alert( str.match(regexp) ); //
```
Регулярное выражение работает. Но давайте посмотрим, что произойдёт, если в тексте будет много ссылок?
```js run
let str = '...... ...';
let regexp = //g;
// Упс! Две ссылки в одном совпадении!
alert( str.match(regexp) ); // ...
```
В данном случае мы получили неправильный результат по той же причине, что в примере с `«witches»`. Квантификатор `.*` забирает слишком много символов.
Совпадение будет выглядеть так:
Давайте изменим шаблон, сделав квантификатор ленивым `.*?`:
```js run
let str = '...... ...';
let regexp = //g;
// Работает!
alert( str.match(regexp) ); // ,
```
Теперь кажется, что всё работает правильно. У нас есть два совпадения:
…Но давайте попробуем его на ещё одном тексте:
```js run
let str = '......