使用Scala Parsers的操作员关联性

Question

所以我一直在尝试用Scala的解析器编写一个计算器,它很有趣,除了我发现操作符关联性是倒退的,当我试图让我的语法左递归时,即使它完全是明确的,我得到了堆栈溢出.

为了澄清,如果我有一个规则,如:def减法:Parser [Int] = num~" - "~add {x => x._1._1 - x._2}然后评估7 - 4 - 3出来是6而不是0.

我实际实现这个的方式是我正在组成一个二叉树,其中运算符是非叶节点,叶节点是数字.我评估树的方式是留给孩子(操作员)的右孩子.在为7 - 4 - 5构建树时,我希望它看起来像是:

-
-   5
7   4   NULL   NULL

其中 - 是根,其子节点是 - 和5,第二个孩子是7和4.

但是,我能够轻松构建的唯一树是

-
7   -
NULL   NULL   4   5

这是不同的,而不是我想要的.

基本上,简单的括号是7 - (4 - 5),而我想要(7 - 4) - 5.

我怎么能破解这个？无论如何,我觉得我应该能够编写一个具有正确运算符优先级的计算器.我应该首先对所有内容进行标记,然后反转我的令牌吗？我是否可以通过抓住正确孩子的所有左子女并让他们成为正确孩子的父母的正确孩子并让父母成为前右孩子的左孩子来翻转我的树？它在第一次近似似乎很好,但我并没有真正考虑过它.我觉得必须有一些我不知道的情况.

我的印象是我只能使用scala解析器创建一个LL解析器.如果您了解其他方式,请告诉我!

Answer 1

Scala的解析器组合器(Parsers特征)的标准实现不支持左递归语法.但是,PackratParsers如果需要左递归,则可以使用.也就是说,如果你的语法是一个简单的算术表达式解析器,你绝对不需要左递归.

编辑

有一些方法可以使用正确的递归并仍然保持左关联性,如果你热衷于此,只需查找算术表达式和递归下降解析器.当然,正如我所说,你可以使用PackratParsers,它允许左递归.

但是,在不使用的情况下处理关联性的最简单方法PackratParsers是避免使用递归.只需使用其中一个重复运算符来获取a List,然后foldLeft或foldRight根据需要.简单的例子:

trait Tree
case class Node(op: String, left: Tree, right: Tree) extends Tree
case class Leaf(value: Int) extends Tree

import scala.util.parsing.combinator.RegexParsers

object P extends RegexParsers {
  def expr = term ~ (("+" | "-") ~ term).* ^^ mkTree
  def term = "\\d+".r ^^ (_.toInt)
  def mkTree(input: Int ~ List[String ~ Int]): Tree = input match {
    case first ~ rest => ((Leaf(first): Tree) /: rest)(combine)
  }
  def combine(acc: Tree, next: String ~ Int) = next match {
    case op ~ y => Node(op, acc, Leaf(y))
  }
}

您可以在scala-dist存储库中找到其他更完整的示例.