3

我只是在学习 Scala 解析器组合器库。我已经尝试了一个可以使用抽象语法树解析一些算术表达式的工作解析器。所以当我打电话时

phrase(expr)(tokens)

我的解析器解析所有输入然后给我一个评估。但是我怎样才能有一步一步的评估呢？

说

3 + 4 * 7

它打印

3 + 28

然后

31

在单独的行中。

我已经浏览了 API，但那里的文档不是很有帮助......感谢您的帮助。

4

2 回答 2

5

这是您尝试执行的操作的一个非常简单的实现：

首先，我们定义一个表达式层次结构。您需要根据您的具体问题对此进行调整。

trait Expr {
  def eval: Int
}
case class IntLeaf(n: Int) extends Expr {
  def eval = n
  override def toString = "%d".format(n)
}
case class Sum(a: Expr, b: Expr) extends Expr {
  def eval = a.eval + b.eval
  override def toString = "(%s + %s)".format(a, b)
}

然后，一个只结合最底层分支的函数。

def combineLeaves(e: Expr): Expr = {
  e match {
    case IntLeaf(n) => IntLeaf(n)
    case Sum(IntLeaf(a), IntLeaf(b)) => IntLeaf(a + b)
    case Sum(a, b) => Sum(combineLeaves(a), combineLeaves(b))
  }
}

然后，一个函数，一次将树组合一层，边打印边打印。

def printEval(e: Expr) {
  println(e)
  e match {
    case IntLeaf(n) =>
    case _ => printEval(combineLeaves(e))
  }
}

现在，解析器。同样，您必须根据您的数据对其进行调整。

object ArithmeticParser extends RegexParsers {
  private def int: Parser[IntLeaf] = regex(new Regex("""\d+""")).map(s => IntLeaf(s.toInt))
  private def sum: Parser[Sum] = ("(" ~> expr ~ "+" ~ expr <~ ")").map { case (a ~ _ ~ b) => Sum(a, b) }
  private def expr = int | sum
  def parse(str: String): ParseResult[Expr] = parseAll(expr, str)
  def apply(str: String): Expr = ArithmeticParser.parse(str) match {
    case ArithmeticParser.Success(result: Expr, _) => result
    case _ => sys.error("Could not parse the input string: " + str)
  }

}

以下是你如何使用它：

scala> printEval(ArithmeticParser("((1 + 7) + ((3 + 9) + 5))"))
((1 + 7) + ((3 + 9) + 5))
(8 + (12 + 5))
(8 + 17)
25
于 2012-09-24T21:02:27.600 回答
2

解析器组合器永远不会给你任何评估。使用解析器组合器解析输入字符串并构建一些表示它的数据结构。评估是您以某种方式处理数据结构并执行所需简化的另一个步骤。因此，有了你的表达式3+4*7，在解析阶段你可以构建以下抽象语法树：

   +
  / \
 3 *   
    / \
   4 7

然后，在评估阶段，递归地遍历树，对每个非叶子节点应用节点操作到其左右子树的评估结果。

如果文档没有帮助，您可以参考Programming in Scala的解析器组合器章节，该章节的第一版是免费提供的。

我最近还写了一篇关于Scala 解析器组合器的博文，其中我讨论了一个与您的场景有些相似的场景。

于 2012-09-24T20:44:05.057 回答