[Haskell-cafe] Parser left recursion

[Martin Drautzburg]

Thank you very much. 

To clarify: I am not in need of a parser, I just wanted to understand why left 
recursion is an issue (that was easy) and what techniques help to circumvent 
the problem. So your answer was spot-on (though I haven't implemented it yet)

On Wednesday, 20. February 2013 09:59:47 Tillmann Rendel wrote:
> Hi,
> 
> Martin Drautzburg wrote:
> > As an exercise I am writing a parser roughly following the expamples in
> > Graham Hutton's book. The language contains things like:
> > 
> > data Exp = Lit Int -- literal integer
> > 
> >           | Plus Exp Exp
> 
> 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.
> 
> One way to fix this problem is to refactor the grammar in order to avoid
> left recursion. So let's distinguish "expressions that can start with
> expressions" and "expressions that cannot start with expressions":
> 
>    Exp-norec ::= Int
>    Exp-rec   ::= Exp-norec
> 
>               |  Exp-norec "+" Exp-rec
> 
> Note that Exp-rec describes a list of Exp-norec with "+" in-between, so
> you can implement it with the combinator many.
> 
> Now if you want to add a rule like
> 
>    Exp ::= "(" Exp ")"
> 
> you need to figure out whether to add it to Exp-norec or Exp-rec. Since
> the new rule is not left recursive, you can add it to Exp-norec:
> 
>    Exp-norec ::= Int
> 
>               |  "(" Exp-rec ")"
> 
>    Exp-rec   ::= Exp-norec
> 
>               |  Exp-norec "+" Exp-rec
> 
> If you implement this grammar with parser combinators, you should be
> able to parse "(1+2)+3" just fine.
> 
>    Tillmann
> 
> PS. Try adding multiplication to your grammar. You will need a similar
> trick to get the priorities right.

-- 
Martin