Operator Priority with Scala Parser Combiners

Question

I am working on Parsing logic, which should take into account operator priority. My needs are not too complicated. First you need to multiply and divide by a higher priority than addition and subtraction.

For example: 1 + 2 * 3 should be considered as 1 + (2 * 3). This is a simple example, but you get the point!

[A few more custom tokens that I need to add to the priority logic, which I can add based on the offers I get here.]

Here is an example of using operator precedence: http://jim-mcbeath.blogspot.com/2008/09/scala-parser-combinators.html#precedencerevisited .

Are there any other ideas?

Answer 1

This is a bit simpler than the example of Jim MacBeth, but he does what you say what you need, i.e. correct arithmetic errors, and also allow brackets. I adapted an example from programming in Scala to make it actually perform the calculation and provide an answer.

That should be perfectly clear. There is a hierarchy formed by the expression expr consists of terms alternating with operators, terms consists of factors with operators, and factors are numbers or floating-point numbers 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 }