One of the reasons I chose to do my StringArt applet as my first Scala applet was because Scala includes a nifty capability called parser combinators.

A parser is a function that converts a stream of input tokens into a data structure that can be more easily digested by the application. A combinator is a way of combing two functions to produce a composed function. A parser combinator is a way of combining two parsers to produce another parser.

The Parser classes in Scala include methods to combine Parsers in various ways and to add functions to be executed when a parse succeeds, to build the resulting datastructure.

Parser combinators simplify the creation of some parsers, including the simple expression parsing I wanted. When using Scala, the specification of the syntax to be parsed, which might normally be done in a separate file which is read by a separate parser (as when using a parser generator such as yacc), can be done directly in a Scala source file.

Scala's syntax has two features that make it possible to write a syntax specification directly in Scala that still looks a lot like a BNF description.

1. (Almost) any operator string can be used as a method name.
2. A method that takes a single argument can be written without parentheses.

The parser combinator class is designed to be able to generate an abstract syntax tree (AST) representing the parse, which can then be easily manipulated by the application. In the following example, we create a parser that builds an AST which we then evaluate to produce a value.

Contents

• Basic Parser
• Repeated Terms
• Precedence
• Parentheses
• Lexical
• Precedence Revisited
• Wrap Up

Basic Parser

We start with a simple Expr base class for our AST elements, with case classes for constant values and an add operator. The base Expr class is a sealed class, so all of its case classes, including whatever we add below, must go into the same source file as the base class.

Now we create a simple parser that understands expressions consisting either of a single integer or two integers with a plus between them.

The parse, apply, test and main methods are all helper methods so that we can run our parser and see what it is doing. So far our actual parser consists only of the value, sum and expr definitions.

In the above code, the tilda character ~ is a Parser method that composes two parsers into another parser that sequentially calls the two composed parsers, and the vertical bar character | creates a parser which calls the second parser only if the first parser fails. The double carat ^^ passes the parsed value to a function that builds the AST element. When we want to match against a parse sequence and extract more than one value, we can use a case statement after the ^^. That case pattern should match the pattern of the parsers (such as can be seen in the sum parser and its case pattern).

Strings in the middle of these sequences of parsers, such as "+" in the sum parser, are implicitly converted into keyword parsers that accept only that literal string.

You can cut and paste the above two code fragments into a file, load it into the Scala interpreter with the :load command, and test it by entering commands such as the following:

Repeated Terms

Our parser only handles additions with two terms. In order to handle additions with three or more terms, we redefine ExprParser.sum using the repsep method:

We also add the ESum case class:

In order to add a subtract operator, we once again modify our ExprParser.sum method, this time using the * operator. We also add our subtract operator - to the list of delimiters:

Note that we are using a triple carat ^^^ here rather than the double carat ^^ that we used earlier. The triple carat operator does not use any data from the parser in the return value. In our use, we are returning a function which will be used by the * operator to collapse the values in the list.

We also add the ESub case class:

Now we can enter expressions like these:

Precedence

Next we add multiply and divide operators. As when we added the subtract operator, we add the * and / delimiters to ExprParser.lexical.delimiters and we add case classes EMul and EDiv:

However, since multiplication and division have higher precedence than add and subtract, we can't just add those operators to the sum parser like we added subtract. Instead, we create a product parser to handle the two new operators. We insert this logically between the sum and value parsers:

We can now enter expressions containing multiplication as well as addition and have them properly evaluated:

Parentheses

We would like to be able to use parentheses, so we add those two characters to ExprParser.lexical.delimiters. We add a parens parser, we add a term parser that accepts either a number or a value in parentheses, and we modify the product parser to call for a term rather than a value:

We don't need to provide a value expression for the term parser because the default value for the | operator is the value of whichever expression was parsed, which is what we want. We don't need to provide a value expression for the parens parser because the ~> operator throws away the value on the left and the <~ operator throws away the value on the right, so we are left with the value of the expr in the middle.

Now we can enter expressions with parentheses when we want to change the order of operations:

Unary Operators

We want to be able to specify negative numbers. We can't just make a leading negative sign an optional part of our numericLit token because then we can't parse a string such as 2-1. Instead, we implement a unary minus operation with a precendence higher than any of our binary operators.

The minus character is already in our set of delimiters, so we don't need to change that list. We add a EUMinus case class, add a unaryMinus parser definition, and modify the term parser to include the unaryMinus parser:

We need to specify the return type for unaryMinus because it is recursive (through the call to term), so Scala does not automatically infer its type.

Now we can parse expressions that include unary minus:

Lexical

The standard Scala lexical analyzer implementation of numericLit only parses integers, but we want floating point notation, so we extend the standard lexical class to do that. Note the first line of the class, where it overrides the definition of the token method to be either our own floatingToken or a token from our superclass. The rest of ExprLexical is the definition of the floatingToken token, complete with optional signed exponent.

We then modify our ExprParser class to use our own lexical parser so that we can parse floats or ints:

Now we can enter expressions with either integer or floating point numbers:

Precedence Revisited

If we wanted to add some more binary operators at a different level of precedence (such as the integer shift operators << and >>), we could handle that the same way as we did when we added multiply and divide, by adding a new rule and modifying the existing rules to insert it at the right location. It would be nicer if we could factor out the precedence rules so that we don't need multiple binary operator rules. Scala's parser classes do not directly support precedence rules, but we can add them relatively easily.

We replace the product and sum parsers with a binary parser and we call that instead of sum from our expr parser. We factor out the binary operations into a binaryOp method where for each precedence level we list each binary operator and its corresponding AST node. The binary parser takes an argument which is the current precedence level.

Now if we want to add binary operators at a new precedence level, we only need to modify the binaryOp method, update the value of maxPrec, and add our case classes.

Wrap Up

Below is the complete example in its final form. You should be able to copy and paste this one code fragment and have a working four-function floating point expression parser.

In my StringArt applet I also implemented variables and function calls, but those did not demonstrate any additional features of Scala's parser combinators, so I have left that as an exercise for the reader.

For additional reading check out these other parser combinator pages:

• Debasish Ghosh blog entry in which he developers a parser for a stock (shares) trading language that looks very much like written English.
• Daniel Spiewak blog entry in which he builds a parser for a simple language. Look in the comments for a link to an on-line version of Wadler's 1985 paper.
• Matt Malone blog entry in which be builds a parser for the Subversion client-server message protocol syntax, using lots of RegexParsers.
• Part 4 of Stefan Zeiger blog on parser combinators, where he creates a parser for interger expressions using * and +. The three previous parts deal more generally with parser combinators, with the promise of additional parts going into more detail about Scala parser combinators.
• Philip Wadler's 1985 paper on parser combinators.
• Adriaan Moors's Parsing in Scala paper. One of Adriaan's examples is a parser that handles the four basic arithmetic functions. In that example, the evaluation of the expression is done by the parser, whereas in my example I create an AST for later evaluation. I did this because in my real usage, I evaluate the expression multiple times, each time with different values for the variables which can be referenced by the expression.
• The "Programming in Scala" book has a chapter on Parser Combinators.
• The scaladoc page for the Parsers.Parser class in Scala lists the parser operators, and the scaladoc for the Parsers trait lists the parser method names.
• This Parser combinator in Java was done by using parser combinators from Haskell and converting them to Java.
• A 2001 paper about the Haskell Parsec parser.