Вопрос необычный.

Для динамически расширяемых правил будет использоваться алгоритм TDOP (он же Pratt-парсер, к сожалению, однозначно хорошей ссылки на описание алгоритма нет (не смотря на его простоту)).

К сожалению этот алгоритм был рассчитан на работу с выделенным лексером. Однако WolfHound предложил алгоритм объединяющей TDOP и PEG

Автор: WolfHound
Дата: 12.02.11

.

Чтобы все понимали о чем идет речь, для начала приведу поверхностное описание алгоритма.

Описание алгоритма

В двух, словах суть алгоритма состоит в следующем:
Мы делим все правила на префиксные и постфиксные.
Префиксные это:

Neg is Expr = '-'s Expr : 100;
Num is Expr = ['0' .. '9']s;

А постфиксные это:

Add  is Expr = Expr : 50 '+'s Expr : 50;
Mul  is Expr = Expr : 70 '*'s Expr : 70;
Cons is Expr = Expr : 21 "::"s Expr : 20; // право-ассоциативный

Постфиксные отличаются тем, что у них вначале идет рекурсивное (леворекурсивное) обращение к расширяемому правилу.

Алгоритм (при разборе расширяемых правил) вначале пытается разобрать префиксные правила. Если одно из правил разбирается, то попытка разобрать другие не производится и алгоритм переходит к разбору постфиксных правил. Тем самым алгоритм разбирает префикс для (возможно) идущего следом постфиксного правила.

Далее алгоритм пытается разобрать оставшуюся часть постфиксного правила (т.е. постфиксное правило без его первого, рекурсивного, обращения). Если хотя бы одно постфиксное правило разобралось, то алгоритм прерывает перебор постфиксных правил и начинает их перебор по новой. (здесь описывается алгоритм без оптимизаций).

Теперь, собственно, вопрос...

Данный алгоритм можно существенно оптимизировать, если при переборе постфиксных правил (коих, например, в грамматике Nemerle 1 более 40 штук) не вызывать функцию разбора постфиксного правила, в случае если оно заведомо не может разобраться.

Примечание: Для расширяемости постфиксные правила будут оформляться в виде переопределения виртуальных методов некоторого базового класса. Так как виртуальный вызов довольно дорог, лучше избегать бессмысленных вызовов.

Так вот, из приведенных выше примеров видно, что для постфиксных правил характерно наличие "литерала" после первого рекурсивного обращения.

Примечание: Литералом я называю '+' или "::".

Для таких подправил можно вычислить первый символ. Такой символ можно запомнить в метаданных расширяющего (не путать с расширяемым!) правилом и проверять его перед входом в постфиксное правило.

Внимание вопрос — можно ли придумать осмысленные примеры постфиксных правил в которых после первого рекурсивного обращения шел бы не "литерал", а более сложное правило? Это не обязательно должно быть примером выражений! Случай когда идет обращение к другому правилу, которое в итоге, все равно приводит "к обращению" к "литералу" опустим, как он сводится к исходному случаю.

Другими словами, может быть осмысленное правило вроде:

X is Y = Y ['a' .. 'z']+ Y;

или

X is Y = Y Z? '*' Y;

Примеры абстрактные, так что вместо конкретных литералов можно подставить что угодно.
Главное, что для подправила идущего за первым рекурсивным обращением, нельзя было "вычислить" первый символ.

Если кто-то сможет придумать, подобный осмысленный пример, то просьба так же оценить насколько он может часто встречаться в реальной грамматике и какое количество постфиксных правил может появляться в таких правилах.