LL и LR грамматики

ANTLR4 генерирует парсер для Java из 500-строчной грамматики. GNU bison генерирует C-парсер для GCC. Tree-sitter строит синтаксическое дерево C++ файла за 5 мс в VS Code при каждом нажатии клавиши. За всем этим - две идеи 1960-х годов: LL и LR. Понять их - значит понять, почему парсинг - решённая задача и почему HTML парсится не regex-ом.

• **ANTLR4 (LL(*)):** генератор парсеров для Java, C#, Python, Go. Используется в Hibernate, Apache Spark, Twitter. Грамматики для 200+ языков: grammar-v4 репозиторий на GitHub
• **GNU bison (LALR(1)):** генерирует C-парсеры для GCC, GNU Bash, Ruby MRI, PostgreSQL SQL-парсера. Один из старейших и самых используемых инструментов в компиляторостроении
• **Tree-sitter (GLR):** инкрементальный парсер, встроенный в Neovim, GitHub Copilot, Helix. Разбирает код с ошибками в реальном времени, обновляет только изменившиеся поддеревья
• **Go compiler (рекурсивный спуск):** LL-парсер написан вручную без генераторов - это позволяет выдавать детальные сообщения об ошибках и контролировать производительность

LL-парсинг: нисходящий анализ

Открывается файл `main.py`. Python-парсер читает `def` и сразу знает: это объявление функции. Он раскрывает нетерминал FuncDef ещё до того, как прочитал имя или аргументы. Это **LL-парсинг** - Left-to-right scan, Leftmost derivation. Парсер смотрит вперёд на k токенов и выбирает правило грамматики сверху вниз.

**LL(k)-грамматика:** грамматика, в которой достаточно смотреть на k токенов вперёд, чтобы однозначно выбрать правило. LL(1) - смотрим на 1 токен. LL(*) (ANTLR4) - смотрим сколько нужно. Алгоритм: рекурсивный спуск с предсказывающими таблицами. Читает левый терминал, строит левостороннее дерево вывода.

Проблема LL: **левая рекурсия**. Правило `E -> E + T` заставляет парсер бесконечно вызывать `parse_E`. ANTLR4 автоматически устраняет левую рекурсию - преобразует в правую рекурсию с накоплением. Ручной рекурсивный спуск требует переписывания грамматики вручную (как `E' -> + T E'` в примере выше).

LR-парсинг: восходящий анализ

yacc, GNU bison, мейнстримные C/C++ компиляторы - все они используют **LR-парсинг**. Left-to-right scan, Rightmost derivation in reverse. Парсер накапливает токены в стек и решает: свернуть вершину стека в нетерминал (reduce) или сдвинуть следующий токен (shift). Никакой рекурсии, никаких проблем с левой рекурсией - LR обрабатывает её естественно.

**LR(k):** читает k токенов lookahead при принятии решения shift/reduce. LR(0): без lookahead. SLR(1): используют FOLLOW-множества. LALR(1): Look-Ahead LR, мощнее SLR. LR(1): полный, но таблицы огромные. На практике LALR(1) - золотой стандарт (yacc, bison). LR мощнее LL: каждый LL(k)-язык есть LR(k)-язык, но не наоборот.

LR-парсер строит дерево снизу вверх. Ключевое преимущество: **естественный приоритет операций**. Если в таблице перехода `*` конкурирует с `+` при принятии решения shift/reduce, конфликт разрешается явно заданным приоритетом. Это то, что позволяет yacc-грамматикам описывать арифметику с приоритетами в несколько строк.

FIRST и FOLLOW: множества предсказания

Чтобы построить таблицу разбора, нужно знать: какой токен может начинать вывод нетерминала? Это **FIRST**. И: какой токен может следовать за нетерминалом? Это **FOLLOW**. Вычисление этих множеств - алгоритмический процесс, автоматизированный в yacc, ANTLR, Tree-sitter.

**FIRST(α):** множество терминалов, с которых может начинаться строка, выводимая из α. Если α =>* ε, то ε ∈ FIRST(α). **FOLLOW(A):** множество терминалов t, которые могут стоять сразу после нетерминала A в любой сентенциальной форме. $ (конец строки) всегда входит в FOLLOW стартового символа.

**Конфликт FIRST/FIRST:** два правила для одного нетерминала начинаются с одинакового токена - LL(1) не может выбрать. **Конфликт FIRST/FOLLOW:** правило может вывести ε, но FOLLOW нетерминала пересекается с FIRST другого правила. Оба типа конфликтов означают: грамматика не является LL(1). Либо переписывать грамматику, либо увеличивать k, либо переходить на LR.

Таблицы разбора и конфликты

FIRST и FOLLOW превращаются в **таблицы разбора** - двумерные массивы [нетерминал][токен] -> правило. Для LL(1): если встречаем нетерминал A и токен t, смотрим в таблицу и получаем одно правило. Для LR: таблица действий [состояние][токен] -> shift/reduce/accept. Конфликт в таблице = грамматика не принадлежит классу.

Tree-sitter использует **GLR (Generalized LR)** - алгоритм, параллельно разрабатывающий несколько возможных деревьев разбора. Это позволяет парсить даже неоднозначные грамматики и частично некорректный код (что критично для IDE). Цена: квадратичное время в худшем случае. На практике Tree-sitter применяет оптимизации и остаётся быстрым.

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

• **LL(k):** нисходящий, рекурсивный спуск, смотрит k токенов вперёд. Проблема - левая рекурсия (устраняется механически). ANTLR4 реализует LL(*)
• **LR(k):** восходящий, shift/reduce на стеке, мощнее LL. LALR(1) = практический стандарт (yacc/bison). Обрабатывает левую рекурсию без преобразований
• **FIRST/FOLLOW** - множества для построения таблиц разбора. Конфликт в таблице = грамматика не принадлежит классу
• **Иерархия мощности:** LL(1) ⊂ LL(*) ≈ LALR(1) ⊂ LR(1) ⊂ GLR (произвольные CFG)

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

LL/LR парсинг - практическая реализация теории КС-грамматик:

• Контекстно-свободные грамматики — LL/LR разбирают именно КС-языки - тип 2 иерархии Хомского
• Стековые автоматы — LR-парсер - это детерминированный PDA; LL - частный случай через рекурсию стека вызовов
• Parser combinators — Альтернатива генераторам: парсеры как функции первого класса, PEG-семантика вместо CFG

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

• Почему большинство языков программирования спроектированы так, чтобы их грамматика была LALR(1)? Какие преимущества это даёт разработчикам компиляторов?
• Tree-sitter разбирает код с синтаксическими ошибками и всё равно строит дерево. Как это возможно, если стандартный LR-парсер останавливается на первой ошибке?
• Go-компилятор написан как ручной рекурсивный спуск, а не через генератор вроде ANTLR. Какие у этого преимущества и недостатки?

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

• comp-12-lr-parsing