Scala Parser Combinators - Part 1

Scala Parser Combinators - Part 2  >

Scala ships with a parser library for writing your own lexers and parser from within Scala. It's a really nifty mechanism for writing DSLs embedded within a Scala program. For this example, let's write a parser that parses simple mathematical expressions, such as "1+9*8" and "4*6/2-5". An EBNF grammar for this language would look like this:

digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

number ::= digit | digit number

operator ::= "+" | "-" | "*" | "/"

expr ::= number (operator expr)?

To start writing a parser with the Scala parsing library, we write a class that extends the Parsers trait. Here's an example of a class that extends RegexParsers, a subtrait of Parsers.

class ExprParser extends RegexParsers {
    val number = "[1-9][0-9]+".r

    def expr: Parser[Any] = number ~ opt(operator ~ expr )

    def operator: Parser[Any] = "+" | "-" | "*" | "/"
}

The only difference between the Scala definition of the valid tokens and the EBNF definition is the following:

• Scala utilizes a "~" between each token
• Instead of using a "?" like you would in EBNF, Scala uses the keyword "opt"
• Although this isn't used in the Scala code shown above, instead of using a "+" to denote repetition as you would in EBNF, Scala uses the keyword "rep"

 To run this parser, we simply invoke the inherited parse method that's part of the inherited Parsers trait.

 def main(args : Array[String]) {
    val parser = new ExprParser

    val result = parser.parseAll(parser.expr, "9*8+21/7")

    println(result.get)
}

The result of this println will be:

(9~Some((*~(8~Some((+~(21~Some((/~(7~None))))))))))

Of course,this isn't a very useful result at this point. However, it sets the foundation for writing a parser in Scala using the parser library. Check out Part 2 on Scala Parser Combinators, where we expand on this topic and look at how to modify this result into something that's more useful.