Scala parser combinators vs ANTLR/Java generated parser?

27
votes

I am writing an expression parser for an app written mostly in Scala. I have built AST objects in Scala, and now need to write the parser. I have heard of Scala's built-in parser combinators, and also of ANTLR3, and am wondering: which would provide better performance and ease of writing code? So far:

ANTLR pros

  1. Well-known
  2. Fast
  3. External DSL
  4. ANTLRWorks (great IDE for parser grammer debugging/testing)

ANTLR cons

  1. Java-based (Scala interop may be challenging, any experience?)
  2. Requires a large dependency at runtime

Parser combinator pros

  1. Part of Scala
  2. One less build step
  3. No need for a runtime dependency; e.g. already included in Scala's runtime library

Parser combinator cons

  1. Internal DSL (may mean slower execution?)
  2. No ANTLRWorks (provides nice parser testing and visualization features)

Any thoughts?

EDIT: This expression parser parses algebraic/calculus expressions. It will be used in the app Magnificalc for Android when it is finalized.

6
javaparsingscalaantlr3parser-combinators
I have no experience with Scala (and therefor it's parser combinators), so I can't make a recommendation. But, for the people who have experience in both, you may want to explain what your expression parser is (going to be) capable of: does it support variable scopes, or classes/structs of some sort? Function declarations? ... – Bart Kiers
Why do you consider being an internal DSL a con? – Jens Schauder
@Jens because it may result in slower execution. Do you know anything about the performance precompiled vs internal DSL? I'd be glad to hear it. – Nathan Moos
Don't have performance information. Are you referring to the performance of the resulting parser? Or the performance of the parser generation step? For the first internal vs external shouldn't matter. For the second I'd expect an internal DSL to be faster since it doesn't need to get parsed, before it gets interpreted. /* getting a little meta here */ – Jens Schauder

6 Answers

18
votes

Scala's parser combinators aren't very efficient. They weren't designed to be. They're good for doing small tasks with relatively small inputs.

So it really depends on your requirements. There shouldn't be any interop problems with ANTLR. Calling Scala from Java can get hairy, but calling Java from Scala almost always just works.

6
votes

I wouldn't worry about the performance limitations of parser combinators unless you were planning on parsing algebraic expressions that are a few pages long. The Programming Scala book does mention that a more efficient implementation of parser combinators is feasible. Maybe somebody will find the time and energy to write one.

I think with ANTLR you are talking about two extra build steps: ANTLR compiles to Java, and you need to compile both Scala and Java to bytecode, instead of just Scala.

2
votes

I have created external DSLs both with ANTLRv4 and Scalas parser combinators and I clearly prefer the parser combinators, because you get excellent editor support when designing the language and it's very easy to transform your parsing results to any AST case class data structure. Developing ANTLR grammars takes much more time, because, even with the ANTLRWorks editor support, developing grammars is very error-prone. The whole ANTLR workflow feels quite bloated to me compared to the parser combinators' one.

0
votes

I would be inclined to try to produce an external DSL using parser combinators. It shouldn't need to be an internal DSL. But I don't know that it would be better.

The best approach to figuring this out would be to take a simplified version of the grammar, try it both ways and evaluate the differences.

0
votes

Just been writing a parser for a home brew 8 bit CPU assembler.

I got so far with Antlr4 before feeling that there had to be a better way. I decided to have a go at Scala parser combinators and have to say that it is way more productive IMHO. However, I do know scala.

0
votes

If you still interested about an integer expression parser please take a look at my example interpreter here: https://github.com/scala-szeged/hrank-while-language . It is 200 hundred lines Scala code using the officail parser combinators. It has expression parsing. It also handle nested if, nested while, variables, and boolean expressions. I also implemented array handling in this github repository. If you need String handling I can help you, too.

An other, somewhat more simple expression parser is also present here in my other public repository https://github.com/scala-szeged/top-calc-dsl