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 · Accepted Answer · 2015-05-25 02:06:09Z

4

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

answered May 25, 2015 at 2:06

Kolmar

14.2k1 gold badge25 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Joshua Snider Over a year ago

I ended up going with the second suggestion.

Collectives™ on Stack Overflow

Stack overflow in mutually recursive scala parser

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related