使用Scala解析器的运算符关联性
所以我一直在尝试用Scala的解析器编写一个计算器，这很有趣，除了我发现运算符的关联性是倒退的，并且当我尝试使我的语法左递归时，即使它完全无歧义，我也会得到堆栈溢出。
为了澄清，如果我有一条规则：def subtract：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解析器。 如果你知道另一种方式，请告诉我！
Scala的解析器组合器（ Parsers trait）的标准实现不支持左递归语法。 但是，如果您需要左递归，则可以使用PackratParsers 。 也就是说，如果你的语法是一个简单的算术表达式解析器，你绝对不需要左递归。
编辑
有很多方法可以使用右递归，并且仍然保持左关联性，如果您对此感兴趣，只需查看算术表达式和递归下降解析器即可。 当然，正如我所说的， 你可以使用允许左递归的PackratParsers 。
但不使用PackratParsers来处理关联性的最简单方法是避免使用递归。 只需使用其中一个重复操作符来获取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存储库中找到其他更完整的示例。
我正在解释你的问题如下：
如果您编写规则如def expression = number ~ "-" ~ expression number〜 def expression = number ~ "-" ~ expression 〜expression，然后在语法树的每个节点上评估，则会发现在3 - 5 - 4 ，首先计算5 - 4 ，结果为1 ，然后计算3 - 1 ，结果为2。
另一方面，如果您编写像def expression = expression ~ "-" ~ number的规则，则这些规则是左递归的并且会溢出堆栈。
这个问题有三种解决方案：
后处理抽象语法树，将其从右联合树转换为左联合树。 如果您正在使用语法规则的操作来立即执行计算，则这不适用于您。
将规则定义为def expression = repsep(number, "-") ，然后在评估计算时，循环解析的数字（将出现在平面列表中），无论哪个方向为您提供所需的关联性。 如果出现多种操作员，则不能使用此操作符，因为操作员将被丢弃。
将规则定义为def expression = number ~ ( "-" ~ number) * 。 您将拥有一个初始数字，并在平面列表中添加一组运算符号对，以您想要的任何方向进行处理（尽管从左到右可能更容易）。
按Daniel Sobral的建议使用PackratParsers 。 这可能是你最好也是最简单的选择。