Removing Left Recursion

Question

I am trying to exclude left recursion from CFG by excluding indirect recursion and then direct recursion, as this algorithm shows.

I will use this grammar:

A = A a | ABC | BC | DD 

When i = 1 and j = 1, we look at the replacement of all productions of the form A → A r with:

A →> ₁ ? | <sub> 2? | .. | ? _k ?

So when I look at A → A a that matches, I have to replace it with

 A -> A aa | ABC aa | BC a | DD a 

which is wrong.

Can someone point me in the right direction how to replace production when you replace it with the product itself?

NOTE. Also, I was only stuck in the first rule, so I skipped the others for simplicity

Any help would be greatly appreciated.

[UPDATE] Found as close to the original Greek characters as possible. In addition, I may be approaching this in the wrong direction. When i = 1 and j = 1, A _j → A a | ABC | BC | DD, BUT I have to use A _j → BC | DD If so, I would get:

 A -> BCA | BCBC | DDA | DDBC | BC | DD 

Since this will eliminate recursion in this setting. Is this the best direction?

Answer 1

This is the recipe:

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

should be converted to:

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

I.e:

• Replace recursive productions with new pieces in which recursion is on the right. Use the new nonterminal symbol for this.
• Add the production with the empty right side to the new nonterminal.
• Add a new nonterminal character to the right of non-recursive productions.

For your grammar:

 A = A a | ABC | BC | DD 

would you get:

 A = BCA' | DDA' A' = a A' | BCA' | ε