Контекстно-свободные грамматики (CFG)

Каждый раз, когда вы пишете `if (x > 0) { return x * 2; }`, компилятор разбирает эту строку по правилам грамматики. Эта грамматика - контекстно-свободная. Без CFG не было бы ни одного языка программирования, ни одного калькулятора, ни одного HTML-парсера.

• **Компиляторы и интерпретаторы** - парсинг кода на C, Python, JavaScript опирается на CFG
• **HTML/XML парсеры** - вложенные теги `<div><p>...</p></div>` описываются контекстно-свободной грамматикой
• **Математические выражения** - калькуляторы используют CFG для правильного порядка операций
• **NLP (обработка естественного языка)** - синтаксический разбор предложений: подлежащее + сказуемое + дополнение

Что такое контекстно-свободная грамматика?

**Регулярные выражения бессильны** перед задачей проверки вложенных скобок. Строка `((()))` - корректна, `(()` - нет. Regex не может «считать» глубину вложенности. Для таких языков нужен более мощный инструмент - **контекстно-свободная грамматика (CFG)**.

**CFG** - это набор правил подстановки, которые описывают, как из стартового символа порождать строки языка. В отличие от регулярных грамматик, правая часть правила может содержать **любую** комбинацию терминалов и нетерминалов.

Формально, **G = (V, Σ, R, S)** - четвёрка, где:

Рассмотрим классический пример - язык **{aⁿbⁿ | n ≥ 0}**, который regex распознать не способен:

**Почему это работает?** Каждое применение правила `S → aSb` добавляет одну `a` слева и одну `b` справа. Стек из `a` и `b` всегда сбалансирован - именно это regex не может проверить.

Выводы: шаг за шагом

**Вывод (derivation)** - это последовательность применений правил, которая превращает стартовый символ в конечную строку из терминалов. На каждом шаге мы берём один нетерминал и заменяем его по одному из правил.

Возьмём грамматику арифметических выражений - ту самую, которую используют настоящие компиляторы:

Выведем строку `id + id * id` (аналог `a + b * c`):

**Leftmost derivation** - на каждом шаге заменяем самый левый нетерминал. **Rightmost derivation** - самый правый. Для однозначной грамматики оба приводят к одному дереву разбора.

Порядок шагов разный, но результат - один и тот же. Давайте напишем генератор строк по грамматике:

В компиляторах используют **rightmost derivation** в обратном порядке - это основа LR-парсинга (shift-reduce). Leftmost derivation используют в LL-парсерах (рекурсивный спуск).

Деревья разбора

**Дерево разбора (parse tree)** - это визуализация вывода. Оно показывает, какие правила были применены и в какой структуре. Корень - стартовый символ, листья - терминалы, внутренние узлы - нетерминалы.

Дерево разбора устраняет неоднозначность порядка шагов: leftmost и rightmost derivation дают **одно и то же дерево**, если грамматика однозначна. Дерево фиксирует структуру, а не порядок.

Построим дерево разбора для `id + id * id` по грамматике G₂:

Обратите внимание: дерево **кодирует приоритет операций**. Умножение `id * id` глубже в дереве (вычисляется первым), сложение - ближе к корню.

В компиляторе дерево разбора трансформируется в **AST (Abstract Syntax Tree)** - упрощённую версию без «лишних» узлов. Например, узлы E, T, F схлопываются, остаются только операции и операнды.

Неоднозначность грамматик

**Грамматика неоднозначна (ambiguous)**, если существует хотя бы одна строка, имеющая **два или более различных деревьев разбора**. Это катастрофа для компилятора - он не знает, как интерпретировать выражение.

Рассмотрим «наивную» грамматику выражений, где всё свалено в один нетерминал:

**Почему это опасно?** Для `2 + 3 * 4` дерево 1 даёт (2+3)*4 = 20, а дерево 2 даёт 2+(3*4) = 14. Компилятор с неоднозначной грамматикой будет генерировать непредсказуемый код!

Решение - **переписать грамматику**, чтобы приоритет и ассоциативность были «зашиты» в структуру правил:

**Inherently ambiguous languages** - существуют контекстно-свободные языки, для которых **не существует** однозначной грамматики. Пример: {aⁿbⁿcᵐ} ∪ {aⁿbᵐcᵐ}. Любая CFG для этого языка будет неоднозначна на строках вида aⁿbⁿcⁿ.

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

• **CFG = (V, Σ, R, S)** - переменные, терминалы, правила подстановки, стартовый символ
• **CFG строго мощнее** регулярных грамматик - может описывать {aⁿbⁿ}, вложенные скобки и другие нерегулярные языки
• **Вывод (derivation)** - последовательность применений правил: S ⟹ ... ⟹ строка
• **Дерево разбора** - визуализация структуры вывода, кодирует приоритет операций
• **Неоднозначная грамматика** - строка имеет ≥2 деревьев; обычно лечится иерархией нетерминалов

Связь с другими темами

CFG - мост между регулярными языками и полной вычислимости:

• Регулярные выражения и автоматы — CFG - следующий уровень иерархии Хомского после регулярных языков
• Автоматы с магазинной памятью (PDA) — PDA - вычислительная модель, эквивалентная CFG по мощности
• Алгоритм CYK — CYK - алгоритм парсинга для CFG за O(n³), использует динамическое программирование

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

• Почему иерархия нетерминалов E → T → F решает проблему приоритета операций? Что произойдёт, если добавить оператор возведения в степень - какой уровень он займёт?
• Язык {aⁿbⁿcⁿ | n ≥ 0} НЕ является контекстно-свободным. Интуитивно - почему CFG не может одновременно «считать» три группы символов?
• HTML позволяет вложенные теги: <div><div></div></div>. Почему для валидации HTML нужна CFG, а не regex?

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

• fl-11-pumping-lemma — Regular languages contrast motivates CFG power
• fl-02-chomsky — CFGs sit at level 2 of the Chomsky hierarchy
• comp-10-cfg — Compilers use CFGs for parser specifications
• fl-13-pda — PDAs are the machine equivalent of CFGs
• fl-16-pumping-cf — Context-free pumping lemma proves non-context-free languages