[Haskell-beginners] parser comparison question

[Daniel Fischer]

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
>