Как реализовать левый элиминатор рекурсии?

Question

Как я могу реализовать элиминатор для этого?

 A := AB |
      AC |
      D  |
      E  ;

Answer 1

Это пример так называемой немедленной левой рекурсии, который удаляется так:

A := DA' |
     EA' ;

A' := ε   |
      BA' |
      CA' ;

Основная идея заключается в том, чтобы сначала отметить, что при разборе A вы обязательно начнете с D или E, После D или E вы либо закончите (tail is ε), либо продолжите (если мы в AB или же AC строительство).

Фактический алгоритм работает так:

Для любого леворекурсивного производства, подобного этому: A -> A a1 | ... | A ak | b1 | b2 | ... | bm заменить производство на A -> b1 A' | b2 A' | ... | bm A' и добавить производство A' -> ε | a1 A' | ... | ak A',

См. http://en.wikipedia.org/wiki/Left_recursion для получения дополнительной информации об алгоритме исключения (включая устранение косвенной левой рекурсии).

Answer 2

Другая доступная форма:

A := (D | E) (B | C)*

Механика выполнения этого примерно одинакова, но некоторые парсеры могут справиться с этой формой лучше. Также подумайте, что нужно сделать, чтобы изменить правила действия вместе с самой грамматикой; другая форма требует инструмента факторинга для создания нового типа для A' Правило возвращать туда, где нет этой формы.