使用scala中的解析器组合器逐步评估

Question

我刚学习Scala解析器组合库.我已经尝试了一个工作解析器,它使用抽象语法树解析一些算术表达式.所以我打电话的时候

phrase(expr)(tokens)

我的解析器解析所有输入然后给我一个评估.但是我怎么能逐步评估呢？

说

3 + 4*7

它打印

3 + 28

然后

31

在单独的行中.

我已经扫描了api,但那里的文档并不是很有帮助...感谢您的帮助.

Answer 1

这是一个非常简单的实现,你要做的是:

首先,我们定义表达式层次结构.您需要根据具体问题进行定制.

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