llmdocsсправочник разработчика

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

Материал из llmdocs — справочник разработчика
Портал: Основы CS
Регулярные выражения
Основарегулярные языки (Клини, 1951–1956)
Первые реализацииQED и ed (Кен Томпсон, 1968)
ДиалектыPOSIX BRE/ERE, PCRE/Perl, JavaScript, Python re, RE2
Движкиобратный поиск (backtracking), автоматный (Thompson NFA/DFA)
РискReDoS — экспоненциальное время на «плохих» шаблонах
Инструментыgrep, sed, ripgrep, regex101

Регулярные выражения (англ. regular expressions, regex) — компактный язык шаблонов для описания множеств строк. С их помощью ищут подстроки, проверяют формат ввода, извлекают части текста и выполняют замены. Регулярные выражения встроены почти во все языки программирования, редакторы и утилиты командной строки, от grep и sed до IDE и СУБД.[1]

История

Математик Стивен Клини в 1950-х описал регулярные языки и нотацию для них. Кен Томпсон в 1968 году реализовал её в редакторе QED, а затем в ed, откуда появился grep (g/re/p — «глобально найти регулярное выражение и напечатать»). Позднее POSIX стандартизировал базовый и расширенный синтаксис, а Perl в 1990-х добавил множество расширений; библиотека PCRE сделала этот диалект стандартом де-факто.

Основной синтаксис

Конструкция Значение Пример
. любой символ (кроме перевода строки) a.c → abc, a-c
[abc], [a-z], [^0-9] класс символов, диапазон, отрицание [А-Яа-яЁё]
\d, \w, \s цифра, «словесный» символ, пробельный \d{3}
*, +, ? 0 и больше, 1 и больше, 0 или 1 colou?r
{n}, {n,m} ровно n, от n до m повторений \d{2,4}
^, $ начало и конец строки ^#
\b граница слова \bcat\b
a|b альтернатива jpe?g|png
( ) группа с захватом (\d+)-(\d+)
(?:...) группа без захвата
(?P<name>...), (?<name>...) именованная группа
(?=...), (?!...), (?<=...) просмотр вперёд и назад \d+(?= ₽)

Квантификаторы по умолчанию жадные — захватывают как можно больше; *?, +? делают их ленивыми. Флаги меняют поведение: i — без учёта регистра, m — ^/$ для каждой строки, s — точка включает перевод строки, x — допускаются пробелы и комментарии в шаблоне.

Примеры в языках

import re

re.findall(r"\b\d{4}-\d{2}-\d{2}\b", "релизы 2024-05-01 и 2026-11-09")
# ['2024-05-01', '2026-11-09']

m = re.search(r"(?P<user>[\w.+-]+)@(?P<host>[\w.-]+)", "почта: ivan@example.com")
m.group("host")     # 'example.com'

re.sub(r"\s+", " ", "много   пробелов\n тут")   # 'много пробелов тут'

const re = /(\d+)\s*₽/g;
[..."100 ₽ и 250₽".matchAll(re)].map(m => Number(m[1]));   // [100, 250]

grep -E '^(ERROR|WARN)' app.log
rg -o 'v\d+\.\d+\.\d+' CHANGELOG.md

В Python шаблоны пишут «сырыми» строками r"...", чтобы обратные слеши не обрабатывались дважды; часто используемые выражения компилируют один раз через re.compile.

Диалекты и движки

Синтаксис отличается в деталях: в POSIX BRE (grep без -E) скобки и + нужно экранировать, \d в POSIX отсутствует (вместо него [[:digit:]]), а просмотр назад и обратные ссылки поддерживаются не везде.

Важнее различие движков:[3]

  • Движки с обратным поиском (backtracking) — Perl, PCRE, Python re, JavaScript, Java, .NET. Поддерживают обратные ссылки ((\w)\1) и просмотр, но на некоторых шаблонах работают экспоненциально долго.
  • Автоматные движки (NFA/DFA по Томпсону) — RE2, пакет regexp в Go, крейт regex в Rust, ripgrep. Гарантируют время, линейное по длине входа, зато не поддерживают обратные ссылки и просмотр.[4]

ReDoS

Шаблон с вложенными квантификаторами, например ^(a+)+$, на строке aaaaaaaaaaaaaaaaaaaaaaaa! заставляет движок с обратным поиском перебрать экспоненциальное число вариантов. Если такой шаблон применяется к пользовательскому вводу, одна строка может занять процессор на минуты — это атака ReDoS (regular expression denial of service).[5] В июле 2019 года одно регулярное выражение в правилах WAF Cloudflare загрузило процессоры по всему миру и вызвало глобальный сбой на 27 минут.[6]

Защита: избегать вложенных и перекрывающихся квантификаторов ((a|a)*, (.*)*), ограничивать длину входа, задавать тайм-ауты, для недоверенных данных использовать линейные движки (RE2, Go, Rust), проверять шаблоны линтерами.

Unicode

\w и \d в Python 3 по умолчанию понимают Unicode: \d совпадёт и с арабско-индийскими цифрами, поэтому для строгой проверки лучше [0-9] или флаг re.ASCII. В JavaScript для корректной работы с Unicode нужен флаг u (или v), тогда доступны классы вида \p{L} (любая буква) и \p{Script=Cyrillic}. Требования к Unicode-регулярным выражениям описывает стандарт UTS #18.[7]

Когда не использовать

Регулярные выражения не умеют разбирать вложенные структуры произвольной глубины: HTML, JSON, языки программирования требуют настоящих парсеров. Для email и URL надёжнее библиотечные валидаторы и проверка подтверждением, чем «идеальная» регулярка на сотни символов. Длинные шаблоны стоит документировать флагом x и покрывать тестами; для отладки удобен сайт regex101, показывающий разбор и шаги движка. Языковые модели неплохо пишут и объясняют регулярные выражения, но их результат тоже нужно проверять на примерах.

См. также

Источники

  1. Python — re: Regular expression operations
  2. MDN — Regular expressions (JavaScript)
  3. Russ Cox — Regular Expression Matching Can Be Simple And Fast
  4. RE2 syntax
  5. OWASP — Regular expression Denial of Service (ReDoS)
  6. Cloudflare — Details of the Cloudflare outage on July 2, 2019
  7. Unicode Technical Standard #18 — Unicode Regular Expressions
Категории: