Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Simple parser question (Martin Drautzburg)
2. Re: Simple parser question (Twan van Laarhoven)
----------------------------------------------------------------------
Message: 1
Date: Thu, 14 Feb 2013 13:59:58 +0100
From: Martin Drautzburg <[email protected]>
Subject: [Haskell-beginners] Simple parser question
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
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.
--
Martin
------------------------------
Message: 2
Date: Thu, 14 Feb 2013 15:23:03 +0100
From: Twan van Laarhoven <[email protected]>
Subject: Re: [Haskell-beginners] Simple parser question
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
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.
Twan
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
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 56, Issue 27
*****************************************
