Регулярные выражения

Регулярные выражения появились в 1951 году, когда математик Стивен Коул Клин описал регулярные языки через математическую нотацию, которую назвал «регулярными событиями» (англ. regular events)^[7]. Формализм возник в рамках теории автоматов и описания формальных языков, с первоначальной целью описания архитектуры ранних искусственных нейронных сетей. (Клин изначально назвал эти события «prehensible» в противопоставление модели МакКаллока — Питтса, позднее признав: «Мы будем рады любым предложениям, как сделать термин более описательным.») В ранних языках программирования, таких как SNOBOL, использовались другие формализмы поиска по шаблону.

Практическое применение регулярных выражений началось в 1968 году: с одной стороны, для поиска по паттернам в текстовом редакторе^[8] — благодаря инициативе Кена Томпсона по интеграции нотации Клина в редактор QED — а с другой стороны, для лексического анализа в компиляторах^[9]. Томпсон реализовал сопоставление с помощью JIT-компиляции в байт-код для IBM 7094 на раннем CTSS — это один из первых примеров JIT-подхода. Позже этот подход появился и в редакторе ed (UNIX), что привело к появлению инструмента grep, название которого образовано от команды поиска по регулярному выражению: g/re/p («Global search for Regular Expression and Print matching lines»)^[10]. В этот же период группа Д. Т. Росса реализовала на основе идей Клина инструменты для лексического анализа в компиляторах.

В 1970-х в Bell Labs на базе Unix создавались многочисленные вариации регулярных выражений: lex, sed, AWK, expr, а также редакторы vi и Emacs, в последнем реализован собственный несовместимый синтаксис^[11]. Эти ранние формализмы были стандартизированы в POSIX.2 (1992).

В 1980-х новый этап развития ознаменовался появлением Perl и библиотеки регулярных выражений Генри Спенсера (1986), которую адаптировали для Tcl («Advanced Regular Expressions»)^[12]. Реализация Tcl представляет собой гибрид НКА/ДКА с улучшенной производительностью и применяется, например, в PostgreSQL^[13]. Perl расширил возможности за счёт новых конструкций^[14]. Особое развитие получила интеграция с Raku (Perl 6), которая оформилась в мини-язык «Raku rules» для описания грамматик и поддержала BNF-стиль задания рекурсивных спусков.

Регулярные выражения легли в основу формализации грамматик описания структуры документов и баз данных в промышленных стандартах 1980-х, включая ISO SGML, DTD и последующие спецификации XML.

Сегодня регулярные выражения встроены во многие языки программирования (Java, Python, Perl, ECMAScript и др.), используются в программах для работы с текстом, анализаторах лексем, редакторах и других утилитах. Современные реализации используют аппаратные ускорители на базе FPGA и GPU^[15] для ускорения обработки по сравнению с реализацией на CPU.

В период 2020–2025 годов аппаратное ускорение на базе ПЛИС (FPGA) получило развитие в системах глубокого анализа пакетов (DPI) и обнаружения вторжений (IDS/IPS). Аппаратный параллелизм применяется для высокоскоростного сопоставления с шаблонами в реальном времени, обеспечивая фильтрацию трафика с высокой пропускной способностью и низкими задержками, в том числе при интеграции с алгоритмами искусственного интеллекта для сетей 5G. Также в эти годы активно развивался стандарт ECMAScript (ES2020–ES2025), в который были добавлены новые возможности для работы с регулярными выражениями, включая методы глобального поиска и замены, улучшенную поддержку Юникода, локальные модификаторы шаблонов и встроенное экранирование строк^[16][17][18].

Термин англ. regular expressions (регулярные выражения) либо англ. regexes (регексы) часто относится к конкретному стандартному синтаксису записи шаблонов поиска текста, отличному от исходной математической нотации. Каждый символ в регулярном выражении либо является метасимволом (обозначает особое действие), либо обычным (сопоставляется буквально). Например, в выражении b. латинская «b» — литерал, а точка — метасимвол (соответствует любому символу, кроме перевода строки). Метасимволы и литералы используются для описания классов текстов или наборов совпадающих строк.

Пример: seriali[sz]e находит оба варианта написания слова: «serialise» и «serialize». Шаблонные символы (wildcards) реализуют похожие функции, но в более ограниченном виде.

Глоббинг файлов в списках файлов применяет шаблоны с подстановочными знаками, но регулярные выражения обычно используются для анализа строк в общем виде. Пример: ^[ \t]+|[ \t]+$ — для поиска лишних пробелов в начале или конце строк. Более сложный шаблон для чисел: [+-]?(\d+(\.\d*)?|\.\d+)([eE][+-]?\d+)?.

Движок регулярных выражений преобразует заданный паттерн в внутреннее представление и сравнивает его с целевым текстом. Один из подходов — алгоритм Томпсона (Thompson's construction) — строит НКА, затем приводит его к ДКА и запускает для поиска совпадений.

Регулярное выражение (шаблон) задаёт множество строк. Для конечного множества можно просто перечислить все элементы, но зачастую регулярное выражение позволяет задать множество компактно. Например, паттерн H(ä|ae?)ndel соответствует «Handel», «Händel», «Haendel»; иной вариант — (Hän|Han|Haen)del.

Основные операции для построения регулярных выражений:

Логическое «или»

Вертикальная черта («|») разделяет альтернативы. Пример: gray|grey.

Группировка

Скобки — задают область действия операторов. Например, gr(a|e)y и gray|grey эквивалентны.

Квантификация

Квантификатор после элемента (литерала, группы) задаёт число повторений: «?» (ноль или одно), «*» (звезда Клини — от нуля до бесконечности), «+» (плюс Клини — одно и более раз).

Подстановочный символ

Точка (.) соответствует любому символу. Примеры:

a.b — "a%b", "axb", "a5b", и т. п.

a.*b — все строки, где после «a» где-то позже встречается «b».

Эти конструкции комбинируются для построения любых выражений.

Точный синтаксис зависит от конкретной реализации — см. ниже раздел «Синтаксис».

Регулярные выражения описывают регулярные языки в теории формальных языков и эквивалентны регулярным грамматикам. Язык самих регулярных выражений — контекстно-свободный язык.

Регулярное выражение (паттерн) состоит из последовательности атомов; атому сопоставляется подстрока строки. Атомом чаще всего является литерал, но могут быть использованы скобки для группировки, повторения, альтернативы и обратные ссылки (backreferences). Совпадение считается, если все атомы паттерна найдены.

В зависимости от реализации, насчитывается свыше десятка метасимволов: { } [ ] ( ) ^ $.|*+? и \\; для обозначения буквального символа используются экранирования. В современных движках (например, PCRE2) количество метасимволов значительно превышает десяток, и в базовый набор включены символы свойств Unicode (\\p, \\P)^[23][24].

Современные движки поддерживают конструкции, выходящие за пределы регулярных языков: например, backreferences позволяют сопоставлять шаблоны типа "papa", "WikiWiki", то есть повторяющиеся группы ((.+)\1), что формально неописуемо в терминах регулярных грамматик.

Использование backreferences делает задачу сопоставления NP-полной^[42].

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

Современный синтаксис также поддерживает именованные группы захвата, которые записываются как (?<name>...). Для обращения к таким группам внутри шаблона используются именованные обратные ссылки, например, \k<name> (в PCRE2 также поддерживаются варианты \g{name}, (?P=name))^[43][44].

Существуют три базовых класса алгоритмов проверки соответствия строки регулярному выражению:

• неявное построение ДКА (O(2^m), использование памяти экспоненциально по размеру выражения, поиск — линейный по длине строки)
• моделирование НКА (O(mn)), используется в большинстве стандартных реализаций
• бэктрекинг (экспоненциальное время в некоторых случаях из-за возвратов; может привести к уязвимости ReDoS)

Описаны ускоренные варианты (Boyer—Moore и др.), а также теоретические подходы с уменьшением экспоненты^[46].

Также применяется механизм «ленивого ДКА» (Lazy DFA), который кэширует состояния «на лету» для избежания экспоненциального взрыва памяти при сохранении линейного времени поиска. Этот подход используется в таких движках, как RE2 и Rust regex^[47]

Среди доминирующих современных движков выделяются:

• Google RE2 и Rust regex — ориентированы на безопасность и гарантированное линейное время выполнения, не поддерживают обратные ссылки^[48]
• PCRE2 — отличается полнотой синтаксиса (поддерживает сложные конструкции, включая обратные ссылки), однако подвержен катастрофическому возврату^[48]

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

• поддержка разных кодировок (UTF-8, UTF-16, UTF-32)
• диапазон поддерживаемых символов (только BMP или весь Unicode)
• расширение классических описаний [x-y] на диапазоны кодовых точек Unicode; ограничения по пересечению блоков (Vim, gawk)
• флаги регистронезависимости — для ASCII, для Unicode
• дополнительные классы — для блоков, скриптов, свойств символов
• вопросы нормализации: эквивалентность канонических и составных символов
• поддержка контрольных и управляющих символов (BOM)

Поддержка Unicode постоянно совершенствуется. Например, библиотеки PCRE2 и ICU поддерживают стандарты Unicode вплоть до версии 17.0^[49][50]. В стандарте ECMAScript 2024 был введён флаг v, который является усовершенствованной версией флага u (Unicode) и добавляет операции над наборами символов (вычитание, пересечение), а также поддержку свойств Unicode для многосимвольных строк.

Большинство языков общего назначения содержит либо встроенную поддержку регулярных выражений, либо библиотеки с их реализацией. В платформе .NET опция RegexOptions.ECMAScript приближает поведение регулярных выражений к JavaScript, но не поддерживает современные флаги u и v, из-за чего возникают расхождения в обработке астральных символов и Unicode-свойств^[51].

Регулярные выражения широко используются при обработке текста: валидация данных, скрейпинг данных, парсинг, подсветка синтаксиса, форматирование. В настольных издательских системах регексы могут использоваться для массового применения стилей к тексту (например, для выделения слов из заглавных букв). Использование в публичных поисковых системах обычно не предоставляется из-за ресурсоёмкости; исключения — Google Code Search (закрыт в 2012), Exalead^[52]. В сфере больших языковых моделей (LLM) и генеративного ИИ регулярные выражения применяются для механизмов ограниченного декодирования (англ. constrained decoding / JSON mode), обеспечивая структурную целостность генерируемых токенов^[6].^[53]

Конкретный синтаксис зависит от реализации, языка или библиотеки. Отличия могут касаться типа скобок, модификаторов (жадный/ленивый), наличия дополнительных классов символов. Обычно используется синтаксис Perl (PCRE).

Примерная таблица основных конструкций:

$string1 = "Hello World\n";
if ($string1 =~ m/...../) {
  print "$string1 has length >= 5.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/(H..).(o..)/) {
  print "We matched '$1' and '$2'.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/l+/) {
  print "There are one or more consecutive letter \"l\"'s in $string1.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/H.?e/) {
  print "Есть 'H' и 'e' с 0–1 символами между ними (например, He Hue Hee).\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/(l.+?o)/) {
  print "Ленивое сопоставление: 'llo', а не 'llo Wo'.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/el*o/) {
  print "Е есть 'e', 0+ букв 'l', далее 'o' (eo, elo, ello, elllo).\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/l{1,2}/) {
  print "Есть подстрока из 1–2 букв 'l'.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/[aeiou]+/) {
  print "$string1 contains one or more vowels.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/(Hello|Hi|Pogo)/) {
  print "$string1 содержит одно из Hello, Hi или Pogo";
}

$string1 = "Hello World\n";
if ($string1 =~ m/llo\b/) {
  print "Слово заканчивается на 'llo'.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/\w/) {
  print "Есть хотя бы один буквенно-цифровой символ.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/\W/) {
  print "Пробел между Hello и World — не алфавитно-цифровой.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/\s.*\s/) {
  print "В строке есть >1 пробельных символа.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/\S.*\S/) {
  print "Есть два непустых символа, разделённых чем угодно.\n";
}

$string1 = "99 bottles of beer on the wall.";
if ($string1 =~ m/(\d+)/) {
  print "$1 — первое число в '$string1'\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/\D/) {
  print "Хотя бы один символ не является цифрой.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/^He/) {
  print "Строка начинается с 'He'.\n";
}

$string1 = "Hello World\n";
if ($string1 =~ m/rld$/) {
  print "Строка заканчивается на 'rld'.\n";
}

Регулярные выражения могут выводиться («индуцироваться») автоматически по набору примеров строк (вычислительное обучение грамматик). Такие методы позволяют строить паттерны по положительным и отрицательным примерам.