Парсеры: грамматики, recursive descent, Pratt, LR, PEG

В уроке 06 парсер уже всплывал как функция из сырого типа в строгий. То есть это не предикат “корректно ли”, а конструктор, который либо собирает типизированное значение, либо рассказывает, где сломался. Сегодня обобщаем приём: разбираем, что такое формальный язык, какие классы языков бывают, какими алгоритмами их обрабатывают, и где проходит граница между регуляркой и полноценным парсером. В финале напишем рабочий парсер арифметики двумя способами: руками в стиле recursive descent и через Pratt с приоритетами. Заодно посмотрим на экосистему генераторов парсеров.

Где парсер живёт в реальной программе

Парсер появляется тогда, когда формат входа сложнее, чем берёт JSON.parse плюс одна регулярка. Типичные места:

• Конфиги и манифесты со своим синтаксисом: TOML, YAML, INI, Caddyfile, nginx.conf, docker-compose-шаблоны.
• DSL для бизнес-правил: формула в Excel, шаблон в Liquid, фильтр в Sentry, выражение в Datalog или Prolog-стиле.
• Языки запросов: SQL, GraphQL, Kibana KQL, Lucene query, сама регулярка как отдельный DSL.
• Сетевые протоколы: текстовый HTTP/1.1, SMTP, IRC, IMAP, метаданные gRPC.
• Исходный код: компиляторы, линтеры, IDE, инструменты автоправок (codemod), форматтеры.
• Логи, особенно многострочные: трассировки исключений, JSON с человекочитаемым хвостом, нестандартные форматы.

Признак того, что без парсера не обойтись: нужны вложенные структуры, произвольная глубина, парные “открыть-закрыть”, переменное число элементов через разделитель. Регулярка такие конструкции не тянет, и ниже мы поймём, почему.

Грамматики и иерархия Хомского

Формальная грамматика описывает язык как набор правил. Каждое правило говорит, как один нетерминал заменяется на другую последовательность терминалов и нетерминалов. Лингвист Ноам Хомский в 1956 году ввёл четырёхуровневую классификацию по силе грамматик. Эта классификация называется иерархией Хомского и до сих пор задаёт словарь.

Тип	Класс языков	Чем распознаётся	Что не охватывает
3	регулярные	конечный автомат, регулярка	вложенные скобки
2	контекстно-свободные	стек, push-down автомат	язык aⁿ bⁿ cⁿ
1	контекстно-зависимые	линейно ограниченный автомат	алгоритмически неразрешимые вопросы
0	рекурсивно перечислимые	машина Тьюринга	по сути ничего

На практике 99 % задач лежат на уровне 2: это контекстно-свободные языки (CFG): JSON, JS, JSON с комментариями, арифметика. Уровень 1 встречается реже. Например, требование уникальности имён переменных строго говоря контекстно-зависимое, но его обычно выносят в отдельный проход семантического анализа, а не в парсер.

Уровень 3, регулярные языки, описывается конечным автоматом, для них работает обычная регулярка. Их главная слабость в том, что регулярка не умеет считать: она не отличит (((( от (((((. Поэтому парные скобки и вложенные структуры всегда поднимают на уровень CFG и стек-парсера.

BNF и EBNF

BNF (Backus-Naur Form), классическая нотация для записи CFG. Появилась в описании Algol 60 и до сих пор живёт в стандартах языков. Вот простая арифметика на BNF:

<expr>   ::= <term> "+" <expr>
           | <term> "-" <expr>
           | <term>

<term>   ::= <factor> "*" <term>
           | <factor> "/" <term>
           | <factor>

<factor> ::= "(" <expr> ")"
           | <number>

<number> ::= <digit> <number>
           | <digit>

<digit>  ::= "0" | "1" | "2" | "3" | "4"
           | "5" | "6" | "7" | "8" | "9"

Здесь <expr>, <term>, <factor> это нетерминалы, а строки в кавычках, терминалы. Грамматика выше задаёт правую ассоциативность через <term> + <expr> (а не <expr> + <term>); чтобы получить левую, привычную для арифметики, запись приходится усложнять (см. секцию о левой рекурсии ниже).

EBNF добавляет операторы повторения и опциональности и сокращает ту же арифметику:

expr   = term, { ("+" | "-"), term } ;
term   = factor, { ("*" | "/"), factor } ;
factor = number | "(", expr, ")" ;
number = digit, { digit } ;
digit  = "0" | "1" | ... | "9" ;

Запятая означает конкатенацию, фигурные скобки задают повторение от нуля раз, альтернативы разделяются |. Это стандарт ISO/IEC 14977.

JSON в EBNF:

json    = value ;
value   = object | array | string | number | "true" | "false" | "null" ;
object  = "{", [ pair, { ",", pair } ], "}" ;
pair    = string, ":", value ;
array   = "[", [ value, { ",", value } ], "]" ;

Уже видна вся структура: рекурсия value -> object -> pair -> value, повторения через запятую, опциональность через [ ... ]. По таким правилам можно построить парсер автоматически (через генератор) или написать руками (recursive descent).

Этапы парсинга

Парсинг редко бывает одношаговым. Типичный конвейер:

сырая строка
   |
   v
[ Lexer / Scanner ]   токены: NUMBER(42), PLUS, NUMBER(7), EOF
   |
   v
[ Parser ]            AST: Add { left: Num(42), right: Num(7) }
   |
   v
[ Semantic analysis ] разрешение имён, типы, проверка инвариантов
   |
   v
[ IR / Lower ]        промежуточное представление (control-flow graph,
                      three-address code, SSA)
   |
   v
[ Codegen / Interp ]  машинный код, байткод, или прямая интерпретация

• Лексер превращает поток символов в поток токенов. Токен это атомарный кирпичик: число, идентификатор, ключевое слово, оператор. Лексер убирает пробелы и комментарии, попутно может добавлять координаты (строка, столбец).
• Парсер строит дерево из токенов по правилам грамматики.
• AST это абстрактное синтаксическое дерево, отражающее структуру программы без лишних украшений. В отличие от дерева разбора (concrete syntax tree) AST не хранит скобки и ключевые слова как отдельные узлы.
• Семантический анализ проверяет смысл: переменная объявлена, типы совпадают, return соответствует сигнатуре. Это уже не работа парсера, а отдельный проход по AST.
• IR это упрощённый язык между AST и целевой платформой: LLVM IR, байткод V8, WebAssembly. У IR обычно линейная структура (basic blocks плюс CFG) и узкий набор операций.
• Кодогенерация превращает IR в машинный код или байткод. Альтернатива кодогенерации, интерпретатор, сразу выполняет AST или IR.

В простом DSL-парсере обычно остаются только лексер, парсер и AST. В полноценном компиляторе живут все шесть этапов.

Top-down против bottom-up

Алгоритмы парсинга делятся на две большие группы.

Top-down парсер строит дерево от корня к листьям. На каждом шаге он смотрит на текущий нетерминал и токен впереди, выбирает правило и рекурсивно разбирает каждый элемент правой части. Это естественный способ для человека: “разбираю выражение, значит первое, что ожидаю, это term”. В семью top-down входят recursive descent, LL(k) и LL-генераторы (ANTLR, JavaCC).

Bottom-up парсер идёт наоборот, от листьев к корню. Он читает токены в стек и на каждом шаге выбирает между двумя действиями: shift (положить токен в стек) и reduce (свернуть верхушку стека по правилу). В семью bottom-up входят LR(k) и его варианты SLR, LALR(1), Canonical LR(1), GLR.

Сильные и слабые стороны:

	Top-down (LL)	Bottom-up (LR)
ручная реализация	легко	очень сложно, обычно генератор
левая рекурсия	требует переписывания	поддерживает
сообщения об ошибках	естественные	требуют усилий
мощность	LL(1) ⊂ LL(k)	LR(1) сильнее LL(k)
где встречается	Python, Rust, парсеры TypeScript	C, GCC до 4.0, yacc/bison

В современных промышленных языках побеждают top-down парсеры: Python в 3.9 ушёл с LR на PEG, Rust с самого начала живёт на recursive descent, TypeScript-компилятор написан вручную в LL-стиле. Причина в понятных сообщениях об ошибках и в том, что такому парсеру проще быть инкрементальным для IDE.