Теория языков программирования
Синтаксический анализ (Parsing)
Парсер превращает плоскую последовательность токенов в структурированное дерево, которое отражает смысл программы. Это мост между текстом и семантикой. Написать парсер - значит определить, что означает каждая конструкция языка.
- **V8/SpiderMonkey**: JavaScript парсеры используют recursive descent с ручными оптимизациями. Chrome парсит 1-2 MB JS за 10-20ms для каждой страницы
- **Prettier**: форматтер кода перепарсит и пересобирает AST для форматирования. Поддерживает 10+ языков через единый AST интерфейс
- **GraphQL**: PEG-based парсер в reference реализации. Каждый GraphQL запрос парсится, валидируется и выполняется
Recursive Descent парсинг
Recursive descent - самый интуитивный метод парсинга. Каждое правило грамматики - отдельная функция, которая вызывает функции для подправил. Читается почти как грамматика. GCC, Clang, rustc, TypeScript - все используют ручной recursive descent.
Recursive descent обрабатывает только LL(k) грамматики (левой рекурсии нет). Левую рекурсию (expr = expr '+' term) нужно устранять переписыванием грамматики.
Почему recursive descent не может напрямую обработать левую рекурсию (expr = expr '+' term)?
LL парсинг
LL(k) означает: Left-to-right scan, Leftmost derivation, k токенов lookahead. Recursive descent - ручная реализация LL(1) или LL(k). ANTLR генерирует LL(*) парсеры (произвольный lookahead через адаптивные предсказания).
LL(1) конфликты: если в таблице M[A, a] больше одной записи - грамматика неоднозначна для LL(1). Решения: рефакторинг грамматики, использование LL(k>1), или PEG грамматика с приоритетом.
Что означает 'k' в LL(k)?
LR парсинг
LR(k) - Left-to-right scan, Rightmost derivation (reversed). Bottom-up: сначала читаем токены, потом свёртываем в правила. LR(1) обрабатывает большинство промышленных грамматик (включая с левой рекурсией). yacc/bison генерируют LALR(1) парсеры.
LR vs LL: LR выразительнее (обрабатывает леворекурсивные грамматики), но таблицы LR(1) огромны. LALR(1) (Look-Ahead LR) - компромисс: таблицы как у SLR, выразительность близка к LR(1). yacc/bison используют LALR(1).
Чем LR парсер принципиально отличается от LL?
PEG грамматики
PEG (Parsing Expression Grammar) - альтернатива CFG. Оператор выбора `/` (приоритетный выбор) вместо `|`. Никакой неоднозначности: первая альтернатива, которая успешно разобрала - победитель. Packrat parsing делает PEG O(n) через memoization.
PEG грамматики - всегда лучший выбор, потому что однозначны и O(n)
PEG имеет ограничения: не все CFG языки выражаются в PEG, левая рекурсия требует расширений, packrat требует O(n) памяти
LALR(1) парсеры (yacc) используются в производственных языках (C, Go, Bash) десятилетиями. PEG хорош для создания языков с нуля, где можно спроектировать грамматику под PEG ограничения
Почему PEG грамматики никогда не бывают неоднозначными?
Ключевые идеи
- **Recursive descent**: каждое правило грамматики = функция. Читаем слева направо, строим AST сверху вниз. Не поддерживает левую рекурсию
- **LL(k)**: k токенов lookahead. ANTLR генерирует LL(*). Recursive descent - ручной LL
- **LR(k)**: bottom-up, обрабатывает левую рекурсию. yacc/bison - LALR(1). Выразительнее LL, но таблицы сложнее
- **PEG**: приоритетный выбор / - никакой неоднозначности. Packrat memoization - O(n). pest (Rust), peg.js
Связанные темы
Парсинг - второй этап компилятора:
- Лексер — Парсер получает токены от лексера
- AST и семантический анализ — Парсер строит AST который анализируется далее
Вопросы для размышления
- Rustc использует recursive descent и специально избегает генераторов парсеров. Почему ручной парсер даёт лучшие сообщения об ошибках?
- Python 3.9 перешёл с LL(1) на PEG (pegen). Какие ограничения LL(1) грамматики вынудили это изменение?
- LR парсеры выразительнее LL, но все современные языки (Rust, Go, Swift) используют recursive descent. Почему производительность парсера важнее выразительности грамматики?