What lexer to build a lexer/parser in Scala

Question

Hi there, I'm currently looking for a lexer/parser that generate Scala code from a BNF grammar (a ocamlyacc file with precedence and associativity) and I'm quite confused to find.. almost nothing:

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

For lexing, I found nothing.

In fact, for both I also found the famous Parser Combinators of Scala, but (correct me if I'm wrong), even if they are quite sexy, they are great time and memory consumers, mainly due to backtracking.

So I have two main questions:

• Why do people only seems to concentrate on Parser Combinators ?
• What is your best lexer/parser generator suggestion to use with Scala ?

Answer 1

Scala 2.8 has a packrat parser. I quote from the API docs here:

Packrat Parsing is a technique for implementing backtracking, recursive-descent parsers, with the advantage that it guarantees unlimited lookahead and a linear parse time. Using this technique, left recursive grammars can also be accepted.

Answer 2

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).