[Haskell-beginners] Simple parser question
Martin.Drautzburg at web.de
Mon Feb 18 21:48:36 CET 2013
Thanks, that kind of worked. As long as I am only dealing with literal
integers at the beginning of pluses is works fine.
*Main> parse "(1+2+3)"
Plus (Lit 1) (Plus (Lit 2) (Lit 3))
But this fails already:
*Main> parse "(1+2)+3"
Error "parse error"
There is no problem with expressions in parenthes, but my "pluses" can only
start with an integer (even one in parentheses), but not with an expression,
since I had to get rid of the expression at the left side, to avoid left-
I am also 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".
Any other ideas?
On Thursday, 14. February 2013 15:23:03 Twan van Laarhoven wrote:
> Left-recursion is always a problem for recursive-descend parsers. The
> solution is to rewrite the parser as:
> * first always parse an expression without a Plus
> * followed by zero or more "+ exp" parts.
> How exactly you write this depends on the combinators that the book defines
> for writing parsers. In Parsec you would write something like:
> parseExp = do
> lit <- parseLit
> pluses <- many (parsePlusToken *> parseLit)
> return (combinePlusesWithLit lit pluses)
> combinePlusesWithLit = foldr Plus -- or foldl
> I hope you get the idea.
> Note that the parsec library has functions chainl and chainr that do
> something like this under the hood, so you would never actually write the
> above code.
> On 14/02/13 13:59, Martin Drautzburg wrote:
> > Hello all,
> > I just hit a sticking point when trying to parse something like
> > data Exp = Lit Int -- literal integer
> > | Plus Exp Exp
> > where something like "1+2" should be parsed to "Plus (Lit 1) (Lit 2)".
> > When I try to parse "1+2" my parser enters an infinite loop. I can
> > understand why: it thinks
> > "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.
> > When I change the rules, so it first checks for "Lit", it does parse the
> > "1" just fine, but then gives up, because the remainder is not an
> > expression anymore, but just a "+2".
> > My parser is written in the style shown in Graham Hutton's book:
> > Parser a :: String -> (a, String).
> > I believe I am missing something obvious, but I can't see it.
> Beginners mailing list
> Beginners at haskell.org
More information about the Beginners