scala - 相互递归 scala 解析器中的堆栈溢出

Question

所以，我正在 scala 中研究这个东西，尝试解析算术表达式。我在下面有这个，其中 expr 可以是两个 expr 的 add 或一个 integer 常量，但它陷入了无限循环添加调用 expr 调用添加调用 expr...我对 scala 很陌生，但对解析不太熟悉。我知道我做错了什么，但真正的问题是，这很简单吗？

import scala.util.parsing.combinator._

abstract class Expr

case class Add(x: Expr, y: Expr) extends Expr
case class Constant(con: String) extends Expr

class Comp extends RegexParsers {

  def integer:Parser[Expr] = """-?\d+""".r ^^ {
    s => Constant(s)
  }

  def add: Parser[Expr] = expr ~ "+" ~ expr ^^ {
    case(a ~ "+" ~ b) => Add(a, b)
  }

  def expr: Parser[Expr] = (add | integer)

}

object Compiler extends Comp {

  def main(args: Array[String]) = parse(expr, "5+ -3"))//println("5+ -3")
}

Answer 1

基本RegexParsers无法解析左递归语法。要使其正常工作，您可以修改 add 规则以删除左递归性:

def add: Parser[Expr] = integer ~ "+" ~ expr ^^ {
  case(a ~ "+" ~ b) => Add(a, b)
}

或使用PackratParsers ，它可以解析这样的语法:

class Comp extends RegexParsers with PackratParsers {

  lazy val integer:PackratParser[Expr] = """-?\d+""".r ^^ {
    s => Constant(s)
  }

  lazy val add: PackratParser[Expr] = expr ~ "+" ~ expr ^^ {
    case(a ~ "+" ~ b) => Add(a, b)
  }

  lazy val expr: PackratParser[Expr] = (add | integer)

}

object Compiler extends Comp {
  def main(args: Array[String]) = parseAll(expr, "5+ -3") 
}