PEG и Packrat-парсинг

Парсер Python до версии 3.9 годами страдал от ограничений LL(1)-генератора pgen: f-strings парсились отдельным регулярным выражением внутри лексера, expression-конкретные конструкции требовали хаков, pattern matching казался невозможным. В 2020 году Гвидо ван Россум, Павел Грановский и Лисандро Нальпас переписали ядро Python на PEG-парсер (PEP 617). Pattern matching пришёл в Python 3.10 через год - грамматика позволила. История PEG - это история про то, как смена модели разбора с CFG на детерминированную PEG открыла языку возможности, недоступные предыдущие 20 лет.

• **Python 3.9+ (PEP 617):** ядро языка парсится PEG-парсером с мемоизацией - именно это позволило добавить structural pattern matching
• **Peggy / PEG.js:** генераторы PEG-парсеров для JavaScript, используются в Babel, Markdown-It и сотнях DSL-инструментов
• **lark / pyparsing / parsimmon:** библиотеки PEG-композиции для построения DSL, конфигурационных языков и query-парсеров

PEG: грамматики без неоднозначностей

Контекстно-свободные грамматики (CFG) Хомского описывают множество строк - но не способ их разбора. Классическая грамматика арифметики допускает 1+2*3 разобрать как (1+2)*3 или 1+(2*3); CFG говорит 'обе верны', хотя смысл разный. Чтобы получить парсер, инженеру приходится дописывать приоритеты, разрешать конфликты shift/reduce и бороться с амбигвальностью. В 2004 году Брайан Форд (MIT) предложил Parsing Expression Grammars (PEG) - семейство грамматик, в котором амбигвальность невозможна по построению. PEG описывает не множество строк, а алгоритм разбора. Каждое правило - детерминированная функция, возвращающая либо успех с длиной совпадения, либо отказ.

PEG-операторы: e1 e2 - последовательность; e1 / e2 - упорядоченный выбор (пробует e1, при отказе - e2); e* - ноль или больше; e+ - один или больше; e? - опционально; &e - lookahead без потребления; !e - negative lookahead. Эти операторы расположены в фиксированной иерархии и гарантируют детерминированный разбор. Современные парсеры на PEG: Python's PEP 617 (Python 3.9+) полностью использует PEG-парсер; ANTLR 4 - PEG-подобная схема; библиотеки lark, pyparsing, peg.js, parsimmon.

Упорядоченный выбор: e1 / e2 вместо e1 | e2

Главное отличие PEG от CFG - оператор / вместо |. В CFG альтернативы коммутативны: A | B и B | A эквивалентны. В PEG операция / упорядоченная: парсер сначала пробует левую альтернативу, и только если она потерпела неудачу, пробует правую. Это даёт жёсткий приоритет и устраняет амбигвальность - но требует от автора грамматики думать о порядке. Классическая ловушка: A <- 'if' Expr 'then' Stmt / 'if' Expr 'then' Stmt 'else' Stmt - парсер всегда выбирает короткое правило и не доходит до else. Правильно: длинное первым.

Negative lookahead (!e) - вторая ключевая фишка PEG, отсутствующая в CFG. Позволяет писать 'если дальше идёт X, не применять это правило' без подсчётов и анализа состояний. Пример: идентификатор - последовательность букв, не являющаяся ключевым словом: Ident <- !Keyword [a-zA-Z]+. Без negative lookahead такие проверки требуют отдельных пост-фильтров. С ним грамматика становится самодостаточной и читаемой.

Мемоизация: ключ к линейности

Naive PEG-парсер имеет экспоненциальную сложность в худшем случае. Причина - бэктрекинг: грамматика вида A <- a A / a при неудаче перебирает все способы разбора одной и той же позиции. Решение известно с 70-х: мемоизация. Если разбор правила P в позиции i уже посчитан с результатом (успех/неудача, новая позиция, AST), повторный вызов возвращает кэш. Уникальных пар (правило, позиция) при N символах и K правилах ровно N*K - значит, общий разбор делается за O(N*K). При фиксированной грамматике это O(N) - линейное время по входу.

Мемоизация платит памятью: таблица размера N*K. Для большинства языков это терпимо (тысячи правил * мегабайты текста = десятки мегабайт). В реальных Packrat-парсерах ленивая мемоизация: кэшируются только правила, для которых бэктрекинг возможен. ANTLR 4 и PEP 617 Python используют selective memoization - кэш заводят только под потенциально неоднозначные правила, что снижает overhead. Левая рекурсия не поддерживается классическим Packrat и требует специальной обработки (Warth et al., 2008).

Packrat-парсер: PEG + мемоизация на практике

Packrat-парсер - имя, придуманное Брайаном Фордом для PEG с полной мемоизацией. Дословно 'крыса-сборщик' - аналогия с тем, как зверёк складывает в норе все встреченные вещи. На практике packrat - это набор взаимно-рекурсивных функций (по одной на правило), каждая обёрнута в memo. Парсер строит AST за линейное время, гарантирует отсутствие амбигвальности и легко расширяется новыми правилами. Минусы: повышенный расход памяти и плохая обработка левой рекурсии (грамматика A <- A '+' B / B уходит в бесконечный цикл без специальной поддержки).

Современные packrat-реализации: PEG.js / Peggy для JS, lark для Python, parsimmon для функциональной композиции, ohm.js (Resilient Software) с интерактивным редактором грамматик. Питоновский PEP 617 - индустриальное доказательство масштабируемости PEG: ядро Python 3.9+ парсится новым PEG-парсером, заменившим pgen 1.0. Грамматика стала проще, диагностика ошибок - точнее, поддержка f-strings и pattern matching - без хаков, доступных только PEG.

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

• **PEG задаёт алгоритм разбора, а не множество строк** - амбигвальность невозможна по построению.
• **Упорядоченный выбор e1 / e2** заменяет коммутативное | в CFG: порядок альтернатив критичен, длиннее обычно первым.
• **Мемоизация делает PEG линейным:** пара (правило, позиция) обрабатывается ровно один раз - O(N*K) по входу.
• **Packrat-парсер - PEG + memoization** в реальном коде; индустриальный пример - PEP 617 ядра Python.
• **Левая рекурсия не поддерживается классическим packrat** - требует специальных расширений (Warth seed parsing).

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

PEG занимает место рядом с традиционными LL/LR подходами к синтаксическому анализу.

• LR-парсинг — LR работает на CFG и разрешает конфликты shift/reduce; PEG детерминирован по построению
• Формальные грамматики — Различие классов выразительности: CFG vs PEG - не подмножество и не надмножество

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

• Python поменял pgen на PEG в 2020 и получил pattern matching. Какие ещё языковые конструкции были недоступны при LL(1)-парсинге и теперь стали возможными с PEG?
• Левая рекурсия требует Warth-стиля seed parsing. Какие компромиссы это создаёт по сравнению с автоматической поддержкой LR-парсеров?
• В PEG порядок альтернатив определяет язык. Какие практики помогают команде ловить случаи, когда e1 'съедает' префикс, не доходя до правильной e2, на ранних этапах разработки грамматики?

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

• comp-12-lr-parsing — LR-парсинг - контекст для понимания мотивации PEG
• comp-11-recursive-descent — PEG - это recursive descent с мемоизацией
• comp-14-parser-generators — Packrat лежит в основе генераторов на базе PEG (pest, PEG.js)
• alg-21-dp — Мемоизация в packrat - это табличная DP на строке
• fl-03-grammars