Parser Combinators library of choice (haskell)

Question

Are there any parser combinators library that gives performance comparable to Happy/Alex ?

I know about Attoparsec, but sometimes it operates not well, like in an example below:

isToken c = isLetter c || isDigit c

symbol :: Parser Expr
symbol = do 
    c    <- skipSpace >> satisfy isLetter 
    rest <- takeWhile isToken
    let token = C.cons c rest  -- oops... O(N)
    error $ show token

The workaround is quite ugly:

do { skipSpace; bs <- scan go True; when (null bs) (fail "Not a symbol"); return bs}
    where go True  c = if isLetter c then Just  False else Nothing
          go False c = if isToken c then Just Fasle else Nothing

Also, Attoparsec lacks of error handling.

Happy/Alex are quite unfriendly (for me) comparing to ocamlyacc/ocamllex, BNFC is inflexible and in my case requires an additional AST traversing after parsing. Also, error handling is not very good.

There are three of rest options: Parsec2, Parsec3 and uu-parselib. I've found a number of controversial benchmarks assuming that Parsec2 is faster than Parsec3, or UU is faster, or it's slower.

But what to choose? Does anyone have an experience using uu-parselib? I need the parser for some kind of DSL, need the parses fast enough to not to change it in future.

If you are parsing "human-sized" data (i.e. files written by people), any of the mainstream parser combinator libraries should be fine speed-wise, though for you might have to to pay some attention to control backtracking in a parser you write. If you are parsing huge data files then the equation changes somewhat, I'd look for benchmarks at this point and consider what features you can to trade for speed (e.g. source position tracking can be a significant slow down). — stephen tetley
– stephen tetley, Commented Jul 19, 2011 at 7:25
Not an answer, but I've used uu-parselib a lot. It's very powerful and has some nice features, like automatic stream correction. My only complaint is that not all of the features are immediately obvious; especially if you're not already familiar with parsers. I've never had a problem with speed, but my input data has mostly been in the kbyte size. — John L
– John L, Commented Jul 19, 2011 at 8:49

fuz · Accepted Answer · 2011-07-19 15:11:21Z

7

There is another alternative: polyparse.
After last year's GSoC, parsec3 was optimized and no longer noticeably slower than parsec2
Couple of years ago I've done tests on several grammars (mid-size) and found that performance of happy/alex, parsec2/alex, parsec2 and polyparse is very close. Attoparsec was faster on byte streams, but I needed multi-byte.

My advise: take a look at the way alternatives handle internal and user-defined state and report errors and choose by these criteria.

edited Jul 19, 2011 at 15:11

fuz

94.7k27 gold badges216 silver badges391 bronze badges

answered Jul 19, 2011 at 5:48

ADEpt

5,5521 gold badge28 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

voidlizard Over a year ago

Are you sure that Parsec is close to Happy/Alex ? In that case there is no sense to use Happy or BNFC at all. May be there are any benchmarks I may to run by myself?

augustss Over a year ago

Regardless of efficiency, using a parser generator like Happy has the advantage that you get errors and warnings about your grammar (like ambiguities).

ADEpt Over a year ago

attoparces-text didn't exist back then, so I didnt test it.

Collectives™ on Stack Overflow

Parser Combinators library of choice (haskell)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related