Здравствуйте, VladD2, Вы писали:

VD>Теперь о проблемах...
Вот тут изложены идеи полутора десятков оптимизаций для packrat:
Better Extensibility through Modular Syntax
реализация (на Java): http://www.cs.nyu.edu/~rgrimm/xtc/xtc-core.zip
Полученные парсеры работают примерно со скоростью ANTLR 2.7 потребляя в 2 раза больше памяти.

VD>Мемоизировать все — это тупиковый вариант. Он конечно O(n), но n там заоблачное. Расход памяти O(p*n) где "p" — количество правил в грамматике, а "n" — количество символов во входном потоке (файле). А это полные вилы. Скорость ниже плинтуса.

VD>Проанализировав все это я пришел к выводу, что PEG можно применять только если добиться того, что мемоизация будет происходить только в там где она действительно необходима. Например если у нас есть взять приведенную выше грамматику, то мемоизировать в ней нужно только правило CustomAttrs и Modifier.

Rats! по умолчанию он мемоизирует все(при этом расход памяти оптимизациями сокращен в 5-10 раз). Результатом вполне можно пользоватся: на мегабайт исходника нужно примерно 300 мег памяти. Потом (при необходимости) можно провести ручную дооптимизацию: пометить правила, которые не нужно мемоизировать. Это, в общем, работает.