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.
- (Almost) any operator string can be used as a method name.
- A method that takes a single argument can be written without parentheses.
Contents
Basic Parser
We start with a simpleExpr 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.sealed abstract class Expr { def eval():Double } case class EConst(value:Double) extends Expr { def eval():Double = value } case class EAdd(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval + right.eval }
Theimport scala.util.parsing.combinator.syntactical._ object ExprParser extends StandardTokenParsers { lexical.delimiters ++= List("+") def value = numericLit ^^ { s => EConst(s.toDouble) } def sum = value ~ "+" ~ value ^^ { case left ~ "+" ~ right => EAdd(left, right) } def expr = ( sum | value ) //top level expression def parse(s:String) = { val tokens = new lexical.Scanner(s) phrase(expr)(tokens) } def apply(s:String):Expr = { parse(s) match { case Success(tree, _) => tree case e: NoSuccess => throw new IllegalArgumentException("Bad syntax: "+s) } } //Simplify testing def test(exprstr: String) = { parse(exprstr) match { case Success(tree, _) => println("Tree: "+tree) val v = tree.eval() println("Eval: "+v) case e: NoSuccess => Console.err.println(e) } } //A main method for testing def main(args: Array[String]) = test(args(0)) }
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:
ExprParser.test("123") ExprParser.test("12 + 34")
Repeated Terms
Our parser only handles additions with two terms. In order to handle additions with three or more terms, we redefineExprParser.sum using the repsep method:
We also add thedef sum = repsep(value,"+") ^^ { a:List[Expr] => ESum(a) }
ESum case class:
In order to add a subtract operator, we once again modify ourcase class ESum(a:List[Expr]) extends Expr { def eval():Double = a.foldLeft(0.0)(_ + _.eval) }
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 caratlexical.delimiters ++= List("+", "-") ... def sum = value * ( "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } | "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) } )
^^^ 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:case class ESub(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval - right.eval }
ExprParser.test("2-1") ExprParser.test("1+2+3-4")
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 thecase class EMul(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval * right.eval } case class EDiv(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval / right.eval } class ExprParser { .... lexical.delimiters ++= List("+", "-", "*", "/") .... }
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:class ExprParser { .... def product = value * ( "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } | "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) } ) def sum = product * ( ... .... }
ExprParser.test("3+4*5")
Parentheses
We would like to be able to use parentheses, so we add those two characters toExprParser.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 theclass ExprParser { ... lexical.delimiters ++= List("+", "-", "*", "/", "(", ")") ... def parens:Parser[Expr] = "(" ~> expr <~ ")" def term = ( value | parens ) def product = term * ... def expr = ( sum | term ) ... }
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:
ExprParser.test("(3+4)*5")
Unary Operators
We want to be able to specify negative numbers. We can't just make a leading negative sign an optional part of ournumericLit 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 forcase class EUMinus(e:Expr) extends Expr { def eval():Double = -e.eval } class ExprParser { ... def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) } def term = ( value | parens | unaryMinus) ... }
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:
ExprParser.test("3*-(2+2)")
Lexical
The standard Scala lexical analyzer implementation ofnumericLit
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 ourimport scala.util.parsing.combinator.lexical.StdLexical class ExprLexical extends StdLexical { override def token: Parser[Token] = floatingToken | super.token def floatingToken: Parser[Token] = rep1(digit) ~ optFraction ~ optExponent ^^ { case intPart ~ frac ~ exp => NumericLit( (intPart mkString "") :: frac :: exp :: Nil mkString "")} def chr(c:Char) = elem("", ch => ch==c ) def sign = chr('+') | chr('-') def optSign = opt(sign) ^^ { case None => "" case Some(sign) => sign } def fraction = '.' ~ rep(digit) ^^ { case dot ~ ff => dot :: (ff mkString "") :: Nil mkString "" } def optFraction = opt(fraction) ^^ { case None => "" case Some(fraction) => fraction } def exponent = (chr('e') | chr('E')) ~ optSign ~ rep1(digit) ^^ { case e ~ optSign ~ exp => e :: optSign :: (exp mkString "") :: Nil mkString "" } def optExponent = opt(exponent) ^^ { case None => "" case Some(exponent) => exponent } }
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:object ExprParser extends StandardTokenParsers { override val lexical = new ExprLexical ... }
ExprParser.test("123.456") ExprParser.test("1.2+3") ExprParser.test("5e-1 + 2")
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 theclass ExprParser { ... def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = { level match { case 1 => "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } | "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) } case 2 => "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } | "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) } case _ => throw new RuntimeException("bad precedence level "+level) } } val minPrec = 1 val maxPrec = 2 def binary(level:Int):Parser[Expr] = if (level>maxPrec) term else binary(level+1) * binaryOp(level) def expr = ( binary(minPrec) | term ) ... }
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.sealed abstract class Expr { def eval():Double } case class EConst(value:Double) extends Expr { def eval():Double = value } case class EAdd(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval + right.eval } case class ESub(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval - right.eval } case class EMul(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval * right.eval } case class EDiv(left:Expr, right:Expr) extends Expr { def eval():Double = left.eval / right.eval } case class EUMinus(e:Expr) extends Expr { def eval():Double = -e.eval } import scala.util.parsing.combinator.lexical.StdLexical class ExprLexical extends StdLexical { override def token: Parser[Token] = floatingToken | super.token def floatingToken: Parser[Token] = rep1(digit) ~ optFraction ~ optExponent ^^ { case intPart ~ frac ~ exp => NumericLit( (intPart mkString "") :: frac :: exp :: Nil mkString "")} def chr(c:Char) = elem("", ch => ch==c ) def sign = chr('+') | chr('-') def optSign = opt(sign) ^^ { case None => "" case Some(sign) => sign } def fraction = '.' ~ rep(digit) ^^ { case dot ~ ff => dot :: (ff mkString "") :: Nil mkString "" } def optFraction = opt(fraction) ^^ { case None => "" case Some(fraction) => fraction } def exponent = (chr('e') | chr('E')) ~ optSign ~ rep1(digit) ^^ { case e ~ optSign ~ exp => e :: optSign :: (exp mkString "") :: Nil mkString "" } def optExponent = opt(exponent) ^^ { case None => "" case Some(exponent) => exponent } } import scala.util.parsing.combinator.syntactical._ object ExprParser extends StandardTokenParsers { override val lexical = new ExprLexical lexical.delimiters ++= List("+","-","*","/","(",")") def value = numericLit ^^ { s => EConst(s.toDouble) } def parens:Parser[Expr] = "(" ~> expr <~ ")" def unaryMinus:Parser[EUMinus] = "-" ~> term ^^ { EUMinus(_) } def term = ( value | parens | unaryMinus ) def binaryOp(level:Int):Parser[((Expr,Expr)=>Expr)] = { level match { case 1 => "+" ^^^ { (a:Expr, b:Expr) => EAdd(a,b) } | "-" ^^^ { (a:Expr, b:Expr) => ESub(a,b) } case 2 => "*" ^^^ { (a:Expr, b:Expr) => EMul(a,b) } | "/" ^^^ { (a:Expr, b:Expr) => EDiv(a,b) } case _ => throw new RuntimeException("bad precedence level "+level) } } val minPrec = 1 val maxPrec = 2 def binary(level:Int):Parser[Expr] = if (level>maxPrec) term else binary(level+1) * binaryOp(level) def expr = ( binary(minPrec) | term ) def parse(s:String) = { val tokens = new lexical.Scanner(s) phrase(expr)(tokens) } def apply(s:String):Expr = { parse(s) match { case Success(tree, _) => tree case e: NoSuccess => throw new IllegalArgumentException("Bad syntax: "+s) } } def test(exprstr: String) = { parse(exprstr) match { case Success(tree, _) => println("Tree: "+tree) val v = tree.eval() println("Eval: "+v) case e: NoSuccess => Console.err.println(e) } } //A main method for testing def main(args: Array[String]) = test(args(0)) }
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.
