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

Когда вы пишете в терминале `grep -E '(error|warn).*timeout' server.log`, вы используете нотацию, изобретённую математиком Стивеном Клини в 1956 году. Он доказал, что ЛЮБОЙ регулярный язык можно описать комбинацией трёх операций: объединения, конкатенации и звезды. Сегодня мы построим эту нотацию формально - и увидим, где заканчиваются возможности «настоящих» regex и начинаются расширения grep/PCRE.

• **grep/sed/awk:** каждый regex в командной строке - это формальное регулярное выражение (плюс синтаксический сахар)
• **Лексический анализ:** компиляторы описывают токены (числа, идентификаторы, ключевые слова) через regex и компилируют их в DFA
• **Сетевые IDS (Snort, Suricata):** сигнатуры атак записываются как regex и матчатся на скорости 10 Gbit/s благодаря конечным автоматам

Синтаксис формальных regex

Вы уже знаете три операции над языками: объединение (∪), конкатенацию (·) и звезду Клини (*). **Регулярное выражение** - это компактная текстовая запись, которая описывает язык через эти три операции. Точно так же, как арифметическое выражение `2 + 3 × 4` компактно описывает число 14.

**Формальное определение.** Регулярные выражения над алфавитом Σ строятся индуктивно: 1. **∅** - regex, описывающий пустой язык {}. 2. **ε** - regex, описывающий {ε}. 3. **a** (для любого a ∈ Σ) - regex, описывающий {a}. 4. Если r и s - regex, то **(r|s)** - regex для L(r) ∪ L(s). 5. Если r и s - regex, то **(r·s)** или **(rs)** - regex для L(r)·L(s). 6. Если r - regex, то **(r*)** - regex для L(r)*.

**Приоритет операторов** позволяет опускать скобки - точно как в арифметике, где умножение выполняется раньше сложения. В regex: ***** (звезда) > **·** (конкатенация) > **|** (объединение). Поэтому `ab*|c` означает `(a(b*))|c`, а не `(ab)*|c` или `a(b*|c)`.

**Мнемоника:** приоритеты regex совпадают с арифметикой. Звезда (*) = степень (высший), конкатенация (·) = умножение (средний), объединение (|) = сложение (низший). Если помните `2+3×4²`, вы помните `a|bc*`.

Построение regex для реальных задач

Знать синтаксис - мало. Нужно уметь **переводить** словесное описание языка в regex и обратно. Это навык, который развивается практикой. Начнём с простых примеров и постепенно усложним задачу.

Пример 1: строки, содержащие подстроку «01»

Пример 2: строки с чётным числом нулей

Пример 3: строки, НЕ содержащие «11»

**Паттерн построения regex:** 1. Определите «хорошие блоки» - части строки, которые точно допустимы. 2. Скомбинируйте блоки через конкатенацию и звезду Клини. 3. Проверьте граничные случаи: пустая строка, один символ, самая короткая допустимая строка.

**Типичная ошибка:** regex `0*1*` описывает НЕ «строки из нулей и единиц», а «ноль или более нулей, затем ноль или более единиц». Это {ε, 0, 1, 00, 01, 11, 001, 011, ...} - подмножество Σ*, а не Σ*. Строка '10' ∉ L(0*1*).

Алгебра регулярных выражений

Два regex могут выглядеть по-разному, но описывать один и тот же язык. Например, `a|b` и `b|a` - это один язык {a, b}. Существует набор **алгебраических законов**, позволяющих упрощать regex - аналогично тому, как `x + 0 = x` упрощает арифметику.

**Два regex r и s эквивалентны** (записывается r ≡ s), если L(r) = L(s) - они описывают один и тот же язык. Эквивалентность можно проверить алгебраически (применяя законы) или конструктивно (построив минимальный DFA для каждого regex).

**Упрощение regex на практике.** Закон `r* ≡ ε|rr*` позволяет «раскрывать» звезду: первая итерация выделяется явно. Закон `r(s|t) ≡ rs|rt` выносит общий префикс. А закон `(r*)* ≡ r*` убирает лишнюю вложенность.

**Ключевое тождество: r* ≡ ε | r·r*.** Звезда Клини - это рекурсивное определение: «или ничего, или один r плюс ещё сколько угодно r». Это основа конструкции NFA по regex (алгоритм Томпсона).

Формальные regex vs grep/PCRE

Если вы писали `\d+\.\d+` или `(\w+)\s+\1`, вы использовали **практические** регулярные выражения (PCRE, POSIX). Они выглядят похоже на формальные regex, но есть принципиальная разница: практические regex **выходят за пределы** регулярных языков. Это одно из самых частых заблуждений в CS.

Первые шесть строк таблицы - просто **синтаксический сахар**: `r+` = `rr*`, `r?` = `r|ε`, `[a-z]` = `a|b|...|z`. Язык описания не расширяется - любой regex с `+`, `?` и `[]` можно переписать с помощью трёх базовых операций. Но **обратные ссылки** - это качественно другой уровень.

**Теорема:** формальные regex описывают ровно класс **регулярных языков** (тип 3 по Хомскому). Ни больше, ни меньше. PCRE с обратными ссылками описывают строго больший класс - некоторые контекстно-свободные и даже контекстно-зависимые языки. Задача проверки PCRE-regex NP-трудна, тогда как формальных regex - O(n).

**Когда говорят «regex» в индустрии - имеют в виду PCRE/POSIX, а не формальные regex.** В курсе теории вычислений «regex» = формальные регулярные выражения (только |, ·, *). Если преподаватель спрашивает «можно ли описать regex», он имеет в виду формальные - без backreferences, lookahead и прочих расширений.

Ключевые идеи

• **Формальный regex** - индуктивное определение: базовые (∅, ε, символ) + три операции (|, ·, *)
• **Приоритет:** * > · > | - как степень > умножение > сложение в арифметике
• **Алгебраические законы** позволяют упрощать regex: r|r ≡ r, (r*)* ≡ r*, r∅ ≡ ∅, r* ≡ ε|rr*
• **Формальные regex ≠ PCRE:** обратные ссылки (\1) и lookahead выходят за пределы регулярных языков; matching PCRE NP-труден

Связанные темы

Регулярные выражения связывают формальные языки с автоматами и практическими инструментами:

• Конечные автоматы (DFA/NFA) — Теорема Клини: regex описывают ровно те языки, что распознаются конечными автоматами
• Конструкция Томпсона — Алгоритм преобразования regex → NFA: каждый оператор (|, ·, *) становится фрагментом автомата

Вопросы для размышления

• Вернёмся к grep-команде из начала: `(error|warn).*timeout`. Перепишите её как формальный regex (используя только |, · и *) над алфавитом ASCII.
• Regex `a*` и `(a|ε)*` описывают один и тот же язык. Докажите это через алгебраические законы.
• Google RE2 (движок regex) намеренно НЕ поддерживает обратные ссылки. Используя знания об NP-трудности PCRE-matching, объясните, почему это разумное инженерное решение.

Связанные уроки

• fl-04-operations — Closure operations are the basis of regex operators
• fl-06-dfa — Every regex has an equivalent DFA
• fl-07-nfa — Regex is most naturally compiled to NFA first
• fl-09-regex-to-automata — Thompson construction converts regex to NFA step by step
• comp-07-regex-in-lexer — Regex used practically in lexer rule specifications