Did you see <a href="http://hackage.haskell.org/packages/archive/parsec/3.1.3/doc/html/Text-Parsec-Expr.html">expression parser in parsec package</a>? Is it not enough?<div><br></div><div><br><div class="gmail_quote">2013/2/20 Martin Drautzburg <span dir="ltr"><<a href="mailto:Martin.Drautzburg@web.de" target="_blank">Martin.Drautzburg@web.de</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello all,<br>
<br>
this was previously asked on haskell-beginners, but only partially answered.<br>
<br>
As an exercise I am writing a parser roughly following the expamples in Graham<br>
Hutton's book. The language contains things like:<br>
<br>
data Exp = Lit Int -- literal integer<br>
| Plus Exp Exp<br>
<br>
My naive parser enters an infinite recursion, when I try to parse "1+2". I do<br>
understand why:<br>
<br>
"hmm, this expression could be a plus, but then it must start with an<br>
expression, lets check".<br>
<br>
and it tries to parse expression again and again considers Plus.<br>
<br>
Twan van Laarhoven told me that:<br>
<br>
> Left-recursion is always a problem for recursive-descend parsers.<br>
<br>
and suggested to do something like:<br>
<br>
> parseExp = do<br>
> lit <- parseLit<br>
> pluses <- many (parsePlusToken *> parseLit)<br>
> return (combinePlusesWithLit lit pluses)<br>
><br>
> combinePlusesWithLit = foldr Plus -- or foldl<br>
<br>
This indeed does the trick, but only when the first token is a Lit (literal<br>
integer).<br>
<br>
I then added the possibility to optionally put things in parentheses. But then<br>
I cannot parse "(1+2)+3". The original code fails, because "(1+2)" is not a<br>
Lit and when I allow an expression as the first argument to "+" I get infinite<br>
recursion again.<br>
<br>
I am generally confused, that saying "a plus expression is an integer followed<br>
by many "plus somethings" is not what the language says. So this requires a<br>
lot of "paying attention" to get right. I'd much rather say "a plus expression<br>
is two expressions with a '+' in between".<br>
<br>
I do know for sure, that it is possible to parse "(1+2)+3" (ghci does it just<br>
fine). But I seem to be missing a trick.<br>
<br>
Can anyone shed some light on this?<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
Martin<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</font></span></blockquote></div><br></div>