Lexing and parsing in Scala using combinators: M-Expression syntax

For the static analysis course I’m teaching next spring, I’ll be releasing parsers for several languages to be used in assignments.

I’ve decided to support Java and Scala explicitly (although students are free to use whatever language they prefer), so this seemed like a good excuse to finally learn Scala’s parser combinators.

I noticed, however, that nearly all of the examples for parser combinators used StandardTokenParsers, and I couldn’t find anything on creating your own lexer.

Related blog articles:

I dug through the library code and figured out how to roll a token-based lexer/parser system from scratch.

Because I usually write S-Expression parsers, I decided to do an M-Expression parser this time.

I learned during this exercise that while Scala’s combinators support back-tracking, they only support LL(*) grammars.

Code

M-Expression lexer/parser: MExpEngine.scala

Related articles