Генераторы парсеров: Bison, ANTLR, tree-sitter

Когда вы набираете в VS Code новую строку, под капотом происходит чудо: парсер за 2 миллисекунды обновляет AST файла на 50 000 строк и подсвечивает синтаксис. А в это время рядом GCC компилирует ваш C-код парсером, написанным на Bison-грамматике 30-летней давности. Это два мира парсеров с разными требованиями.

• **PostgreSQL** - 50 000 строк Bison-грамматики, в которой каждая строчка - переговоры между LALR-конфликтами; парсер один из старейших в проекте
• **Hibernate HQL** написан на ANTLR; парсер за 20 лет обработал миллиарды запросов в Java-приложениях
• **GitHub Code Search 2024** использует tree-sitter для построения индексов на 200M+ репозиториев - инкрементальность критична на таком масштабе

Yacc и Bison

В 1975 году Стивен Джонсон в Bell Labs написал Yacc - Yet Another Compiler-Compiler. Идея: вместо рукописного парсера C компилятор сам генерирует LALR(1)-таблицы по грамматике. Через 10 лет вышел GNU **Bison** - совместимая замена с расширениями. На Bison написаны парсеры GCC, PostgreSQL и Ruby; одна `.y`-файл превращается в готовый `parser.c`.

Bison-грамматика - это правила в BNF плюс semantic actions (C-код в фигурных скобках). При парсинге Bison строит **parse table** и работает как state machine со стеком. Конфликты shift/reduce и reduce/reduce - типичная боль: разработчик правит грамматику до устранения конфликтов либо явно объявляет приоритеты через `%left`, `%right`, `%nonassoc`.

**LALR(1) vs LR(1)**: LALR(1) объединяет состояния LR(1) с одинаковым ядром, давая меньше состояний (тысячи вместо десятков тысяч), но иногда создаёт ложные reduce-reduce конфликты на грамматиках, которые LR(1) парсил бы чисто. Bison сегодня поддерживает оба.

ANTLR: LL(*) и сильная типизация

Bison требует мыслить в терминах LALR-состояний и shift/reduce-конфликтов, что нелегко даже опытным разработчикам. Теренс Парр (Terence Parr) спроектировал **ANTLR** - генератор top-down парсеров с алгоритмом **LL(*)** (адаптивный lookahead). LL-парсеры читаются как рекурсивный спуск, что упрощает отладку и переписывание.

На ANTLR написаны: парсер Hibernate HQL, плагины IntelliJ для языков, Twitter Search Query parser, parser стандарта SQL в Presto/Trino. Генерирует Java, C#, Python, Go и другие. Главная фишка - **adaptive prediction**: для конкретной альтернативы выбирается ровно столько lookahead, сколько нужно (может быть сколько угодно символов, в отличие от LL(1)).

**Visitor vs Listener pattern**: ANTLR генерирует оба интерфейса. Listener-паттерн обходит AST автоматически через `walk()`, удобен для side-effects. Visitor возвращает значения и используется для интерпретации/трансформации.

tree-sitter: парсинг для IDE

В IDE при наборе кода парсер вызывается на **каждое нажатие клавиши**. Обычный LALR-парсер этого не выдержит: переразбор файла на 10 000 строк - сотни миллисекунд. Atom/GitHub в 2018 выпустил **tree-sitter** - инкрементальный парсер, который обновляет AST за 1-5 мс, разбирая только изменённый участок.

tree-sitter использует **GLR (Generalized LR)** парсер с error-recovery: умеет жить с синтаксическими ошибками (важно для IDE, где код всегда невалиден в процессе набора). Один AST содержит и валидные узлы, и узлы ошибок. Используется в Neovim, GitHub code search, Helix, многих language server. Грамматика пишется на JavaScript (DSL).

**tree-sitter в Neovim**: при редактировании файла парсится только окно изменений; всё остальное AST переиспользуется. Это даёт highlighting и folding без задержек даже на 100k-строчных файлах.

Error recovery в парсерах

Компилятор C сообщает только об одной ошибке за раз - и это плохо: исправил, перекомпилировал, увидел следующую, через полчаса всё работает. Современные компиляторы (rustc, clang, TypeScript) показывают **десятки ошибок за один проход**. Это требует **error recovery**: после ошибки парсер не падает, а пытается найти безопасную точку синхронизации и продолжить.

Классические стратегии: **panic mode** (пропускать токены до маркера типа `;` или `}`), **phrase-level recovery** (вставлять пропущенные токены), **error productions** (правила в грамматике, моделирующие частые ошибки, например `expr: expr '+' /* missing */`). tree-sitter и Roslyn (C#) используют ML-driven recovery - подбирают исправление по вероятностной модели.

**Why это критично для language servers**: VS Code, IntelliJ показывают подчёркивания ошибок в реальном времени. Если парсер падает на первой ошибке, остальные участки кода не получат подсветку и автокомплит. Error recovery даёт UX как у Word с грамматической проверкой.

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

• **Bison (LALR)** - проверенный временем выбор для компиляторов: один проход, эффективные таблицы, но shift/reduce конфликты требуют опыта
• **ANTLR (LL(*))** - удобнее в работе: рекурсивный спуск читается как код, левая рекурсия переписывается автоматически, есть Visitor/Listener
• **tree-sitter (GLR + incremental)** оптимизирован для IDE: инкрементальный re-parse за миллисекунды плюс error recovery с ERROR-узлами в AST
• **Error recovery** - не опция, а требование для современных компиляторов: panic mode, phrase-level recovery, error productions дают UX 'все ошибки сразу'
• Выбор парсера = выбор профиля нагрузки: один проход на чистом вводе vs тысячи re-parse на постоянно меняющемся файле

Связанные темы

Возвращаясь к двум мирам: компиляторы и IDE используют разные парсеры по разным причинам. Эта тема связана с:

• Лексический анализ и токенизация — Любой генератор парсеров требует лексер; tree-sitter совмещает их, Bison обычно использует Flex отдельно
• LR-парсинг и парсер-таблицы — LALR в Bison - оптимизация LR-таблиц; понимание LR-алгоритма необходимо для разрешения конфликтов

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

• Если бы PostgreSQL переписывали с нуля сегодня, на чём бы написали парсер? Bison остаётся для совместимости или потому что лучший выбор для DBMS?
• tree-sitter жертвует чистотой AST (ERROR-узлы) ради скорости. В каких сценариях этот компромисс неприемлем?
• Почему компиляторы как rustc и clang используют рукописные парсеры, а не генераторы? Контроль над error messages или что-то ещё?

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

• comp-13-peg-packrat — PEG - одна из формальных основ для генераторов типа pest
• comp-12-lr-parsing — Bison генерирует LALR-парсер - LR нужно понимать
• comp-11-recursive-descent — ANTLR строит LL(*) рекурсивный спуск
• comp-15-pratt-parser — Pratt - ручной парсер vs генераторный - компромиссы
• alg-01-big-o — Время разбора зависит от класса грамматики - нужен Big O
• fl-12-cfg