Ван Россум думает над возможностью использования PEG (РВГ)

Пару дней назад ван Россум в статье «PEG Parsers» рассказал о том, что он заинтересовался идеей заменить парсер, используемый в Питоне на более совершенный, основанный на PEG.


Использование LL(1), с его просмотром только одного последующего токена:
1. Усложняет написание правил грамматики;
2. Не даёт возможности заранее определить, имеем ли мы дело с выражением или присваиванием;
3. Провоцирует написание дополнительных проверок (нивелирующих недостаток, упомянутый в предыдущем пункте), необходимых для разбора сложных выражений.

PEG — это грамматика, разбирающая выражение (РВГ). Использование такого подхода позволяет заглядывать на многие токены вперёд, ценой потребления дополнительной памяти. Кеширование (мемоизация промежуточных результатов разбора), используемое при «разборе про запас» (packrat parsing) позволяет добиться линейного времени разбора.

PEG решает не только упомянутые выше проблемы, но может позволить дальнейшие оптимизации. Например, можно будет строить абстрактное синтаксическое дерево AST прямо по ходу разбора. В текущей реализации перед созданием AST должно быть создано дерево разбора. На этой операции можно попробовать сэкономить и, возможно, экономия будет больше затрат на PEG.

Сейчас у ван Россума уже есть прототип, собирающий AST, правда пока только для ограниченного подмножества Питона. И пока Гвидо не собирается останавливаться на достигнутом.

А мы будем наблюдать.