运算符优先与Scala解析器组合器 [英] Operator Precedence with Scala Parser Combinators

问题描述

我正在研究需要考虑运算符优先级的解析逻辑。我的需求并不太复杂。首先，我需要乘法和除法比加法和减法具有更高的优先级。

例如：1 + 2 * 3应该被视为1 +（2 * 3 ）。这是一个简单的例子，但你明白了！

[我需要添加更多的自定义标记以添加到优先逻辑，我可以添加基于我在这里收到的建议。]

以下是处理运算符优先级的一个示例： http://jim-mcbeath.blogspot.com/2008/09/scala-parser-combinators.html#precedencerevisited 。

是否还有其他想法？

解决方案

这比Jim McBeath的例子更简单一些，但它可以满足你所说的需要，即正确的算术预设，并且还允许使用括号。我调整了Scala中的 Programming 中的例子来让它实际进行计算并提供答案。

它应该是不言自明的。通过说 expr 由散布在运算符中的 terms ， terms 包含因子与运算符，因子是浮点数或圆括号中的表达式。 / p>

  import scala.util.parsing.combinator.JavaTokenParsers 
 $ b $ class Arith扩展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：解析器[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：解析器[D] = fpn | （〜> expr<〜）
 def fpn：Parser [D] = floatingPointNumber ^^（_.toDouble）
 
} 
 
 object Main通过应用程序扩展Arith {
 val input =（1 + 2 * 3 + 9）* 2 + 1
 println（parseAll（expr，input）.get）//打印33.0 
} 
  

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?

解决方案

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
}

这篇关于运算符优先与Scala解析器组合器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！