Формальные грамматики и разбор

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Грамматика — это правила, по которым из «абстрактных» символов порождают строки языка. Парсер в компиляторе делает обратное: по строке (исходному коду) восстанавливает, какие правила сработали. Без грамматики нет однозначного синтаксиса; без разбора нет AST.

Обзор иерархии: Формальные языки и автоматы. Автоматы: конечные, магазинные. Этапы компиляции: Программа — компиляция.

Для читателя без математического фона

Грамматика — это правила «как собирать правильные фразы» из кусочков. В русском: «предложение = подлежащее + сказуемое + …». В коде: «выражение = выражение + терм | терм». Парсер читает готовую строку (исходник) и проверяет: можно ли её разобрать по этим правилам, и какое дерево получилось.

Бытовой пример	Аналог в грамматике
Рецепт блюда	правила P
Готовое блюдо	предложение (только терминалы)
Промежуточный черновик с пометками «ещё добавить соус»	сентенциальная форма (терминалы + нетерминалы)
Схема «из чего состоит»	дерево вывода
Упрощённая картинка для повара	AST в компиляторе

Терминал — «лист», конкретный символ в тексте (+, if, имя переменной). Нетерминал — «заготовка» (Expr, Stmt), которую ещё нужно развернуть по правилам.

Направления изучения грамматик и языков

Направление	Вопрос	Пример
Порождение	как сгенерировать все правильные строки?	правила E → E + T | T
Распознавание	принадлежит ли слово языку?	парсер на входе a+b*c
Анализ	какая структура у слова?	дерево вывода → AST
Преобразование	как упростить грамматику для алгоритма?	убрать левую рекурсию
Сравнение классов	что мощнее?	регуляр ⊂ КС ⊂ …

В разработке вы постоянно в распознавании и анализе: JSON, SQL, свой DSL, конфиги. Порождение видно в генераторах кода и тестовых данных.

Основные понятия порождающих грамматик

Формальная грамматика (в смысле Хомского):

G = (N, Σ, P, S)

Символ	Имя	Пример
N	нетерминалы (переменные)	E, T, Stmt
Σ	терминалы (алфавит «букв»)	+, if, id, (
P	правила (продукции)	E → E + T
S ∈ N	аксиома (стартовый символ)	E

Слово (предложение) — конечная строка только из терминалов.

Вывод

Шаг вывода: в текущей строке, где среди символов есть нетерминал A, выбирают правило A → α и заменяют одно вхождение A на α.

Вывод — цепочка таких шагов от S до слова из терминалов.

Пример (арифметика, упрощённо):

S = E
E → E + T | T
T → T * F | F
F → ( E ) | id

Слово id + id:

E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + F ⇒ id + id

Как читать цепочку ⇒: на каждом шаге выбирают один нетерминал в строке и заменяют его на правую часть правила (здесь — левыйmost, самый левый нетерминал).

Шаг	Текущая строка	Правило	Комментарий
0	E	E → E + T	«выражение — выражение плюс терм»
1	E + T	E → T	левый E свернули в T
2	T + T	T → F
3	F + T	F → id	первый операнд
4	id + T	T → F
5	id + F	F → id	второй операнд
6	id + id	—	только терминалы — предложение

Символ id здесь — один терминал «идентификатор» (лексер в реальном компиляторе выдаст конкретное имя, например foo).

Сентенциальные формы

• Сентенциальная форма — любая строка (терминалы + нетерминалы), полученная из S за конечное число шагов.
• Предложение — сентенциальная форма без нетерминалов.

Язык L(G) — множество всех предложений, выводимых из S.

Левый и правый вывод

При каждом шаге можно заменять левыйmost или правыйmost нетерминал — получаются левосторонний и правосторонний выводы.

Парсер	Какой вывод строит
LL(k)	левый — «сверху вниз» совпадает с порядком развёртки
LR	правый — «снизу вверх» сворачивает к корню

Для однозначной грамматики левый и правый вывод одного слова совпадают как дерево; для неоднозначной — могут дать разные деревья при одном слове.

Дерево вывода

Дерево вывода фиксирует структуру: корень — S, дети — символы правой части применённого правила, листья — терминалы слева направо дают слово.

        E
       /|\
      E + T
      |   |
      F   F
      |   |
     id  id

Компилятор строит AST — сжатую версию дерева без «синтаксического шума» (скобки, лишние уровни). См. семантический анализ.

	Дерево вывода	AST
Назначение	показать какие правила сработали	удобно вычислять и оптимизировать
Скобки, запятые	часто остаются как узлы	часто убирают
Несколько уровней E, T, F	полная цепочка грамматики	обычно узел + с двумя детьми

Пример: для id + id * id AST — корень +, слева id, справа поддерево * с двумя id — без промежуточных нетерминалов E, T, F.

Нотации BNF и EBNF

BNF (Backus–Naur Form):

<expr> ::= <expr> "+" <term> | <term>
<term> ::= <term> "*" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <id>

EBNF добавляет удобства: { ... } — повтор, [ ... ] — опционально, "+" — терминал.

Спецификации JSON Schema, OpenAPI, языки вроде W3C — наследники той же идеи.

Классификация грамматик Н. Хомского

Тип задаётся ограничением на вид правил α → β:

Тип	Ограничение на правило	Автомат	Пример языка
0	без ограничений (кроме длины)	МТ	всё алгоритмически порождаемое
1	контекстно-зависимые: αAγ → αβγ, `	β	≥ 1`
2	контекстно-свободные: A → β	МП-автомат	сбалансированные скобки
3	регулярные (праволинейные): A → aB или A → a	КА	суффикс ab, чётное число a

Вложение: тип 3 ⊂ тип 2 ⊂ тип 1 ⊂ тип 0.

Практический ориентир

Лексер — почти всегда регулярный (тип 3). Синтаксис выражений и блоков — КС (тип 2). Семантика типов и анализ потока — уже отдельные алгоритмы.

Грамматический разбор

Разбор (parsing) — по слову w построить дерево вывода (или доказать, что w ∉ L(G)).

Стратегия	Идея	Примеры алгоритмов
Сверху вниз	от S к слову, «разворачиваем» нетерминалы	рекурсивный спуск, LL(k)
Снизу вверх	от слова к S, «сворачиваем» фрагменты	LR, LALR, SLR
Универсальные для КС	CYK (динамическое программирование)	учебные, XML-подобные

В компиляторе упоминаются рекурсивный спуск, LR/LALR — это инженерные реализации для детерминированных КС-грамматик.

LL и LR — интуиция

• LL — читает вход слева направо, строит левый вывод; «предсказывает» по lookahead, какое правило применить.
• LR — тоже слева направо, но правый вывод; сильнее по классу грамматик, стандарт для yacc/Bison.

Конфликты shift/reduce в LR — грамматика неоднозначна или нужна другая таблица.

Неоднозначность

Грамматика неоднозначна, если существует строка w ∈ L(G), для которой есть два различных дерева вывода (эквивалентно: два разных левых или два разных правых вывода — в зависимости от постановки).

Не путать с конфликтом shift/reduce в LR: таблица может быть построена с приоритетами, хотя грамматика формально неоднозначна; генераторы парсеров часто ограничивают класс грамматик, чтобы таблица была детерминированной.

Классика — «висячий else»:

stmt ::= if expr then stmt
       | if expr then stmt else stmt
       | other

Для вложенных if без else неясно, к какому if относится else. Решения: переписать грамматику, приоритеты в yacc, явные endif в языке (Ada, Lua).

Неоднозначные КС-грамматики не всегда приводят к неоднозначным LR-таблицам (иногда таблица + приоритеты спасают), но для генераторов парсеров лучше однозначная грамматика.

Неоднозначность выражений a + b * c

Одна строка — два дерева (приоритет * vs +):

   E              E
  /|\            / \
 E + T          T   + T
 |   |          |     |
 T   T          F     F
 |   |          |     |
 F   F          a     *
 |   |                / \
 a   *               F   F
    / \              |   |
   F   F             b   c
   |   |
   b   c

Языки фиксируют приоритет грамматикой (T под E, F под T) или приоритетами в yacc. Без этого семантика «по умолчанию» не определена.

Преобразования КС-грамматик

Перед построением парсера грамматику нормализуют:

Преобразование	Зачем
Удаление ε-правил A → ε	упростить таблицы (кроме S при необходимости)
Удаление бесплодных нетерминалов	не порождают терминальных строк
Удаление недостижимых из S	«мусор» в грамматике
Устранение левой рекурсии A → Aα | …	LL(1) не работает с левой рекурсией
Приведение к CNF	A → BC или A → a — теоремы и CYK

Левая рекурсия (естественна для левоассоциативных операторов):

E → E + T | T

Для LL заменяют на правую итерацию через вспомогательный нетерминал:

E  → T E'
E' → + T E' | ε

В LR левая рекурсия часто нормальна — отсюда различие инструментов.

Пример ε-удаления: если было List → Item List | ε, после удаления ε нужно явно разрешить пустой список отдельным правилом или стартовым символом.

LL(1) — FIRST и FOLLOW (практика генераторов)

Для детерминированного разбора сверху вниз на каждом нетерминале A смотрят:

• FIRST(α) — с каких терминалов могут начинаться строки, выводимые из α.
• FOLLOW(A) — какие терминалы могут идти сразу после A в каком-то выводе.

Таблица LL(1): строка — нетерминал, столбец — текущий входной терминал; ячейка — какое правило A → β применить. Конфликт в ячейке → грамматика не LL(1) (нужен k > 1 или LR).

Инструменты вроде ANTLR, расчёт FIRST/FOLLOW в учебниках — прямое продолжение этой таблицы.

CYK (идея алгоритма)

Для грамматики в CNF (A → BC или A → a) проверка «слово w длины n в языке?» — динамическое программирование по подстрокам: O(n³) времени, универсально для КС, но на больших n тяжело.

Используют в учебных целях и для узких грамматик; промышленные парсеры редко на чистом CYK.

Лемма о накачке для КС (интуиция)

Если язык КС, то для достаточно длинного слова z ∈ L можно разбить z = uvxyz так, что «накачанные» u vⁿ x yⁿ z всё ещё в L (с условиями на длину v,y).

Следствие: { aⁿbⁿ | n ≥ 0 } — не регулярный (уже регулярная лемма); { aⁿbⁿcⁿ } — не КС (доказательство накачкой для КС).

Связь грамматик и автоматов

Грамматика	Автомат
Регулярная (тип 3)	ДКА / НКА
КС (тип 2)	МП-автомат
Тип 0	Машина Тьюринга

Теорема: язык генерируется КС-грамматикой тогда и только тогда, когда распознаётся МП-автоматом.

Регулярные грамматики (праволинейные A → aB | a) — то же, что регулярные языки и regex.

Практика — от грамматики к коду

1. Записать грамматику в BNF/EBNF (спецификация языка).
2. Устранить левую рекурсию, если нужен LL.
3. Сгенерировать парсер (ANTLR, yacc, tree-sitter) или написать рекурсивный спуск вручную.
4. В действиях парсера строить AST и диагностировать ошибки с позицией в исходнике.

PEG (parsing expression grammars) — альтернатива: упорядоченный выбор e1 / e2 («первый успешный»), не всегда совпадает с классическими КС.

Рекурсивный спуск (минимальный парсер выражений)

Грамматика E → E + T | T, T → T * F | F, F → ( E ) | id — классическая взаимная рекурсия (статья 41):

class ParseError(Exception):
    pass

class Parser:
    def __init__(self, tokens: list[str]):
        self.tokens = tokens
        self.i = 0

    def peek(self) -> str | None:
        return self.tokens[self.i] if self.i < len(self.tokens) else None

    def eat(self, expected: str | None = None) -> str:
        tok = self.peek()
        if tok is None or (expected and tok != expected):
            raise ParseError(f"ожидался {expected!r}, получен {tok!r}")
        self.i += 1
        return tok

    def parse_E(self):
        node = ("E", self.parse_T())
        while self.peek() == "+":
            self.eat("+")
            node = ("+", node, self.parse_T())
        return node

    def parse_T(self):
        node = ("T", self.parse_F())
        while self.peek() == "*":
            self.eat("*")
            node = ("*", node, self.parse_F())
        return node

    def parse_F(self):
        if self.peek() == "(":
            self.eat("(")
            node = self.parse_E()
            self.eat(")")
            return node
        if self.peek() == "id":
            return ("id", self.eat("id"))
        raise ParseError("ожидался id или (")

print(Parser(["id", "+", "id", "*", "id"]).parse_E())

Для LL(1) ту же грамматику сначала устраняют левую рекурсию (E'); LR-парсеры часто оставляют левую рекурсию — см. таблицу выше.

Ошибки разбора в UX

Хороший парсер возвращает не «syntax error», а:

• позицию (строка, столбец);
• ожидаемые терминалы (ожидался ';', ожидался ')');
• иногда восстановление (panic-mode, sync на ; или }).

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

Мини-лабораторная

1. Запишите BNF для списка 1, 2, 3 (элементы через запятую) с опциональным хвостом.
2. Устраните левую рекурсию в E → E + T | T вручную (E').
3. Постройте дерево вывода для if a then if b then s else s2 — сколько «висячих else» без правил приоритета?

Контрольные вопросы

1. Что входит в кортеж G = (N, Σ, P, S)?
2. Чем дерево вывода отличается от AST?
3. Почему язык сбалансированных скобок не регулярный?
4. Зачем устраняют левую рекурсию перед LL-парсером?
5. Приведите пример неоднозначности в грамматике операторов или if.

Дальше: Конечные автоматы и регулярные языки.

---