Формальные грамматики и разбор
Грамматика — это правила, по которым из "абстрактных" символов порождают строки языка. Парсер в компиляторе делает обратное: по строке (исходному коду) восстанавливает, какие правила сработали. Без грамматики нет однозначного синтаксиса; без разбора нет 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.
Практика — от грамматики к коду
- Записать грамматику в BNF/EBNF (спецификация языка).
- Устранить левую рекурсию, если нужен LL.
- Сгенерировать парсер (ANTLR, yacc, tree-sitter) или написать рекурсивный спуск вручную.
- В действиях парсера строить 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 на
;или}).
Это инженерная надстройка над формальным выводом; теория указывает, на каком нетерминале и при каком входном токене дерево перестало строиться.
Упражнение
- Запишите BNF для списка
1, 2, 3(элементы через запятую) с опциональным хвостом. - Устраните левую рекурсию в
E → E + T | Tвручную (E'). - Постройте дерево вывода для
if a then if b then s else s2— сколько "висячих else" без правил приоритета?
Вопросы для самопроверки
- Что входит в кортеж
G = (N, Σ, P, S)? - Чем дерево вывода отличается от AST?
- Почему язык сбалансированных скобок не регулярный?
- Зачем устраняют левую рекурсию перед LL-парсером?
- Приведите пример неоднозначности в грамматике операторов или
if.
Дальше: Конечные автоматы и регулярные языки.