Stack overflow when using parser combinators

Question

import scala.util.parsing.combinator._

object ExprParser extends JavaTokenParsers {
    lazy val name: Parser[_] = "a" ~ rep("a" | "1") | function_call
    lazy val function_call = name ~ "(" ~> name <~ ")"
}

recurs indefinitely for function_call.parseAll("aaa(1)"). Obviously, it is because 1 cannot inter the name and name enters the function_call, which tries the name, which enters the funciton call. How do you resolve such situations?

There was a solution to reduce name to simple identifier

def name = rep1("a" | "1") 
def function_call = name ~ "(" ~ (function_call | name) ~ ")"

but I prefer not to do this because name ::= identifier | function_call is BNF-ed in VHDL specification and function_call is probably shared elsewhere. The left recursion elimination found here is undesirable for the same reason

def name: Parser[_] = "a" ~ rep("a" | "1") ~ pared_name
def pared_name: Parser[_] = "(" ~> name <~ ")" | ""

BTW, I also wonder, if I fix the error, will name.parseAll consume "aaa" only as first alternative in the name rule or take whole "aaa(1)"? How can I make name to consume the whole aaa(1) before consuming only aaa? I guess that I should put function_call a first alternative in the name but it will stack overflow even more eagerly in this case?

dwickern · Accepted Answer · 2015-12-30 02:37:41Z

1

An easy solution is use the packrat parser:

object ExprParser extends JavaTokenParsers with PackratParsers {
  lazy val name: PackratParser[_] = "a" ~ rep("a" | "1") | function_call
  lazy val function_call: PackratParser[_] = name ~ "(" ~> name <~ ")"
}

Output:

scala> ExprParser.parseAll(ExprParser.function_call, "aaa(1)")
res0: ExprParser.ParseResult[Any] =
[1.5] failure: Base Failure

aaa(1)
    ^

answered Dec 30, 2015 at 2:37

dwickern

3,5291 gold badge16 silver badges21 bronze badges

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

1 Comment

D. Ben Knoble Over a year ago

why does this suddenly fix the issue?

Collectives™ on Stack Overflow

Stack overflow when using parser combinators

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related