Skip to content

Latest commit

 

History

History
342 lines (189 loc) · 22.3 KB

1.3.4.2 GreedyAndLazySearch.md

File metadata and controls

342 lines (189 loc) · 22.3 KB

Квантификаторы

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

Аннотация

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

Жадный

По умолчанию движок регулярного выражения пытается повторить квантификатор столько раз, сколько это возможно. Например, \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 (кавычка, какой-то текст, другая кавычка) может выглядеть хорошим решением, но это не так!

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

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`, так что совпадения нет.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В нашей задаче мы хотим другого. И нам поможет ленивый режим квантификатора

Не жадный или ленивые (lazy) поиск

a "witch" and her "broom" is one

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еще пример 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RegexWithHTMLSearch1

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

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

// Работает!
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

Теперь кажется, что всё работает правильно. У нас есть два совпадения:

RegexWithHTMLSearch2

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

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

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

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

Почему?

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

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

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

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

RegexWithHTMLSearch3

Итак, нужен шаблон для поиска <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 regexp = /<a href="[^"]*" class="doc">/g;

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

Задачи для практики

1) Поиск HTML-комментариев

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

Написать регулярку, чтобы из текста ... <!-- My -- commenttest --> .. <!----> .. получить результат: <!-- My -- commenttest -->', '<!---->'

Итого нам нужно найти комментария <!--...все что угодно...-->:

Решение

2) Поиск HTML-тегов

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

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

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

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

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

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

Решение

<[^<>]+>/

1.3.4.1 Regex Theme | Back To iOSWiki Contents | 1.3.4.3 Regex In Swift Theme Folder