Operator Precedence with Scala Parser Combinators

Question

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?

Missie

This is a duplicate -- there's another question, not very old, about precedence of arithmetic operators with parser combinators. Amazingly, even though the topic is exactly the same, I'm having difficult finding it. – Seoul

possible duplicate of How to change code using Scala Parser Combinators to take operator precedence into account? – Seoul

See also this question which handles associativity, a harder problem. – Seoul

Finally, look at the examples for parser combinators, many of which are arithmetic expression parsers. – Seoul

Daniel, thanks a ton for all this info! Appreciate it. – Missie

Answer 1

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
}

Equality