Scala parser combinators vs ANTLR/Java generated parser?

Question

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.

Wormseed

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? ... – Teat

Why do you consider being an internal DSL a con? – Excruciate

@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. – Wormseed

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 */ – Excruciate

Answer 1

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.

Maller

I've tried this and it works very well. It plays nicely with Scalas case-classes too (and so does JFlex/JavaCup too btw :-) – Wingspan

My problem is that my AST objects are in Scala exclusively...is there a way to call those objects in an ANTLR parser? – Wormseed

If you want to call Scala from Java and have it look nice your Scala can't rely on Scala-specific language features such as implicit conversions, implicit arguments, default arguments, symbolic method names, by-name parameters, etc. Generics should be kept relatively simple as well. If you're Scala objects are relatively simple then there shouldn't be any problem using them from Java. – Maller

Answer 2

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.

Moniquemonism

The additional build step shouldn't be a problem for me, I'm using Maven. – Wormseed

Answer 3

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.

Devalue

Answer 4

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.

Suburbicarian

By "Internal DSL" I meant that the grammar definition is an internal DSL. – Wormseed

Answer 5

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.

Acidity

Answer 6

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

Showalter