[Haskell-cafe] Parser left recursion

[Martin Drautzburg]

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