算术表达式语法和解析器 [英] Arithmetic Expression Grammar and Parser

问题描述

最近我正在寻找算术表达式的体面语法，但只找到了一些琐碎的语法，例如忽略了 pow(..., ...).然后我自己尝试了它，但有时它并没有像人们预期的那样工作.例如，我错过了在表达式前面允许一元 - 并修复它.也许有人可以看看我目前的方法并改进它.此外，我认为其他人可以利用，因为能够解析算术表达式是一项常见任务.

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?)

推荐答案

为了获得更好的性能，我建议在定义解析器时使用 private lazy val 而不是 private def.否则，每当解析器被引用时，它就会被再次创建.

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.

这篇关于算术表达式语法和解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！