表示 Scala Parser 中的临时运算符优先级

Question

所以我正在尝试使用 scala RegexParsers 专门为我正在使用的编程语言的算术片段编写一个解析器。就目前而言，我的顶级表达式解析器的形式是：

parser: Parser[Exp] = binAppExp | otherKindsOfParserLike | lval | int

它接受 lvals（像 "a.b, a.b[c.d], a[b], {record=expression, like=this}" 这样的东西就好了。现在，我想启用像 "1 + b / c = d" 这样的表达式，但可能使用（源语言，而不是 Scala）编译时用户-定义的运算符。

我最初的想法是，如果我按优先级对操作进行递归和数字编码，那么我可以临时添加更高的优先级，并且每个优先级都可以在右侧解析消耗较低优先级的子项的运算表达式。所以，我正在尝试用一些相当常见的运算符来构建一个这个想法的玩具。所以我希望 "1 * 2+1" 解析成类似 Call(*, Seq(1, Call(+ Seq(2,1)))) 的东西，其中 case class Call(functionName: String, args: Seq[Exp]) extends Exp.

相反，它解析为 IntExp(1)。

这有什么不能工作的原因吗（它是以我想念的方式左递归的吗？如果是这样，我确定还有其他问题，或者它永远不会终止，对吧？ ), 还是出于其他原因完全错误？

  def binAppExp: Parser[Exp] = {
    //assume a registry of operations
    val ops = Map(
      (7, Set("*", "/")),
      (6, Set("-", "+")),
      (4, Set("=", "!=", ">", "<", ">=", "<=")),
      (3, Set("&")),
      (2, Set("|"))
    )

    //relevant ops for a level of precedence
    def opsWithPrecedence(n: Int): Set[String] = ops.getOrElse(n, Set.empty)

    //parse an op with some level of precedence
    def opWithPrecedence(n: Int): Parser[String] = ".+".r ^? (
      { case s if opsWithPrecedence(n).contains(s) => s },
      { case s => s"SYMBOL NOT FOUND: $s" }
      )

    //assuming the parse happens, encode it as an AST representation
    def folder(h: Exp, t: LangParser.~[String, Exp]): CallExp =
      CallExp(t._1, Seq(h, t._2))

    val maxPrecedence: Int = ops.maxBy(_._1)._1

    def term: (Int => Parser[Exp]) = {
      case 0 => lval | int | notApp | "(" ~> term(maxPrecedence) <~ ")"
      case n =>
        val lowerTerm = term(n - 1)
        lowerTerm ~ rep(opWithPrecedence(n) ~ lowerTerm) ^^ {
          case h ~ ts => ts.foldLeft(h)(folder)
        }
    }

    term(maxPrecedence)
  }

Answer 1

好吧，我想做的事情本身并没有什么不可能，只是在细节上错了。

核心思想就是：维护从优先级到 operators/parsers 的映射，并根据 table 递归查找解析。如果您允许括号表达式，只需在对括号项的解析器的调用中嵌套对最先例的可能解析器的调用。

以防万一其他人想做这样的事情，这里是一组 arithmetic/logical 运算符的代码，大量注释将其与上述内容联系起来：

 def opExp: Parser[Exp] = {
sealed trait Assoc

val ops = Map(
  (1, Set("*", "/")),
  (2, Set("-", "+")),
  (3, Set("=", "!=", ">", "<", ">=", "<=")),
  (4, Set("&")),
  (5, Set("|"))
)

def opsWithPrecedence(n: Int): Set[String] = ops.getOrElse(n, Set.empty)

/* before, this was trying to match the remainder of the expression,
   so something like `3 - 2` would parse the Int(3),
   and try to pass "- 2" as an operator to the op parser.
   RegexParsers has an implicit def "literal : String => SubclassOfParser[String]",
   that I'm using explicitly here.
*/

def opWithPrecedence(n: Int): Parser[String] = {
  val ops = opsWithPrecedence(n)
  if (ops.size > 1) {
    ops.map(literal).fold (literal(ops.head)) {
      case (l1, l2) => l1 | l2
    }
  } else if (ops.size == 1) {
    literal(ops.head)
  } else {
    failure(s"No Ops for Precedence $n")
  }
}

def folder(h: Exp, t: TigerParser.~[String, Exp]): CallExp = CallExp(t._1, Seq(h, t._2))

val maxPrecedence: Int = ops.maxBy(_._1)._1

def term: (Int => Parser[Exp]) = {
  case 0 => lval | int | "(" ~> { term(maxPrecedence) } <~ ")"
  case n if n > 0 =>
    val lowerTerm = term(n - 1)
    lowerTerm ~ rep(opWithPrecedence(n) ~ lowerTerm) ^^ {
      case h ~ ts if ts.nonEmpty => ts.foldLeft(h)(folder)
      case h ~ _ => h
    }
}

term(maxPrecedence)

}

表示 Scala Parser 中的临时运算符优先级

Representing ad-hoc operator precedence in Scala Parser

parsing

scala

context-free-grammar