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

Question

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

 A := AB |
      AC |
      D  |
      E  ;

Answer 1

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

A := DA' |
     EA' ;

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

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

Фактический алгоритм работает следующим образом:

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

См. Википедия: Левая рекурсия для получения дополнительной информации об алгоритме исключения (включая устранение косвенной левой рекурсии).

Answer 2

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

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

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