Menu
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?
816
In Scala, a combinator is a Higher-Order Function and also a pure function. As they are pure functions, we can easily compose them together very well as flexible, fine-grained building blocks for constructing larger, more complex programs. Some of the frequently used Scala combinators are as follows: map. flatMap.
Parser combinators are generally slower than a hand-written or code-generated parser. That's somewhat innate due to the overhead of “threading” (for lack of a better word) your control flow through many function calls.
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:
Note that Haskell has many other parser combinator libraries, if you're interested in this approach, e.g.
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.
179
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)
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
