24 Feb
2013
24 Feb
'13
6:31 a.m.
On Wednesday, 20. February 2013 09:59:47 Tillmann Rendel wrote:
So the grammar is:
Exp ::= Int
| Exp "+" Exp
My naive parser enters an infinite recursion, when I try to parse "1+2". I do understand why:
"hmm, this expression could be a plus, but then it must start with an expression, lets check".
and it tries to parse expression again and again considers Plus.
Indeed.
Twan van Laarhoven told me that:
Left-recursion is always a problem for recursive-descend parsers.
Note that the left recursion is already visible in the grammar above, no need to convert to parser combinators. The problem is that the nonterminal Exp occurs at the left of a rule for itself.
Just a silly quick question: why isn't right-recursion a similar problem? -- Martin