Arithmetic Expression Grammar and Parser

Question

Recently I was looking for a decent grammar for arithmetic expressions but found only trivial ones, ignoring pow(..., ...) for example. Then I tried it on my own, but sometimes it didn´t worked as one expects. For example, I missed to allow a unary - in front of expressions and fixed it. Perhaps someone can take a look at my current approach and improve it. Furthermore I think others can take advantage because it´s a common task to be able to parse arithmetic expressions.

import scala.math._
import scala.util.parsing.combinator._
import scala.util.Random

class FormulaParser(val constants: Map[String,Double] = Map(), val userFcts: Map[String,String => Double] = Map(), random: Random = new Random) extends JavaTokenParsers {
  require(constants.keySet.intersect(userFcts.keySet).isEmpty)
  private val allConstants = constants ++ Map("E" -> E, "PI" -> Pi, "Pi" -> Pi) // shouldn´t be empty
  private val unaryOps: Map[String,Double => Double] = Map(
   "sqrt" -> (sqrt(_)), "abs" -> (abs(_)), "floor" -> (floor(_)), "ceil" -> (ceil(_)), "ln" -> (math.log(_)), "round" -> (round(_)), "signum" -> (signum(_))
  )
  private val binaryOps1: Map[String,(Double,Double) => Double] = Map(
   "+" -> (_+_), "-" -> (_-_), "*" -> (_*_), "/" -> (_/_), "^" -> (pow(_,_))
  )
  private val binaryOps2: Map[String,(Double,Double) => Double] = Map(
   "max" -> (max(_,_)), "min" -> (min(_,_))
  )
  private def fold(d: Double, l: List[~[String,Double]]) = l.foldLeft(d){ case (d1,op~d2) => binaryOps1(op)(d1,d2) } 
  private implicit def map2Parser[V](m: Map[String,V]) = m.keys.map(_ ^^ (identity)).reduceLeft(_ | _)
  private def expression:  Parser[Double] = sign~term~rep(("+"|"-")~term) ^^ { case s~t~l => fold(s * t,l) }
  private def sign:        Parser[Double] = opt("+" | "-") ^^ { case None => 1; case Some("+") => 1; case Some("-") => -1 }
  private def term:        Parser[Double] = longFactor~rep(("*"|"/")~longFactor) ^^ { case d~l => fold(d,l) }
  private def longFactor:  Parser[Double] = shortFactor~rep("^"~shortFactor) ^^ { case d~l => fold(d,l) }
  private def shortFactor: Parser[Double] = fpn | sign~(constant | rnd | unaryFct | binaryFct | userFct | "("~>expression<~")") ^^ { case s~x => s * x }
  private def constant:    Parser[Double] = allConstants ^^ (allConstants(_))
  private def rnd:         Parser[Double] = "rnd"~>"("~>fpn~","~fpn<~")" ^^ { case x~_~y => require(y > x); x + (y-x) * random.nextDouble } | "rnd" ^^ { _ => random.nextDouble }
  private def fpn:         Parser[Double] = floatingPointNumber ^^ (_.toDouble) 
  private def unaryFct:    Parser[Double] = unaryOps~"("~expression~")" ^^ { case op~_~d~_ => unaryOps(op)(d) }
  private def binaryFct:   Parser[Double] = binaryOps2~"("~expression~","~expression~")" ^^ { case op~_~d1~_~d2~_ => binaryOps2(op)(d1,d2) }
  private def userFct:     Parser[Double] = userFcts~"("~(expression ^^ (_.toString) | ident)<~")" ^^ { case fct~_~x => userFcts(fct)(x) }
  def evaluate(formula: String) = parseAll(expression,formula).get
}

So one can evaluate the following:

val formulaParser = new FormulaParser(
    constants = Map("radius" -> 8D, 
                    "height" -> 10D, 
                    "c" -> 299792458, // m/s
                    "v" -> 130 * 1000 / 60 / 60, // 130 km/h in m/s
                    "m" -> 80),
    userFcts  = Map("perimeter" -> { _.toDouble * 2 * Pi } ))

println(formulaParser.evaluate("2+3*5")) // 17.0
println(formulaParser.evaluate("height*perimeter(radius)")) // 502.6548245743669
println(formulaParser.evaluate("m/sqrt(1-v^2/c^2)"))  // 80.00000000003415

Any improvement suggestions? Do I use the right grammar or is it only a question of time until a user types in a valid (with respect to my provided functions) arithmetic expression that can´t be parsed?
(What´s about operator precedence?)

Ophthalmoscope

E.g.: a userFct starting with an E yields a parse error, because math.E is matched before. How can I prevent this or how is the right precedence in combining Parser[Double] with |? – Ophthalmoscope

This code is pretty nice @Peter Schmitz. You should put it in a library on Github then I can give you my improments. I'm using it as a starting point for a project I'm working on. – Tanika

@Tanika Thank you. When time permits I will publish it on Github, but you are free to do so and use my code with your improvements. I am looking forward to see the improvements because I am still asking myself if the grammar is right. – Ophthalmoscope

@PeterSchmitz quite a read. I have read this code for the first time. and I guess there is still no github repository. Some documentation might have been helpful. most of the grammar is quite clear but it took me a while to figure out where your terminals are (actually is). this is especially the case for people who are not familiar with the scala parsing dsl. – Highboy

@Alex, years later I have the same problems. Sorry. Still no repo, because I haven't had time to polish, document and put all in a repo. Please feel free to do so und improve! I am still not sure if this is the right grammar. – Ophthalmoscope

@PeterSchmitz I would do the parsing differently to be honest. it's faster not to have an AST, but having an AST makes it a lot clearer. anyway the read was insightful as I'm just starting scala. – Highboy

How did you figure out map2Parser would create parsers if you did ^^ identity ? – Volva

Sorry, it's years ago, I am not into that code anymore. Probably I would use another parsing library anyway, e.g. fastparse or parboiled2. – Ophthalmoscope

Answer 1

For a better performance I suggest to use private lazy val instead of private def when defining parsers. Otherwise whenever a parser is references it is created again.

Nice code BTW.

Purpleness

You´re right, thanks. I tried it while coding but it didn´t work when running the parser on several inputs. I guessed the parser can only be used once, so I chose def similar to Programming in Scala book. Now it works with lazy val. – Ophthalmoscope

Answer 2

Well maybe add variables in the loop :

import scala.math._
import scala.util.parsing.combinator._
import scala.util.Random

class FormulaParser(val variables: Set[String] = Set(),
                    val constants: Map[String, Double] = Map(),
                    val unary: Map[String, Double => Double] = Map(),
                    val binary: Map[String, (Double, Double) => Double] = Map(),
                    val userFcts: Map[String, String => Double] = Map(),
                    random: Random = new Random) extends JavaTokenParsers {
    require(constants.keySet.intersect(userFcts.keySet).isEmpty)
    private val allConstants = constants ++ Map("E" -> E, "PI" -> Pi, "Pi" -> Pi)
    // shouldn´t be empty
    private val unaryOps = Map[String, Double => Double](
    "sqrt" -> (sqrt(_)), "abs" -> (abs(_)), "floor" -> (floor(_)), "ceil" -> (ceil(_)), "ln" -> (math.log(_)), "round" -> (round(_).toDouble), "signum" -> (signum(_))
    ) ++ unary
    private val binaryOps1 = Map[String, (Double, Double) => Double](
        "+" -> (_ + _), "-" -> (_ - _), "*" -> (_ * _), "/" -> (_ / _), "^" -> (pow(_, _))
    )
    private val binaryOps2 = Map[String, (Double, Double) => Double](
        "max" -> (max(_, _)), "min" -> (min(_, _))
    ) ++ binary

    type Argument = Map[String, Double]
    type Formula = Argument => Double

    private def fold(d: Formula, l: List[~[String, Formula]]) = l.foldLeft(d) { case (d1, op ~ d2) => arg => binaryOps1(op)(d1(arg), d2(arg))}
    private implicit def set2Parser[V](s: Set[String]) = s.map(_ ^^ identity).reduceLeft(_ | _)
    private implicit def map2Parser[V](m: Map[String, V]) = m.keys.map(_ ^^ identity).reduceLeft(_ | _)
    private def expression: Parser[Formula] = sign ~ term ~ rep(("+" | "-") ~ term) ^^ { case s ~ t ~ l => fold(arg => s * t(arg), l)}
    private def sign: Parser[Double] = opt("+" | "-") ^^ { case None => 1; case Some("+") => 1; case Some("-") => -1}
    private def term: Parser[Formula] = longFactor ~ rep(("*" | "/") ~ longFactor) ^^ { case d ~ l => fold(d, l)}
    private def longFactor: Parser[Formula] = shortFactor ~ rep("^" ~ shortFactor) ^^ { case d ~ l => fold(d, l)}
    private def shortFactor: Parser[Formula] = fpn | sign ~ (constant | variable | rnd | unaryFct | binaryFct | userFct | "(" ~> expression <~ ")") ^^ { case s ~ x => arg => s * x(arg)}
    private def constant: Parser[Formula] = allConstants ^^ (name => arg => allConstants(name))
    private def variable: Parser[Formula] = variables ^^ (name => arg => arg(name))
    private def rnd: Parser[Formula] = "rnd" ~> "(" ~> fpn ~ "," ~ fpn <~ ")" ^^ { case x ~ _ ~ y => (arg: Argument) => require(y(arg) > x(arg)); x(arg) + (y(arg) - x(arg)) * random.nextDouble} | "rnd" ^^ { _ => arg => random.nextDouble}
    private def fpn: Parser[Formula] = floatingPointNumber ^^ (value => arg => value.toDouble)
    private def unaryFct: Parser[Formula] = unaryOps ~ "(" ~ expression ~ ")" ^^ { case op ~ _ ~ d ~ _ => arg => unaryOps(op)(d(arg))}
    private def binaryFct: Parser[Formula] = binaryOps2 ~ "(" ~ expression ~ "," ~ expression ~ ")" ^^ { case op ~ _ ~ d1 ~ _ ~ d2 ~ _ => arg => binaryOps2(op)(d1(arg), d2(arg))}
    private def userFct: Parser[Formula] = userFcts ~ "(" ~ (expression ^^ (_.toString) | ident) <~ ")" ^^ { case fct ~ _ ~ x => arg => userFcts(fct)(x)}
    def evaluate(formula: String) = parseAll(expression, formula).get
}

So now you have to pass a map to evaluate and you can do :

val formulaParser = new FormulaParser(Set("x"), unary = Map(
    "sin" -> (math.sin(_)), "cos" -> (math.cos(_)), "tan" -> (math.tan(_))
))
val formula = formulaParser.evaluate("sin(x)^x")
val function: Double => Double = x => formula(Map("x" -> x))
println(function(5.5))

As you can see, I also added parameters to add unary and binary functions.

Thanks for that good code by the way!

Emerald