在互相遞歸的scala解析器中堆棧溢出

Question

所以，我正在scala中嘗試解析算術表達式。我有下面的地方expr可以是兩個exprs的add或一個integer常量，但它被卡在一個無限循環的add調用expr調用add calling 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") 
}