使用Scala解析器的运算符关联性

Question

所以我一直在尝试用Scala的解析器写一个计算器，这很有趣，除了我发现运算符的关联性是反向的，而且当我试图让我的语法左递归时，即使它是完全明确的，我也会得到堆栈溢出。

为了清楚起见，如果我有这样一个规则: def subtract: ParserInt = 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，，允许左递归。

但是，在不使用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存储库中找到其他更完整的示例。

Answer 2

我对你的问题的解释如下：

如果您编写像def expression = number ~ "-" ~ expression这样的规则，然后对语法树的每个节点求值，那么您会发现在3 - 5 - 4中，首先计算5 - 4，结果为1，然后计算3 - 1，结果为2。

另一方面，如果您编写像def expression = expression ~ "-" ~ number这样的规则，则这些规则是左递归的，并且会溢出堆栈。

这个问题有三种解决方案：

1. 对抽象语法树进行后处理，将其从右关联树转换为左关联树。如果您使用语法规则上的操作来立即执行计算，这对您不起作用。
2. 将规则定义为def expression = repsep(number, "-")，然后在计算计算时，对解析后的数字(将出现在平面列表中)进行循环，无论哪个方向为您提供所需的关联性。如果将出现一种以上的运算符，则不能使用它，因为运算符将被丢弃。
3. 将该规则定义为def expression = number ~ ( "-" ~ number) *。你将有一个初始的数字，再加上一个扁平列表中的一组运算符-数字对，可以按你想要的任何方向进行处理(尽管从左到右在这里可能更容易)。
4. 按照Daniel Sobral的建议使用PackratParsers。这可能是你最好也是最简单的选择。