[Haskell-cafe] Parser left recursion

[Roman Cheplyaka]

* Martin Drautzburg <Martin.Drautzburg at web.de> [2013-02-24 12:31:37+0100]
> > > 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?

Right recursion is recursion of the form

  A ::= B A

There are two cases to consider here.

The language defined by B may or may not contain the empty string.

If it contains the empty string, then we have an indirect left
recursion, since the rule

  A ::= A

is an instance of the original rule.

If it doesn't contain the empty string, then, by the time you get to A,
you necessarily have to consume some part of the input. Thus, your
recursion is well-founded — you enter the recursion with the input
strictly smaller than you had in the beginning.

Roman