Lexer/parser to generate Scala code from BNF grammar

Question

I'm currently looking for a lexer/parser that generates Scala code from a BNF grammar (an ocamlyacc file with precedence and associativity). I'm quite confused since I found almost nothing on how to do it.

For parsing, I found scala-bison (that I have a lot of trouble to work with). All the other tools are just Java parsers imported into Scala (like ANTLR).

For lexing, I found nothing.

I also found the famous parser combinators of Scala, but (correct me if I'm wrong), even if they are quite appealing, they consume a lot of time and memory, mainly due to backtracking.

So I have two main questions:

• Why do people only seem to concentrate on _parser combinators?
• What is your best lexer/parser generator suggestion to use with Scala?

Answer 1

As one of the authors of the ScalaBison paper, I have run into this issue a few times. :-) What I would usually do for scanning in Scala is use JFlex. It works surprisingly well with ScalaBison, and all of our benchmarking was done using that combination. The unfortunate downside is that it does generate Java sources, and so compilation takes a bit of gymnastics. I believe that John Boyland (the main author of the paper) has developed a Scala output mode for JFlex, but I don't think it has been publicly released.

For my own development, I've been working a lot with scannerless parsing techniques. Scala 2.8's packrat parser combinators are quite good, though still not generalized. I've built an experimental library which implements generalized parsing within the parser combinator framework. Its asymptotic bounds are much better than traditional parser combinators, but in practice the constant time overhead is higher (I'm still working on it).