Could someone please explain to me why recursive-descent parsers can't work with a grammar containing left recursion?
+12
A:
consider:
A ::= A B
the equivalent code is
boolean A() {
if (A()) {
return B();
}
return false;
}
see the infinite recursion?
cadrian
2009-05-11 10:01:46
+6
A:
For whoever is interested
A ::= A B | A C | D | E
can be rewritten as:
A ::= (D | E) (B | C)*
The general form of the transformation is: any one of the non left recursive disjuncts followed by any number of the left recursive disjuncts without the first element.
Reforming the action code is a bit trickery but I thing that can be plug-n-chug as well.
BCS
2009-05-11 19:32:15
First time I've seen that, I always saw advice to use a new non-terminal, usually called A'
Benjamin Confino
2009-05-11 20:14:50
Well some BNF based tools won't allow () groups so you end up stuck with the new rule solution. I'm kinda partial to the form I proposed because my parser generator needs to do the action transformation as well so it's a lot easier to make it work without a new rule.
BCS
2009-05-11 20:20:20