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 -> δ1 γ | δ2 γ | .. | δ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, Aj -> A a | A B C | B C | D D, BUT should I be using Aj -> 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?
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:
- Replace the recursive productions with new productions in which recursion is on the right. Use a new non-terminal symbol for that.
- Add a production with an empty right side to the new non-terminal.
- 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' | ε
精彩评论