Left recursion elimination

问题:

I'm attempting to eliminate left recursion from a CFG by eliminating indirect recursion then direct recursion as this algorithm shows.

I'll be using this grammar:

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

When i = 1, and j = 1 we are looking at replacing all productions of the form A -> A r with:

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

So when I look at A -> A a which matches, i should replace it with

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

which im sure is wrong

Can anyone point me in the right direction for how to replace productions when your replacing it with the production itself?

NOTE : Also, I'm only stuck on the first rule so have omitted the others for simplicity

Any help would be greatly appreciated

[UPDATE]Found as close to the original greek symbols as I could. Also, am I perhaps approaching this in the wrong direction. When i=1 and j=1, A_j -> A a | A B C | B C | D D, BUT should I be using A_j -> B C | D D If so then I would get:

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

As that would then eliminate the recursion in that production. This a better direction?

回答1:

This is the recipe:

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

should be transformed to:

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

That is:

1. Replace the recursive productions with new productions in which recursion is on the right. Use a new non-terminal symbol for that.
2. Add a production with an empty right side to the new non-terminal.
3. Append the new non-terminal symbol to the right of the non-recursive productions.

For your grammar:

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

you would obtain:

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