Stack overflow in mutually recursive scala parser

Question

So, I'm working on this thing in scala to try to parse arithmetic expressions. I have this below where an expr can either be an add of two exprs or an integer constant, but it gets stuck in an infinite loop of add calling expr calling add calling expr... I'm pretty new to scala, but not to parsing. I know I'm doing something wrong, but the real question is, it it something simple?

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")
}

Kolmar Kolmar · Accepted Answer · 2015-05-25T02:06:09

Basic RegexParsers can't parse left-recursive grammars. To make it work, you can either modify the rule for add to remove left-recursiveness:

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

or use PackratParsers, which can parse such grammars:

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") 
}

Stack overflow in mutually recursive scala parser

1 Answers