Цель этой темы посоветоваться с народом по поводу мыслей которые пришли в мою голову в процессе анализа PEG/Packrat.

Для начала небольшой анализ.

Плюсы PEG/Packrat:
1. Покрывает почти все нужды парсинга языков программирования.
2. Линейная скорость.
3. Простая реализация.
4. Гибкость. Грамматики можно менять хоть в рантайме. Возможна модульная организация грамматик.
5. Неограниченное заглядывание вперед позволяет упростить многие грамматики.
6. Возможность совместить лексер и парсер в одной грамматике (фактически отдельный лексер не требуется). Именно этим вызвана дружественность к модульности и гибкость.

Минусы:
1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.
2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла.
3. Большое потребление памяти. Собственно проблема та же что и в п. 2.
4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.

Теперь собственно мысли...

В презентации автора алгоритма Packrat (Форда) говорится, о том, что фактически PEG выражает грамматики разбираемые методом рекурсивного спуска с откатами. При этом он указывает, что реальные парсеры в реальных компиляторах и интерпретаторах в большинстве случае именно так и делаются и что мол Packrat предоставляет все преимущества этого метода.
Но на самом деле он лукавит. Реальные парсеры создаваемые методом рекурсивного спуска работают несколько иначе. Откаты в них встречаются крайне редко. Именно этим, а не мемоизацией (которой в них попросту нет) объясняется их реальная скорость.

Я проанализировал то как пишутся парсеры и понял в чем отличие создания парсеров "по науке" и "вручную". Дело в том, что парсер создаваемый вручную пользуется знанием грамматики. Скажем если парсер C# распарсил "class X {", то ему нет никакого смысла думать об откатах. Ведь цель достигнута — парсер распознал корректную конструкцию языка. Далее он может встретить правильную или не правильную конструкцию. Таким образом у рукопашных парсеров есть нечто от парсеров создаваемых на основе конечных автоматов. Я назову этот феномен "контрольной точкой".
Можно сказать, что рукопашные парсеры неявно вводят контрольные точки после которых начинается распознавание некоторой вложенной грамматики. У языка вроде C# такими точками являются: пространства имен, типы, члены типов. Фактически тело метода — это совсем другой язык. Этот язык может использовать общие элементы с другими частями общей (большой) грамматики (например, ссылка на тип может встречаться в описании параметров, в списке базовых типов класса, и внутри кода).

Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.

Грамматика при этом будет выглядеть как-то так:

Class = CastomAttributs? Modifiers? "partial"? "class" # Identifier # TypeParams? Constrains? '{' # ClassMembers* '}'

Это позволит с одной стороны делать серьезные оптимизации, а с другой улучшить выявление ошибок в разбираемом коде.

Главной оптимизацией при этом станет возможность использования отдельных хэш-таблиц для всех вложенных частей правил в которых встречается контрольная точка. Это позволит сохранить хэш-таблицу маленькой и уменьшит промахи мимо кэша процессора.

Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.