[Haskell-cafe] Parser left recursion

[Martin Drautzburg]

Hello all,

this was previously asked on haskell-beginners, but only partially answered.

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

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.
  
Twan van Laarhoven told me that:

> Left-recursion is always a problem for recursive-descend parsers.

and suggested to do something like:

>     parseExp = do
>       lit <- parseLit
>       pluses <- many (parsePlusToken *> parseLit)
>       return (combinePlusesWithLit lit pluses)
>
>     combinePlusesWithLit = foldr Plus -- or foldl

This indeed does the trick, but only when the first token is a Lit (literal 
integer). 

I then added the possibility to optionally put things in parentheses. But then  
I cannot parse "(1+2)+3". The original code fails, because "(1+2)" is not a 
Lit and when I allow an expression as the first argument to "+" I get infinite 
recursion again.

I am generally confused, that saying "a plus expression is an integer followed 
by many "plus somethings" is not what the language says. So this requires a 
lot of "paying attention" to get right. I'd much rather say "a plus expression 
is two expressions with a '+' in between".

I do know for sure, that it is possible to parse "(1+2)+3" (ghci does it just 
fine). But I seem to be missing a trick.

Can anyone shed some light on this?

-- 
Martin