parser comparison question

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

parser comparison question

Scott N. Walck
I've been comparing Graham Hutton's simple parser with Parsec.  Here is some example code.

-- Comparison of Hutton's simple parser with Parsec

-- Hutton's simple parser is available at
-- http://www.cs.nott.ac.uk/~gmh/Parsing.lhs

-- Hutton simple parser called H
-- Parsec called P

import qualified Parsing as H
import qualified Text.ParserCombinators.Parsec as P

exH = H.parse (H.string "hi") "hiho"
exP = P.parse (P.string "hi") "" "hiho"

charH = H.parse (H.char 'a' H.+++ H.char 'b') "bbb"
charP = P.parse (P.char 'a' P.<|> P.char 'b') "" "bbb"

choiceH = H.parse (H.string "hoo" H.+++ H.string "ho") "hono"
choiceP1 = P.parse (P.string "bb" P.<|> P.string "ba") "" "bbb"
choiceP2 = P.parse (P.string "ba" P.<|> P.string "bb") "" "bbb"

choiceP22 = P.parse (P.try (P.string "ba") P.<|> P.string "bb") "" "bbc"

I am interested if anyone could comment on the design of the Parsec 'try' function.
For example, choiceP2 fails and returns Left error, while choiceP22 succeeds.

Hutton's simple parser doesn't need try.  It seems so simple and elegant.
I'm wondering why Parsec requires me to use 'try' for a string parse that might fail.

Thanks,

Scott


Scott N. Walck
Associate Professor of Physics
Lebanon Valley College

Reply | Threaded
Open this post in threaded view
|

parser comparison question

Daniel Fischer-4
Am Samstag 25 April 2009 04:31:29 schrieb Walck, Scott:

> I've been comparing Graham Hutton's simple parser with Parsec.  Here is
> some example code.
>
> -- Comparison of Hutton's simple parser with Parsec
>
> -- Hutton's simple parser is available at
> -- http://www.cs.nott.ac.uk/~gmh/Parsing.lhs
>
> -- Hutton simple parser called H
> -- Parsec called P
>
> import qualified Parsing as H
> import qualified Text.ParserCombinators.Parsec as P
>
> exH = H.parse (H.string "hi") "hiho"
> exP = P.parse (P.string "hi") "" "hiho"
>
> charH = H.parse (H.char 'a' H.+++ H.char 'b') "bbb"
> charP = P.parse (P.char 'a' P.<|> P.char 'b') "" "bbb"
>
> choiceH = H.parse (H.string "hoo" H.+++ H.string "ho") "hono"
> choiceP1 = P.parse (P.string "bb" P.<|> P.string "ba") "" "bbb"
> choiceP2 = P.parse (P.string "ba" P.<|> P.string "bb") "" "bbb"
>
> choiceP22 = P.parse (P.try (P.string "ba") P.<|> P.string "bb") "" "bbc"
>
> I am interested if anyone could comment on the design of the Parsec 'try'
> function. For example, choiceP2 fails and returns Left error, while
> choiceP22 succeeds.
>
> Hutton's simple parser doesn't need try.  It seems so simple and elegant.
> I'm wondering why Parsec requires me to use 'try' for a string parse that
> might fail.

In short: efficiency

The simple parser is a fully backtracking parser, therefore it has to keep the whole input
available in case a parse fails and an alternative has to be tried.
Parsec's alternative (<|>) tries the second parser only if the first parser failed
*without consuming any input*, so the input consumed so far can be immediately discarded,
which is more efficient. To get backtracking behaviour you must wrap the first parser in a
'try', which makes it either succeed or fail without consuming any input.
Using try means keeping more of the input available, which has a performance cost, so use
try sparingly, try to write your parsers so that they either succeed or fail (almost)
immediately (P.try (P.string "ba") requires only a short part of the input kept available,
so it doesn't hurt performance measurably, but imagine you have a parser that can fail
after having consumed 500MB of input. Keeping that around to try the second alternative on
as the simple parser must do will hurt.)

>
> Thanks,
>
> Scott
>
>
> Scott N. Walck
> Associate Professor of Physics
> Lebanon Valley College
>