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

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 | До н.э. D D, НО я должен использовать A_j -> BC | DD Если так, то я бы получил:

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' | ε