Устранение левой рекурсии

Question

Я пытаюсь устранить левую рекурсию из CFG, устраняя косвенную рекурсию, а затем прямую рекурсию, как показывает этот алгоритм .

Я буду использовать эту грамматику:

A = A a | A B C | B C | D D

Когда i = 1 и j = 1 , мы планируем заменить все произведения вида A -> A r на:

A -> δ ₁ γ |δ ₂ γ |.. |δ _k γ

Поэтому, когда я смотрю на A -> A a , что соответствует, я должен заменить его на

A -> A a a | A B C a a | B C a | D D a  

, чтоконечно, это неправильно

Может кто-нибудь указать мне правильное направление для замены производств, когда вы заменяете их производством?

ПРИМЕЧАНИЕ. Кроме того, я застрял только в первом правилепоэтому опускаем другие для простоты

Любая помощь будет принята с благодарностью

[ОБНОВЛЕНИЕ] Найден как можно ближе к оригинальным греческим символам.Кроме того, я, возможно, подхожу к этому в неправильном направлении.Когда i = 1 и j = 1 , A _j -> A a |ABC |До н.э.ДД, НО мне следует использовать A _j -> BC |ДД Если так, то я бы получил:

A -> B C A | B C B C | D D A | D D B C | B C | D D

Так как это исключило бы рекурсию в этом производстве.Это лучшее направление?

Answer 1

Это рецепт:

A → Aα1 | ... | Aαm | β1 | ... | βn

следует преобразовать в:

A → β1 A' | ... | βn A'
A' → α1 A' | ... | αm A' | ε

То есть:

1. Заменить рекурсивные производства на новые производствав котором рекурсия справа.Для этого используйте новый нетерминальный символ.
2. Добавьте производство с пустой правой стороной к новому нетерминальному символу.
3. Добавьте новый нетерминальный символ справа от-рекурсивные произведения.

Для вашей грамматики:

A = A a | A B C | B C | D D

вы получите:

A  = B C A' | D D A'
A' = a A' | B C A' | ε