КС-грамматики: правила и вывод

Контекстно-свободная грамматика описывает вложенные структуры — выражения, блоки, скобки, — на которых конечные автоматы спотыкались.

КС-грамматика — грамматика, все правила которой имеют вид A → γ, где A — один нетерминал, а γ — любая строка из терминалов и нетерминалов.

Анатомия грамматики

КС-грамматика — это четвёрка (V, Σ, P, S): нетерминалы V (синтаксические категории, обычно заглавные), терминалы Σ (символы языка), правила P и стартовый символ S. Ключевая особенность: слева от стрелки — ровно один нетерминал, безо всякого контекста (отсюда «контекстно-свободная»: A можно заменить на γ где угодно, независимо от соседей). Это и даёт силу описывать рекурсию: нетерминал может ссылаться сам на себя.

Канонический пример — арифметические выражения:

E → E + E
E → E * E
E → ( E )
E → num

Здесь E — нетерминал «выражение», num и +,*,(,) — терминалы.
Правило E → ( E ) рекурсивно: выражение может содержать выражение.

Вывод строки

Вывод — последовательность подстановок от S до строки из одних терминалов. На каждом шаге берём один нетерминал и заменяем его правой частью какого-то правила (записываем ⇒). Например, для грамматики скобок S → ( S ) S | ε выведем «(())»:

S ⇒ ( S ) S ⇒ ( ( S ) S ) S ⇒ ( ( ) S ) S ⇒ ( ( ) ) S ⇒ ( ( ) )
(последовательно заменяем S, в конце S → ε убирает лишние)

Грамматика S → ( S ) S | ε порождает ровно все сбалансированные скобочные последовательности — тот самый язык, что был не по зубам регуляркам. Стек «прятался» в рекурсии правила.

Порождение строк программно

Сгенерируем все сбалансированные скобочные строки до заданной длины перебором выводов грамматики Дика (язык правильных скобок). Используем рекурсивный генератор.

from functools import lru_cache

# грамматика Дика: S -> ( S ) S | ε ; генерируем все строки длины 2n
@lru_cache(maxsize=None)
def dyck(n):
    if n == 0:
        return [""]
    res = []
    for i in range(n):                 # i пар внутри скобок, n-1-i снаружи
        for inner in dyck(i):
            for rest in dyck(n - 1 - i):
                res.append("(" + inner + ")" + rest)
    return res

for n in range(4):
    seqs = dyck(n)
    print(f"{2*n} символов ({len(seqs)} шт): {seqs}")

Вывод:

0 символов (1 шт): ['']
2 символов (1 шт): ['()']
4 символов (2 шт): ['()()', '(())']
6 символов (5 шт): ['()()()', '()(())', '(())()', '(()())', '((()))']

Числа 1, 1, 2, 5 — это числа Каталана: количество правильных скобочных последовательностей. Грамматика породила в точности все сбалансированные строки.

Как работает под капотом

КС-грамматики — это BNF (форма Бэкуса-Наура), на которой записан синтаксис почти всех языков программирования. Когда в спецификации Python пишут `if_stmt: 'if' test ':' suite`, это правило КС-грамматики. Парсер компилятора берёт грамматику и по входному коду восстанавливает вывод — то есть доказывает, что программа порождается грамматикой, попутно строя дерево разбора. Контекстная свобода (A заменяется независимо от соседей) — почему синтаксис можно разбирать локально и эффективно; именно она делает возможными быстрые парсеры (LL, LR).

Частые ошибки

Ставить несколько символов слева от стрелки. Это уже контекстно-зависимая грамматика (тип 1), не КС. В КС слева строго один нетерминал.

Путать терминалы и нетерминалы. Терминалы — реальные символы выхода; нетерминалы — временные, в финальной строке их не должно остаться.

Забывать базовый случай рекурсии. Без правила-выхода (например, S → ε или E → num) вывод никогда не завершится строкой терминалов.

Итог

• КС-грамматика: правила A → γ с одним нетерминалом слева; описывает рекурсивные, вложенные структуры.
• Вывод — цепочка подстановок от S до строки терминалов; S → ( S ) S | ε задаёт сбалансированные скобки.
• КС-грамматики = BNF: на них записан синтаксис языков программирования.
• Контекстная свобода делает синтаксический разбор локальным и эффективным.