Приоритет оператора с помощью комбинаторов Scala Parser

Question

Я работаю над логикой синтаксического анализа, которая должна учитывать приоритет операторов. Мои потребности не слишком сложны. Для начала мне нужно умножение и деление, чтобы иметь более высокий приоритет, чем сложение и вычитание.

Например: 1 + 2 * 3 следует рассматривать как 1 + (2 * 3). Это простой пример, но вы понимаете!

[Есть еще пара пользовательских токенов, которые мне нужно добавить в логику приоритетов, которые я могу добавить, основываясь на предложениях, которые я получаю здесь.]

Вот один пример работы с приоритетом операторов: http://jim-mcbeath.blogspot.com/2008/09/scala-parser-combinators.html.

Есть ли другие идеи?

Answer 1

Это немного проще, чем пример Джима МакБита, но он делает то, что, как вы говорите, вам нужно, то есть исправляет арифметическое значение, а также учитывает скобки. Я адаптировал пример из программирования в Scala, чтобы он действительно выполнял вычисления и давал ответ.

Это должно быть совершенно очевидно. Существует иерархия, образованная expr состоит из terms перемежаются с операторами, terms состоит из factors с операторами, и factors являются числами с плавающей точкой или выражениями в скобках.

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
}