22 серпня 2023 р.

Жадібні та ліниві квантифікатори

На перший погляд, квантифікатори не викликають питань, але насправді все не так просто.

Нам варто добре розуміти як працює пошук, якщо ми плануємо розглядати щось складніше за /\d+/.

Візьмемо за приклад наступну задачу.

Ми маємо текст та хочемо замінити всі лапки "..." на французькі лапки: «...». Їм віддають перевагу у типографії у багатьох країнах.

Наприклад: "Hello, world" має перетворитись на «Hello, world». Існують й інші види лапок, як-то „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".

Про це можна сказати “жадібність – причина всіх бід”.

Жадібний пошук

Аби знайти збіг, рушій регулярних виразів використовує наступний алгоритм:

Для кожної позиції в рядку
- Спробувати виявити збіг на цій позиції.
- Якщо збігу немає, перейти до наступної позиції.

Ці загальні фрази не пояснюють, чому регулярний вираз працює неправильно, тож розберемо, як пошук працює для шаблону ".+".

Першим символом шаблону є одна з лапок ".

Рушій регулярних виразів намагається знайти його на нульовій позиції вихідного рядку a "witch" and her "broom" is one, але бачить a, тож вважає, що збігу немає.

Йдемо далі: бере наступну позицію рядку та намагається на ній знайти перший символ шаблону, знову невдача, але, нарешті, необхідний символ знаходиться на третій позиції:
Першу з лапок виявлено, після цього рушій намагається знайти збіг для решти шаблону. Він намагається зрозуміти, чи відповідає решта рядка .+".

В нашому випадку, наступний символ шаблону – це . (крапка). Він вказує на “будь-який символ, за винятком символу нового рядку”, тож наступна літера рядку 'w' підходить під опис:
Після цього, дія крапки повторюється через наявність квантифікатору .+. Рушій регулярних виразів додає до збігу символи один за одним.

…До якого моменту? Крапка приймає усі символи, таким чином зупиняючись тільки досягнувши кінця рядку:
Тепер рушій завершив повтори .+ та намагається знайти наступний символ шаблону – другу закриваючу лапку ". Але виникає проблема: рядок закінчився, символів більше немає!

Рушій регулярних виразів розуміє, що взяв забагато .+ та починає повернення.

Іншими словами, він скорочує збіг для квантифікатора по одному символу:

Після цього, рушій припускає, що .+ завершується одним символом раніше кінця рядку та намагається знайти збіг для решти шаблону, починаючи з тієї позиції.

Якби друга з лапок була на цьому місці, то пошук завершився б, але останній символ 'e' не відповідає цілі пошуку.
…Тому рушій зменшує кількість повторів .+ на ще один символ:

Друга закриваюча лапка '"' не співпадає з 'n'.
Рушій продовжує процес повернення: число повторів '.' зменшується доти, доки решта шаблону (в цьому випадку, '"') не збігається:
Збіг знайдено.
Отож, першим збігом буде:“witch” and her "broom". Якщо регулярний вираз має прапорецьpattern:g, тоді пошук продовжиться з кінця першого збігу. Решта рядкуsubject:is one` не містить лапок, тож інших збігів не буде.

Напевно, це не те, чого ми очікували, але так вже воно працює.

В жадібному режимі (типово) квантифікований символ повторюється максимально можливу кількість разів.

Рушій регулярного виразу додає до збігу всі можливі символи для .+, а потім зменшує результат посимвольно, якщо решта шаблону не збігається.

Наша задача потребує іншого підходу. Тут може стати в нагоді лінивий режим.

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

Лінивий режим квантифікаторів є протилежним до жадібного режиму. Його алгоритм: “повторювати мінімальну кількість разів”.

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

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

Регулярний вираз /".+?"/g працюватиме, як потрібно: він знайде "witch" та "broom":

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

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

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

Аби чітко побачити різницю, відслідкуємо процес пошуку покроково.

Перший крок той самий: знаходимо початок шаблону '"' на третій позиції:
Наступний крок теж подібний: рушій знаходить збіг для крапки '.':
З цього моменту пошук йде іншим шляхом. Для +? включений лінивий режим, тож тепер рушій більше не намагається знайти збіг для крапки, зупиняється та намагається знайти збіг для решти шаблону '"':

Якби на цьому місці була остання з лапок, тоді пошук закінчився б, але бачимо 'i', тож збігу немає.
Далі, рушій регулярних виразів збільшує кількість повторів для крапки та ще раз проводить пошук:

Знову невдача, тож кількість повторів крок за кроком збільшується…
…До моменту знаходження збігу для решти шаблону:
Наступний пошук починається з кінця поточного збігу та приносить ще один результат:

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

Лінивий режим можна включити лише за допомогою ?.

Інші квантифікатори залишаються жадібними.

Для прикладу:

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

Шаблон \d+ намагається додати в збіг якомога більше цифр (жадібний режим), тож він знаходить 123 та зупиняється, тому що наступним йде пробіл ' '.
Далі в шаблоні працює пробіл, відбувається збіг.
Після цього, маємо \d+?. Квантифікатор в лінивому режимі, тож він знаходить одну цифру 4 та, починаючи з цієї позиції, переходить до перевірки на збіг для решти шаблону.

…Але після \d+? в шаблоні нічого не залишилось.

Лінивий режим не повторює нічого без потреби. Шаблон завершився, а з ним і наша робота. Ми знайшли збіг 123 4.

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

Але, для розуміння принципу побудови та роботи регулярних виразів, нам все це знати не обов’язково. Вони використовуються виключно внутрішньо для оптимізації.

Складні регулярні вирази погано піддаються оптимізації, тож пошук працюватиме саме так, як описано вище.

Інший підхід

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

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

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

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

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

Регулярний вираз "[^"]+" дає правильні результати, бо шукає першу з лапок '"', за якою слідують один чи більше символів (не лапок) [^"] та друга з лапок в кінці.

Коли рушій регулярних виразів шукає [^"]+, він припиняє повторення, як тільки зустрічає другу з лапок, на цьому все.

Зверніть увагу, цей спосіб не замінює ліниві квантифікатори!

Він просто інший. Різні ситуації потребують різні підходи.

Розглянемо приклад, в якому ліниві квантифікатори помиляються, на відміну від другого варіанту.

Скажімо, ми хочемо знайти посилання форми <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”. Квантифікатор .* бере забагато символів.

Збіг виглядає наступним чином:

          <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 regexp = /<a href=".*?" class="doc">/g;

// Працює!
alert( str.match(regexp) ); // <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 regexp = /<a href=".*?" class="doc">/g;

// Хибна відповідь!
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

Тепер він не працює, як ми хотіли. Збіг не обмежується посиланням, а містить також купу тексту, разом з <p...>.

Чому?

Ось процес виконання:

Спочатку, регулярний вираз знаходить початок посилання <a href=".
Далі, він шукає .*?: бере один символ (ліниво!), перевіряє наявність збігу для " class="doc"> (немає).
Після того, перевіряє наступний символ відносно .*?, і так далі… доки він нарешті доходить до " class="doc">.

Але ось де проблема: він вже вийшов поза посилання <a...> в інший тег <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 regexp = /<a href="[^"]*" class="doc">/g;

// Працює!
alert( str1.match(regexp) ); // null, збігів немає, все правильно
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

Підсумки

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

Жадібний: Типово рушій регулярних виразів намагається повторити квантифікований символ максимально можливу кількість разів. Для прикладу, \d+ обирає всі можливі цифри. Коли продовжити цей процес неможливо (більше немає цифр/кінець рядку), тоді продовжується пошук збігу для решти шаблону. Якщо збігу немає, він зменшує кількість повторень (повертається) та пробує наново.
Лінивий: Включається знаком питання ? після квантифікатору. Рушій намагається знайти збіг решти шаблону перед кожним повторенням квантифікованого символу.

Як бачимо, лінивий режим не є “панацеєю” від жадібного пошуку. Як альтернативу розглядають “добре налаштований” жадібний пошук, з виключенням, як в шаблоні "[^"]+".

Завдання

Збіг для /d+? d+?/

Який результат ми отримаємо?

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

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

Для початку, лінивий \d+? намагається взяти мінімальну можливу кількість цифр, але він має дійти до пробілу, тож обирається 123.

Далі, другий \d+? обере лише одну цифру, бо цього достатньо.

Знайти HTML коментарі

Знайти всі HTML коментарі в тексті:

          let regexp = /ваш регулярний вираз/g;

let str = `... <!-- Мій -- коментар
 test --> ..  <!----> ..
`;

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

Нам потрібно знайти початок коментарю .

Прийнятним є варіант  – лінивий квантифікатор зупиняє крапку (будь-який символ, за винятком символу нового рядку) прямо перед -->. Нам також треба додати прапорець s, аби крапка включала символи нового рядку.

Інакше коментарі на кілька рядків не знаходитимуться:

let regexp = /<!--.*?-->/gs;

let str = `... <!-- Мій -- коментар
 test --> ..  <!----> ..
`;

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

Знайти 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>'

Тут ми припускаємо, що атрибути тегу не містять < та > (внутрішні лапки) для спрощення задачі.

Відповідь: <[^<>]+>.

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

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

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

Навчальна карта

Коментарі

прочитайте це, перш ніж коментувати…