|Removal of left recursion email@example.com (2004-03-11)|
|Re: Removal of left recursion firstname.lastname@example.org (2004-03-26)|
|From:||email@example.com (Colin Manning)|
|Date:||11 Mar 2004 12:54:17 -0500|
|Posted-Date:||11 Mar 2004 12:54:17 EST|
This is an example taken from Parsons (9780716782612) textbook. [By
the way, I can't recommend that book highly enough]
Remove all the left recursions from this grammar:
S -> aA | b | cS
A -> Sd | e
Now this grammar has no immediate left recursion. So it's only the
non-immediate we have to worry about.
My question is this. Why bother? It seems to me that this particuar
grammar isn't in need of any help since at each stage of the parse
some input is consumed.
Now, if it was
A -> Sx
S -> Ay | z
I could see why it would need some work. But I don't understand why
the grammar above would cause trouble for a top down parser.
Any thoughts? Am I missing something?
Return to the
Search the comp.compilers archives again.