Регулярные выражения в информатике¶
Регулярное выражение (регэксп, regex, от англ. regular expression) — строковый шаблон, описывающий набор строк, построенный по формальным правилам регулярных языков. Регулярные выражения используются для поиска, распознавания и манипулирования текстом: в текстовых редакторах, интерпретаторах оболочки, языках программирования, системах поиска и валидации данных.
¶История
Математическая теория регулярных языков была заложена Стивеном Клини в 1956 году в работе о конечных автоматов и алгебраических теориях. В 1962 году Кеннетом Томпсоном реализован алгоритм компиляции регулярных выражений в конечные автоматы, применённый в текстовом редакторе QED. Томпсон стал соавтором утилиты grep (1973), название которой происходит от команды «global regular expression print».
В 1986 году в системе UNIX появился утилитный набор awk, а в 1987 году Ларри Уолл выпустил Perl, в котором регулярные выражения получили развитый синтаксис с обратными ссылками и поддержкой захвата групп. Этот набор функций стал основой для POSIX-стандартов (BRE и ERE) и впоследствии для PCRE (Perl Compatible Regular Expressions) — библиотеки, скопированной во многие языки и системы.
¶Основные элементы
Синтаксис регулярных выражений включает литеральные символы и метасимволы:
| Элемент | Описание |
|---|---|
. | любой один символ (кроме перевода строки в большинстве диалектов) |
* | ноль или более повторений предыдущего элемента |
+ | один или более повторений |
? | ноль или один повтор |
^, $ | начало и конец строки |
[abc] | символьный класс — любой из указанных символов |
(abc) | группа — объединение элементов, захват подстроки |
\d, \w, \s | цифра, буква/цифра/подчёркивание, пробельный символ |
Пример: шаблон ^\d{3}-\d{2}-\d{4}$ описывает строки формата «123-45-6789» — номер социального страхования США, часто используемый как учебный пример валидации.
¶Виды и стандарты
Различают несколько основных диалектов:
- BRE (Basic Regular Expressions) — классический синтаксис утилит grep и sed в UNIX; группировка задаётся через
\(\), а квантификаторы+и?требуют экранирования. - RESE / ERE (Extended Regular Expressions) — расширенный синтаксис с группировкой
()и прямыми квантификаторами, поддерживается grep -E. - PCRE — совместимый с Perl набор функций, включает ленивые квантификаторы, lookahead/lookbehind, рекурсивные шаблоны.
- RE2 — библиотека Google, гарантирующая линейное время работы за счёт отказа от обратных ссылок и lookahead; используется в ClickHouse, CockroachDB и других системах.
¶Алгоритмы и сложность
Поиск регулярного выражения в тексте выполняется либо интерпретацией шаблона как конечного автомата (метод Томпсона, время O(n·m) для текста длины n и шаблона длины m), либо обратным сопоставлением (backtracking). Backtracking-движки (Perl, Python, JavaScript) поддерживают расширенные конструкции, но в худшем случае демонстрируют экспоненциальное время работы — эффект, известный как «катаклизм регулярных выражений» (ReDoS). Известны примеры, когда шаблон вида (a+)+b на строке из десятков символов «a» без завершающего «b» приводит к многоминутной задержке.
¶Применение
Регулярные выражения встроены в большинство языков программирования: Python (модуль re), JavaScript (RegExp), Java (java.util.regex), C# (System.Text.RegularExpressions), Go (пакет regexp с движком RE2). В операционных системах они используются в утилитах grep, sed, awk, find, в текстовых редакторах (Vim, Emacs, Sublime Text) для поиска и замены.
В веб-разработке регулярные выражения применяются для валидации форм (адреса электронной почты, номера телефонов, почтовые индексы), разбора логов, извлечения данных из HTML/XML. Поисковые системы и СУБД используют расширения регулярных языков: PostgreSQL поддерживает POSIX-синтаксис в операторе ~, MySQL — собственный диалект в REGEXP.
В естественных науках и биоинформатике регулярные выражения применяются для поиска мотивов в последовательностях ДНК и белков; для этих задач разработаны специализированные расширения (PROSITE, regular expressions с допуском несоответствий).
¶Ограничения
Классические регулярные выражения описывают только регулярные языки и неспособны к счёту вложенных скобок — задача вида «найти сбалансированные скобки» не решается стандартным regex. Для таких задач используются парсеры или контекстно-свободные грамматики. Кроме того, сложность чтения сложных регулярных выражений привела к появлению термина «write-only language» — шаблон, который его автор способен понять только в момент написания.
¶Интересные факты
В 2023 году исследователи продемонстрировали, что на современных браузерах выполнение вредоносного регулярного выражения способно заблокировать основной поток выполнения JavaScript на десятки секунд, что стало основанием для включения ReDoS в список OWASP Top 10 для API.
Источники:
- Клини С. «Введение в теорию автоматов, языки и вычислений»
- Фридл Д. «Regular Expressions Cookbook»
- Документация POSIX.1-2017, раздел «Regular Expression Notation»
- Russ Cox, «Regular Expression Matching Can Be Simple And Fast» (2007)
- Документация библиотеки RE2 (Google)