How do Scala parser combinators compare to Haskell's Parsec?

Question

I have read that Haskell parser combinators (in Parsec) can parse context sensitive grammars. Is this also true for Scala parser combinators? If so, is this what the "into" (aka ">>") function is for?

What are some strengths/weaknesses of Scala's implementation of parser combinators, vs Haskell's? Do they accept the same class of grammars? Is it easier to generate error messages or do other miscellaneous useful things with one or the other?

How does packrat parsing (introduced in Scala 2.8) fit into this picture?

Is there a webpage or some other resource that shows how different operators/functions/DSL-sugar from one language's implementation maps onto the other's?

Answer 1

You have many questions!

Comparing parsec (which is only one of many Haskell parser combinator libraries) to the Scala implementation of parsec

No one has made comparisons here, as the Scala code is fairly new, but check the documentation:

• http://hackage.haskell.org/package/parsec
• http://www.scala-lang.org/docu/files/api/scala/util/parsing/combinator/Parsers.Parser.html

Note that Haskell has many other parser combinator libraries, if you're interested in this approach, e.g.

• attoparsec + attoparsec-iteratee
• polyparse

What are some strengths/weaknesses of Scala's implementation of parser combinators, vs Haskell's?

The Haskell code is more than a decade old, well understood, and there are many examples, lots of documentation and user cases. Scala's stuff is relatively new.

packrat parsing

packrat parsing is different entirely. The original packrat paper was developed in Haskell, but has since become more widespread.

Is there a webpage or some other resource that shows how different operators/functions/DSL-sugar from one language's implementation maps onto the other's?

No, but that would be cool. However, almost all(?) parser combinator libraries are based on the pioneering parsec implementation, so they share a lot with the original parsec.

Answer 2

There's also the following technical report:

Parser combinators in Scala

Parser combinators are well-known in functional programming languages such as Haskell. In this paper, we describe how they are implemented as a library in Scala, a functional object-oriented language. Thanks to Scala's flexible syntax, we are able to closely approximate the EBNF notation supported by dedicated parser generators. For the uninitiated, we first explain the concept of parser combinators by developing a minimal library from scratch. We then turn to a detailed description of the existing Scala library, including its support for denoting variable binding as part of the syntax. We provide several realistic examples to illustrate the utility of our library.

report.pdf (324K)