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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
