1

所以我一直在尝试用 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 解析器。如果你知道另一种方法，请告诉我！

4

2 回答 2

7

Scala 的解析器组合器（Parsers特征）的标准实现不支持左递归语法。但是，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存储库中找到其他更完整的示例。

于 2012-06-03T18:17:38.343 回答
1

我将您的问题解释如下：

如果您编写规则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. PackratParsers按照 Daniel Sobral 的建议使用。这可能是您最好和最简单的选择。

于 2012-06-04T00:35:48.423 回答