Operator Precedence with Scala Parser Combinators

functional-programming, parser-combinators, scala

Solution

This is a bit simpler that Jim McBeath's example, but it does what you say you need, i.e. correct arithmetic precdedence, and also allows for parentheses. I adapted the example from Programming in Scala to get it to actually do the calculation and provide the answer.

It should be quite self-explanatory. There is a heirarchy formed by saying an `expr` consists of `terms` interspersed with operators, `terms` consist of `factors` with operators, and `factors` are floating point numbers or expressions in parentheses.

import scala.util.parsing.combinator.JavaTokenParsers

class Arith extends JavaTokenParsers {

  type D = Double

  def expr:   Parser[D]    = term ~ rep(plus | minus)     ^^ {case a~b => (a /: b)((acc,f) => f(acc))} 
  def plus:   Parser[D=>D] = "+" ~ term                   ^^ {case "+"~b => _ + b}
  def minus:  Parser[D=>D] = "-" ~ term                   ^^ {case "-"~b => _ - b}
  def term:   Parser[D]    = factor ~ rep(times | divide) ^^ {case a~b => (a /: b)((acc,f) => f(acc))}
  def times:  Parser[D=>D] = "*" ~ factor                 ^^ {case "*"~b => _ * b }
  def divide: Parser[D=>D] = "/" ~ factor                 ^^ {case "/"~b => _ / b} 
  def factor: Parser[D]    = fpn | "(" ~> expr <~ ")" 
  def fpn:    Parser[D]    = floatingPointNumber          ^^ (_.toDouble)

}

object Main extends Arith with App {
  val input = "(1 + 2 * 3 + 9) * 2 + 1"
  println(parseAll(expr, input).get) // prints 33.0
}

Problem

I am working on a Parsing logic that needs to take operator precedence into consideration. My needs are not too complex. To start with I need multiplication and division to take higher precedence than addition and subtraction. For example: 1 + 2 * 3 should be treated as 1 + (2 * 3). This is a simple example but you get the point! [There are couple more custom tokens that I need to add to the precedence logic, which I may be able to add based on the suggestions I receive here.] Here is one example of dealing with operator precedence: http://jim-mcbeath.blogspot.com/2008/09/scala-parser-combinators.html#precedencerevisited. Are there any other ideas?

Original source