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

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

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

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

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

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

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

Термин англ. 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».

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

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

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

Регулярные выражения строятся из констант, обозначающих множества строк, и операторов, обозначающих операции над ними. Пусть Σ — конечный алфавит. Стандартные константы:

• (пустое множество) ∅ — пустое множество ∅.
• (пустая строка) ε — множество из единственной пустой строки.
• (литерал) a ∈ Σ — множество, состоящее из строки-литерала.

Далее над ними определяют операции:

• Конкатенация (RS) — все строки, получаемые склеиванием строки из R и строки из S.
• Альтернатива (R|S) — объединение множеств R и S.
• Звезда Клини (R*) — наименьшее надмножество множества R, содержащее ε и замкнутое относительно конкатенации (любое количество повторений элементов R, в том числе ноль).

Приоритет: звезда Клини > конкатенация > альтернатива. Круглые скобки можно опускать в случае однозначности. Для альтернативы иногда используют ∪, + или ∨.

• [hc]?at — «at», «hat», «cat»
• [hc]*at — все слова, где перед «at» любая последовательность «h», «c»
• cat|dog — «cat» или «dog»

Формальное определение минимально по набору операций: ? и + выражаются через базовые — a+ = aa*, a? = (a|ε). Иногда вводят оператор дополнения для краткости (все строки, не входящие в заданное регулярное выражение), но выразительную силу это не увеличивает, лишь сокращает запись^[20][21].

Регулярные выражения строго описывают класс языков, распознаваемых детерминированными конечными автоматами, однако в ряде случаев DFA требует экспоненциально большего числа состояний по сравнению с коротким выражением (пример: язык всех слов, в которых k-я с конца буква — «a»). Для преобразования регулярного выражения в НКА используют алгоритм Томпсона, для обратного преобразования — алгоритм Клина.

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

Операции над регулярными выражениями (например, перестановка местами альтернатив, скобочное вложение) могут приводить к эквивалентным языкам — существуют алгоритмы проверки эквивалентности, основанные на приведении к минимальному ДКА^[22].

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

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

В языках программирования регулярные выражения часто помещают в строковые литералы; в некоторых случаях (например, Perl) паттерн выделяют косыми чертами: /re/. Альтернативные разделители иногда удобны для избежания экранирования символов-разделителей внутри паттерна.

POSIX определяет режимы BRE (Basic Regular Expressions), ERE (Extended Regular Expressions) и устаревший SRE (deprecated). BRE требует экранирования некоторых скобок и фигурных скобок, ERE — нет, и добавляет операторы ?, +, |. Например, в GNU grep ERE вызывается через -E, BRE — через -G; -P включает синтаксис Perl.

Перловский синтаксис регулярных выражений стал своего рода де-факто стандартом расширений, включая ленивые квантификаторы, именные группы, рекурсию.

В режиме BRE скобки и фигурные скобки обозначаются как \(\), \{\}, в ERE — как (), {}. Таблица основных метасимволов:

В ERE экранирование инвертирует смысл ряда метасимволов. В ERE — (), {}, backreferences нет.

Класс символов — основная конструкция для сопоставления с набором символов, например [A-Z] — любая заглавная латинская; \d — любая цифра.

POSIX-классы могут использоваться только внутри конструкций [...].

Perl и совместимые синтаксисы (PCRE) расширяют набор атомов и модификаторов: группы, Backreferences, ленивые квантификаторы, именованные группы, рекурсии. широкий набор подобных поддерживается в Java, Python, JavaScript и других языках^[23].

PCRE2 (Perl Compatible Regular Expressions) — широко используемая C-библиотека и современное развитие PCRE, лежащая в основе работы регулярных выражений во многих языках и инструментах, включая PHP и R^[24]. В 2024 году в неё были внесены значительные обновления^[25]:

• Поддержка стандарта Unicode была обновлена до версий 15.0.0 и 16.0^[25].
• Добавлена поддержка утверждений просмотра назад (lookbehind) с ограниченной переменной длиной^[25].
• Изменено поведение квантификаторов вида {,n} (например, {,3}), которые теперь трактуются как {0,n} для совместимости с Perl^[25].
• Введены новые функции API, такие как pcre2_get_match_data_heapframes_size() для контроля над памятью и pcre2_next_match() для безопасного перебора совпадений^[25].

Стандарт ECMAScript, на котором основан JavaScript, получил значительные обновления для регулярных выражений в версиях ES2024 и ES2025.

Ключевым нововведением стандарта ES2024 стал флаг v, который является усовершенствованной версией флага u (для полной поддержки Unicode). Новый флаг добавил возможность выполнять операции над наборами символов, такие как вычитание и пересечение, а также поддержку свойств Unicode для многосимвольных строк^[26].

Для стандарта ES2025 были финализированы (достигли стадии 4) следующие возможности:

• Модификаторы шаблона (англ. Pattern Modifiers): введён синтаксис, позволяющий включать или отключать флаги для отдельных частей регулярного выражения, а не для всего шаблона целиком. Например, конструкция (?i:subpattern) применяет регистронезависимый поиск только к подшаблону subpattern^[27].
• RegExp.escape(): добавлен встроенный статический метод для экранирования специальных символов в строке. Это позволяет безопасно создавать регулярные выражения из пользовательского ввода или других переменных, снижая риск ошибок и устраняя необходимость в самописных функциях экранирования^[28].
• Дублирующиеся имена для групп захвата: разрешено использовать одинаковые имена для групп захвата в разных ветвях альтернативного сопоставления (например, при использовании оператора |). Данное расширение синтаксиса допустимо при условии, что в ходе сопоставления может сработать только одна из групп с одинаковым именем^[29].

Во многих интерпретациях (Python, Java) квантификаторы по умолчанию жадные, то есть поглощают максимум символов^[30]. Для ленивого (минимального) поведения используется суффикс ?: ".+?".

В некоторых реализациях (например, Java, Python 3.11+) квантификаторы могут быть посессивными (жадность без бэктрекинга), отмечается как *+ и т. п^[31].

IETF RFC 9485 описывает унифицированный подмножество регулярных выражений («I-Regexp»), обеспечивающий кроссплатформенную переносимость сопоставления без дополнительных расширений^[32].

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

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

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

Расширенные регулярные выражения поддерживают lookahead и lookbehind-утверждения для сложных видов поиска: (?=...), (?!...), (?<=...), (?<!...). Они широко используются с 1990-х (начиная с Perl 5)^[35].

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

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

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

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

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

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

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

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

Конкретный синтаксис зависит от реализации, языка или библиотеки. Отличия могут касаться типа скобок, модификаторов (жадный/ленивый), наличия дополнительных классов символов. Обычно используется синтаксис 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";
}

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