Регулярний вираз

В програмуванні, регулярний вираз (від англ. regular expression, скорочено regex або regexp, а іноді ще й називають rational expression)[1][2] — це рядок, що описує або збігається з множиною рядків, відповідно до набору спеціальних синтаксичних правил. Вони використовуються в багатьох текстових редакторах та допоміжних інструментах для пошуку та зміни тексту на основі заданих шаблонів. Багато мов програмування підтримують регулярні вирази для роботи з рядками. Наприклад, Perl та Tcl мають потужний механізм для роботи, вбудований безпосередньо в їхній синтаксис. Завдяки набору утиліт (разом з редактором sed та фільтром grep), що входили до складу дистрибутивів UNIX, регулярні вирази стали відомими та поширеними.

Базові принципи

Регулярні вирази базуються на теорії автоматів та теорії формальних мов. Ці розділи теоретичної кібернетики займаються дослідженням моделей обчислення (автомати) та способами описання та класифікації формальних мов.

Регулярний вираз (часто називається шаблон) є послідовністю, що описує множину рядків. Ці послідовності використовують для точного описання множини без переліку всіх її елементів. Наприклад, множина, що складається із слів «грати» та «ґрати», може бути описана регулярним виразом «[гґ]рати». В більшості формалізмів, якщо існує регулярний вираз, що описує задану множину, тоді існує нескінченна кількість варіантів, які описують цю множину^[джерело?].

Синтаксис

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

Представлення символів

Звичайні символи (літерали) і спеціальні символи (метасимволи)

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

Більшість символів у регулярному виразі представляють самі себе, за винятком спеціальних символів (метасимволів) [ ] \ ^ $ . | ? * + ( ) { }, яким може передувати символ \ (зворотна коса риска), котрий робить метасимволи «екранованими», «захищеними» для представлення, відображення їх самих як символів тексту. Можна екранувати деяку послідовність символів, розмістивши її між \Q і \E.

Приклад	Відповідність
a\.?	a. або a
a\\\\b	a\\b
a\[F\]	a[F]
\Q+-*/\E	+-*/

Аналогічно можуть бути представлені інші спеціальні символи (набір символів, що вимагають екранування, може відрізнятися залежно від конкретної реалізації). Частина символів, які в тій або іншій реалізації не вимагають екранування (наприклад, кутові дужки < >), можуть бути екрановані з міркувань зручності читання.

Залежно від інтерпретатора регулярних виразів, метасимволи «?», «+», «{», «|», «(», та «)» можуть втрачати своє спеціальне значення, замість цього слід вживати «\?», «\+», «\{», «\|», «\(», та «\)».

Будь-який символ

Метасимволу . (крапка) відповідає довільний символ, окрім символу нового рядка (в деяких реалізаціях).

Символьні класи (набори символів)

Набір символів у квадратних дужках [ ] називається символьним класом і дозволяє вказати інтерпретаторові регулярних виразів, що на даному місці в рядку може стояти один із перерахованих символів.

Зокрема, [абв] задає можливість появи в тексті одного із трьох зазначених символів, а [1234567890] задає відповідність одній із цифр. Можливе зазначення діапазонів символів: наприклад, [0-9].

Для включення усіх символів українського алфавіту можна використовувати [Є-ЯҐ], [а-їґ].[3]

Якщо потрібно вказати символи, які не входять у зазначений набір, то використовують символ ^ усередині квадратних дужок, наприклад, [^0-9] означає будь-який символ, крім цифр.

Додавання в набір спеціальних символів шляхом екранування символом «\» — найпростіший спосіб. Однак сучасні регулярні вирази успадковують також і традиційний підхід — див. Традиційні регулярні вирази.

Деякі символьні класи можна замінити спеціальними метасимволами:

Символ	Опис
\d	Відповідає цифрі. Еквівалентно [0-9]
\D	Відповідає нецифровому символу. Еквівалентно [^0-9]
\s	Відповідає будь-якому пробільному символу. Еквівалентно [ \f\n\r\t\v]
\S	Відповідає будь-якому непробільному символу. Еквівалентно [^ \f\n\r\t\v]
\w	Відповідає будь-якому літерному символу, цифровому й знаку підкреслення. Еквівалентно [[:word:]]
\W	Відповідає будь-якому символу, крім літерного символу, цифрового або підкреслення. Еквівалентно [^[:word:]]

Позиція всередині рядка

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

Представлення	Позиція	Приклад	Відповідність
^	Початок рядка	^a	aaa aaa
$	Кінець рядка	a$	aaa aaa
\b	Межа слова	a\b	aaa aaa
		\ba	aaa aaa
\B	Не межа слова	\Ba\B	aaa aaa
\G	Попередній успішний пошук	\Ga	aaa aaa (пошук зупинився на 4-й позиції — там, де не знайшлося a)

Квантифікація (пошук послідовностей)

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

Представлення	Кількість повторень	Приклад	Відповідність
{n}	Рівно n разів	colou{3}r	colouuur
{m,n}	Від m до n включно	colou{2,4}r	colouur, colouuur, colouuuur
{m,}	Не менше m	colou{2,}r	colouur, colouuur, colouuuur і т.д.
{,n}	Не більше n	colou{,3}r	color, colour, colouur, colouuur

Представлення	Кількість повторень	Еквівалент	Приклад	Відповідність
*	Нуль або більше	{0,}	colou*r	color, colour, colouur і т.д.
+	Одне або більше	{1,}	colou+r	colour, colouur і т.д. (але не color)
?	Нуль або одне	{0,1}	colou?r	color, colour

Часто використовується послідовність .* для позначення будь-якої кількості будь-яких символів між двома частинами регулярного виразу.

Символьні класи в поєднанні із квантифікаторами дозволяють установлювати відповідності з реальними текстами. Наприклад, колонками цифр, телефонами, поштовими адресами, елементами HTML-розмітки й ін.

Якщо символи { } не утворюють квантифікатор, їхнє спеціальне значення ігнорується.

Жадібна й ледача квантифікація

Приклад використання жадібних і ледачих виразів

Вираз (<.*>) відповідає рядку, що містить декілька тегів HTML-розмітки, цілком.

<p><b>Вікіпедія</b> - вільна енциклопедія, у якій <i>кожен</i> може змінити або доповнити будь-яку статтю</p>.

Щоб виділити окремі теги, можна застосувати ледачу версію цього виразу: (<.*?>) Їй відповідає не весь показаний вище рядок, а окремі теги (виділені кольором):

<p><b>Вікіпедія</b> - вільна енциклопедія, у якій <i>кожен</i> може змінити або доповнити будь-яку статтю</p>.

У деяких реалізаціях квантифікаторам у регулярних виразах відповідає максимально довгий рядок із можливих (квантифікатори є жадібними, англ. greedy). Це може стати значною проблемою. Наприклад, часто очікують, що вираз (<.*>) знайде в тексті теги HTML. Однак, якщо в тексті є більше одного HTML-тегу, то цьому виразу відповідає цілком рядок, що містить множину тегів.

<p><b>Вікіпедія</b> - вільна енциклопедія, у якій <i>кожен</i> може змінити або доповнити будь-яку статтю</p>.

Цю проблему можна вирішити двома способами.

1. Ураховувати символи, що не відповідають бажаному взірцю (<[^>]*> для вищеописаного випадку).
2. Визначити квантифікатор як нежадібний (ледачий, англ. lazy) — більшість реалізацій дозволяють це зробити, додавши після нього знак питання.

Використання ледачих квантифікаторів може викликати зворотну проблему, коли виразу відповідає занадто короткий, зокрема, порожній рядок.

Жадібний	Ледачий
*	*?
+	+?
{n,}	{n,}?

Також спільною проблемою як жадібних, так і ледачих виразів є точки повернення для перебору варіантів виразу. Точки ставляться після кожної ітерації квантифікатора. Якщо інтерпретатор не знайшов відповідності після квантифікатора, то він починає повертатися за всіма встановленими точками, перераховуючи звідти вираз по-іншому.

Ревнива квантифікація (Найжадібніша)

При пошуку виразу (a+a+)+b у рядку aaaaa інтерпретатор піде приблизно таким шляхом:

1. aaaaa
2. aaaaa
3. aaaaa
4. aaaaa
5. aaaaa
6. aaaaa
7. aaaaa — і тільки тут, перевіривши всі точки повернення, здасться.

При використанні ревнивого квантифікатора буде виконаний тільки перший крок алгоритму.

На відміну від звичайної (жадібної) квантифікації, ревнива квантифікація не тільки намагається знайти максимально довгий варіант, але ще й не дозволяє алгоритму вертатися до попередніх кроків пошуку для того, щоб знайти можливі відповідності для частини регулярного виразу, що залишилася.

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

Жадібний	Ревнивий
*	*+
?	?+
+	++
{n,}	{n,}+

Приклад	Відповідність
ab(xa)*+a	abxaabxaa; але не abxaabxaa, тому що літера a уже зайнята

Групування

Позначення групи

Круглі дужки використовуються для визначення області дії й пріоритету операцій. Шаблон усередині групи обробляється як єдине ціле й може бути квантифікованим. Наприклад, вираз (тр[ау] м-?)* знайде послідовність виду трумтрам-трум-трамтрум.

Зворотний зв'язок

Одне із застосувань групування — повторне використання раніше знайдених груп символів (підрядків, блоків, позначених підвиразів). При обробці виразу підрядки, що знайдені за шаблоном усередині групи, зберігаються в окремій області пам'яті й отримують номер, починаючи з одиниці. Кожному підрядку відповідає пара дужок у регулярному виразі. Квантифікація групи не впливає на збережений результат, тобто зберігається лише перше входження. Зазвичай підтримується до 9 нумерованих підрядків із номерами від 1 до 9, але деякі інтерпретатори дозволяють працювати з більшою кількістю. Згодом у межах даного регулярного виразу можна використати позначення від \1 до \9 для перевірки на збіг із раніше знайденим підрядком.

Наприклад, регулярний вираз (та|ту)-\1 знайде рядок та-та або ту-ту, але пропустить рядок та-ту.

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

Групування без зворотного зв'язку

Якщо група використовується тільки для групування і її результат надалі не буде потрібен, то можна використати групування виду (?:шаблон). Під результат такого групування не виділяється окрема область пам'яті й, відповідно, їй не призначається номер. Це позитивно впливає на швидкість виконання виразу, але знижує зручність читання.

Атомарне групування

Атомарне групування (виду (?>шаблон)), так само як групування без зворотного зв'язку, не створює зворотних зв'язків. На відміну від нього, таке групування забороняє вертатися назад по рядку, якщо частина шаблону вже знайдена.

Приклад	Відповідність	Створювані групи
a(bc|b|x)cc	abccaxcc abccaxcc	abccaxcc abccaxcc
a(?:bc|b|x)cc		немає
a(?>bc|b|x)cc	abccaxcc але не abccaxcc: варіант x знайдений, інші зігноровані
a(?>x*)xa	не знайдеться axxxa: усі x зайняті, і немає повернення всередину групи

Атомарне групування виконується ще швидше, ніж групування без зворотного зв'язку, і зберігає процесорний час при виконанні решти виразу, тому що забороняє перевірку будь-яких інших варіантів усередині групи, коли один варіант уже знайдений. Це дуже корисно при оптимізації груп із множиною різних варіантів.

Модифікатори

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

Синтаксис	Опис
(?i)	Включає	нечутливість виразу до регістра символів (англ. case insensitivity)
(?-i)	Виключає
(?s)	Включає	режим відповідності точки символам переносу рядка й повернення каретки
(?-s)	Виключає
(?m)	Символи ^ і $ викликають відповідність тільки	після й до символів нового рядка
(?-m)		із початком і кінцем рядка
(?x)	Включає	режим без урахування пробілів між частинами регулярного виразу й дозволяє використовувати # для коментарів
(?-x)	Виключає

Групи-модифікатори можна об'єднувати в одну групу: (?i-sm). Така група включає режим i і виключає режим s, m. Якщо використання модифікаторів потрібне тільки в межах групи, то потрібний шаблон вказується всередині групи після модифікаторів і двокрапки. Наприклад, (?-i)(?i:tv)set знайде TVset, але не TVSET.

Коментарі

Для додавання коментарів у регулярний вираз можна використовувати групи-коментарі виду (?#коментар). Така група інтерпретатором цілком ігнорується й не перевіряється на входження в текст. Наприклад, вираз А(?#тут коментар)Б відповідає рядку АБ.

Перерахування

Вертикальна риса розділяє допустимі варіанти. Наприклад, gray|grey відповідає gray або grey. Варто пам'ятати, що перебір варіантів виконується зліва праворуч, як вони вказані.

Якщо потрібно вказати перелік варіантів усередині складнішого регулярного виразу, то його потрібно взяти в групу. Наприклад, gray|grey або gr(a|e)y описують рядок gray або grey. У разі односимвольних альтернатив кращий варіант gr[ae]y, тому що порівняння із символьним класом виконується простіше, ніж обробка групи з перевіркою на всі її можливі модифікатори й генерацією зворотного зв'язку.

Перегляд уперед та назад

У більшості реалізацій регулярних виразів є спосіб провадити пошук фрагмента тексту, «переглядаючи» (але не включаючи в знайдене) навколишній текст, що розташований до або після шуканого фрагмента тексту. Наприклад, таким способом легко знайти ім'я тегу HTML, не включаючи в результат пошуку оточуючі його кутові дужки або інші знаки, але й, не упускаючи їх «з уваги» при пошуку потрібного контексту. Перегляд із запереченням використовується рідше й «стежить» за тим, щоб указані відповідності, навпаки, не зустрічалися до або після шуканого текстового фрагмента.

Представлення	Вид перегляду	Приклад регулярного виразу	Відповідність
(?=шаблон)	Позитивний перегляд уперед	Людовик(?=XVI)	ЛюдовикXV, ЛюдовикXVI, ЛюдовикXVIII, ЛюдовикLXVII, ЛюдовикXXL
(?!шаблон)	Негативний перегляд уперед (із запереченням)	Людовик(?!XVI)	ЛюдовикXV, ЛюдовикXVI, ЛюдовикXVIII, ЛюдовикLXVII, ЛюдовикXXL
(?<=шаблон)	Позитивний перегляд назад	(?<=Сергій )Іванів	Сергій Іванів, Ігор Іванів
(?<!шаблон)	Негативний перегляд назад (із запереченням)	(?<!Сергій )Іванів	Сергій Іванів, Ігор Іванів

Пошук за умовою

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

Представлення	Пояснення	Приклад	Відповідність
(?(?=якщо)то|інакше)	Якщо операція перегляду успішна, то далі виконується частина то, інакше виконується частина інакше. У виразі може використовуватися кожна із чотирьох операцій перегляду. Варто враховувати, що операція перегляду нульової ширини, тому частини то у разі позитивного або інакше у разі негативного перегляду повинні містити в собі опис шаблону з операції перегляду.	(?(?<=а)м|п)	мам,пап
(?(n)то|інакше)	Якщо n-а група повернула значення, то пошук за умовою виконується за шаблоном то, інакше за шаблоном інакше.	(а)?(?(1)м|п)	мам,пап

Різне

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

Два регулярних вирази можна з'єднати інфіксним оператором «|»; у цьому разі складний вираз буде відповідатиме рядкам, що відповідають або першому, або другому простому регулярному виразу.

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

Приклади

Наведемо декілька словесних прикладів регулярних виразів: «три цифри» (такому шаблону відповідають рядки «121», «424», але не «23абв»), «дві цифри, після яких стоїть крапка, за якою йдуть кілька цифр, проте не менше однієї» (цьому шаблону відповідають «11.2», «11.4а», але не «11. »). Регулярні вирази подібні до арифметичних у тому, що формуються з менших за допомогою операторів.

Заголовки розділів Вікіпедії

Відповідно до правил форматування Вікіпедії, назви розділів починаються з декількох знаків «дорівнює» на початку рядка. Наступний регулярний вираз для GNU Emacs відповідає таким заголовкам:

 \(^==+\).*\1

Див. також

• Представлення символів у регулярних виразах
• sed — джерела регулярних виразів
• Perl — поширена мова програмування, регулярні вирази включено до синтаксису.
• Регулярні події та вирази — теоретичні відомості про вирази регулярними мовами.
• Регулярна множина
• Алгоритм Ерлі
• Висота ітерації мови
• Зіставляння зі взірцем

Примітки

1. Ruslan Mitkov (2003). The Oxford Handbook of Computational Linguistics. Oxford University Press. с. 754. ISBN 978-0-19-927634-9.
2. Mark V. Lawson (17 вересня 2003). Finite Automata. CRC Press. с. 98—100. ISBN 978-1-58488-255-8.
3. Для зручного використання послідовностей літер у деяких мовах необхідно встановити кодову сторінку, у якій ці послідовності будуть іти в порядку від і до зазначених символів. У Юнікоді деякі літери українського алфавіту знаходяться за межами діапазонів А-Я та а-я. [1]

Посилання

• Regular-Expressions.info(англ.) Інструменти для роботи з регулярними виразами, приклади та довідники.
• DMOZ: Перелік посилань на ресурси про регулярні вирази(англ.)
• Інтерактивний редактор regexp'ів
• LDP: Bash beginners guide/regular expressions, docs.linux.org.ua, 24 січня 2007.

Література

• Гаврилків В. М. Формальні мови та алгоритмічні моделі. — І.-Ф.  : Сімик, 2012. — 172 с. Архів оригіналу. (укр.)
• Гаврилків В. М. Регулярні вирази у програмних продуктах. — І.-Ф.  : Голіней, 2012. — 72 с. (укр.)

Портал «Програмування»