Removal of left recursion

manningcolin@hotmail.com (Colin Manning)
11 Mar 2004 12:54:17 -0500

          From comp.compilers
Related articles
Removal of left recursion manningcolin@hotmail.com (2004-03-11)
Re: Removal of left recursion whopkins@csd.uwm.edu (2004-03-26)
| List of all articles for this month |
From: manningcolin@hotmail.com (Colin Manning)
Newsgroups: comp.compilers
Date: 11 Mar 2004 12:54:17 -0500
Organization: http://groups.google.com
Keywords: parse
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?


Thanks


Colin

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.