Ван Россум думает над возможностью использования PEG (РВГ)
Есть шансы, что на смену простому pgen придёт нечто более хитрое
Пару дней назад ван Россум в статье «PEG Parsers» рассказал о том, что он заинтересовался идеей заменить парсер, используемый в Питоне на более совершенный, основанный на
Использование
1. Усложняет написание правил грамматики;
2. Не даёт возможности заранее определить, имеем ли мы дело с выражением или присваиванием;
3. Провоцирует написание дополнительных проверок (нивелирующих недостаток, упомянутый в предыдущем пункте), необходимых для разбора сложных выражений.
Сейчас у ван Россума уже есть прототип, собирающий
А мы будем наблюдать.
PEG
. На заметку
Парсер, используемый в Python сейчас, называемый
pgen
, был написан лет 30 назад. Для простоты в нём умышленно используется модель разбора LL(1) — слева-направо, деривация слева. Некоторое время назад обсуждалась идея сделать pgen
доступным непосредственно из Python — PEP 269, но не получила развития.Использование
LL(1)
, с его просмотром только одного последующего токена:1. Усложняет написание правил грамматики;
2. Не даёт возможности заранее определить, имеем ли мы дело с выражением или присваиванием;
3. Провоцирует написание дополнительных проверок (нивелирующих недостаток, упомянутый в предыдущем пункте), необходимых для разбора сложных выражений.
PEG
— это грамматика, разбирающая выражение (РВГ). Использование такого подхода позволяет заглядывать на многие токены вперёд, ценой потребления дополнительной памяти. Кеширование (мемоизация промежуточных результатов разбора), используемое при «разборе про запас» (packrat parsing) позволяет добиться линейного времени разбора.PEG
решает не только упомянутые выше проблемы, но может позволить дальнейшие оптимизации. Например, можно будет строить абстрактное синтаксическое дерево AST
прямо по ходу разбора. В текущей реализации перед созданием AST
должно быть создано дерево разбора. На этой операции можно попробовать сэкономить и, возможно, экономия будет больше затрат на PEG
.Сейчас у ван Россума уже есть прототип, собирающий
AST
, правда пока только для ограниченного подмножества Питона. И пока Гвидо не собирается останавливаться на достигнутом.А мы будем наблюдать.
Категории
Область
Интерпретатор
Уровень
Аспект языка
На заметку
Читайте нас в Twitter. Ссылка в самом низу страницы.