My parser-combinators for EBNF grammar specs overflows the stack. Why? How do I fix it?
I'm attempting to define a parser via combinators from the scala library for an EBNF syntax. In actuality, the code builds an AST of the grammar, but I've stripped out those bits and inlined a utility method in order to produce an MVCE (below).
The code as written, when run, gives a stack overflow (also below). What I cannot get my head around is that it seems to overflow in the skip whitespace part of the parsing. How do I resolve this error? It would really be unfortunate if parsing EBNF syntax isn't possible—I intend to develop some tooling for it.
package org.benknoble.ebnf
import scala.util.parsing.combinator._
class EbnfParserSimple extends RegexParsers {
def nonterminal: Parser[String] = """<[^>]+>""".r
def goesTo: Parser[String] = """::="""
def epsilon: Parser[String] = "ε"
def terminal: Parser[String] = "\"[^\"]+\"".r
def sequence: Parser[String] =
exp ~ exp ^^ { case left ~ right => left + right }
def alternation: Parser[String] =
exp ~ "|" ~ exp ^^ { case left ~ _ ~ right => left + "|" + right }
def opt: Parser[String] =
"[" ~ exp ~ "]" ^^ { case lb ~ e ~ rb => lb + e + rb }
def repetition: Parser[String] =
"{" ~ exp ~ "}" ^^ { case lb ~ e ~ rb => lb + e + rb }
def group: Parser[String] =
"(" ~ exp ~ ")" ^^ { case lb ~ e ~ rb => lb + e + rb }
def exp: Parser[String] =
(epsilon
| terminal
| nonterminal
| sequence
| alternation
| opt
| repetition
| group)
def rule: Parser[String] = nonterminal ~ goesTo ~ exp ~ ";" ^^ {
case nt ~ delim ~ e ~ semi => nt + delim + e + semi
}
def join[A](sep: String, list: Seq[A]): String = list match {
case h :: t => h.toString() + t.foldLeft("")(_.toString() + sep + _.toString())
case Nil => ""
}
def root: Parser[String] = phrase(
rep(rule) ^^ {
case rules =>
val joined = join(" ;\n", rules)
if (joined.isEmpty)
joined
else
joined + " ;"
}
)
}
object Main extends App {
val parser = new EbnfParserSimple()
val grammar = """<A> ::= ["a"|ε]"c" ; """
// <B> ::= <A>"b" ;
// <C> ::= {<B>}"$" ;
// <D> ::= "a""b""d" ;
// <E> ::= ("a"|"b")"c" ;
// """
val rule = parser.root
println(parser.parse(rule, grammar))
}
Full log can be found as a Gist.
[info] Loading project definition from /Users/Knoble/loner/project
[info] Loading settings for project root from build.sbt ...
[info] Set current project to loner (in build file:/Users/Knoble/loner/)
[info] Set current project to ebnf (in build file:/Users/Knoble/loner/)
[info] Running org.benknoble.ebnf.Main
[error] (run-main-0) java.lang.StackOverflowError
[error] java.lang.StackOverflowError
[error] at java.util.regex.Pattern.compile(Pattern.java:1673)
[error] at java.util.regex.Pattern.<init>(Pattern.java:1351)
[error] at java.util.regex.Pattern.compile(Pattern.java:1028)
[error] at scala.util.matching.Regex.<init>(Regex.scala:226)
[error] at scala.collection.immutable.StringLike.r(StringLike.scala:284)
[error] at scala.collection.immutable.StringLike.r$(StringLike.scala:284)
[error] at scala.collection.immutable.StringOps.r(StringOps.scala:33)
[error] at scala.collection.immutable.StringLike.r(StringLike.scala:273)
[error] at scala.collection.immutable.StringLike.r$(StringLike.scala:273)
[error] at scala.collection.immutable.StringOps.r(StringOps.scala:33)
[error] at org.benknoble.ebnf.EbnfParserSimple.terminal(EbnfParser_strings.scala:13)
[error] at org.benknoble.ebnf.EbnfParserSimple.$anonfun$exp$1(EbnfParser_strings.scala:32)
[error] at scala.util.parsing.combinator.Parsers$Parser.p$lzycompute$1(Parsers.scala:253)
[error] at scala.util.parsing.combinator.Parsers$Parser.p$4(Parsers.scala:253)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$2(Parsers.scala:254)
[error] at scala.util.parsing.combinator.Parsers$Failure.append(Parsers.scala:202)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$1(Parsers.scala:254)
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$1(Parsers.scala:254)
[...]
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$1(Parsers.scala:254)
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$1(Parsers.scala:254)
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$1(Parsers.scala:254)
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$append$1(Parsers.scala:254)
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] at scala.util.parsing.combinator.Parsers$Parser.$anonfun$flatMap$1(Parsers.scala:239)
[error] at scala.util.parsing.combinator.Parsers$$anon$3.apply(Parsers.scala:222)
[error] Nonzero exit code: 1
[error] (Compile / run) Nonzero exit code: 1
[error] Total time: 1 s, completed 12 mars 2019 21:11:15
I ended up being able to solve my problem by removing the left recursion via techniques found in this answer. Below find the working code.
I had to think carefully about the transformations: particularly alternation.+ ^^ { _.reduce(_ + _) } and sequence.+ ^^ { _.reduce(_ + _) }—converting those back to the AST generator may be non-trivial (as the constructors for those require only a left and right). The repetition also bothers me a little, but without extracting a helper function it was the only thing to do.
package org.benknoble.ebnf
import scala.util.parsing.combinator._
class EbnfParserSimple extends RegexParsers {
def epsilon: Parser[String] = "ε"
def terminal: Parser[String] = "\"[^\"]+\"".r
def nonterminal: Parser[String] = """<[^>]+>""".r
def opt: Parser[String] =
"[" ~ exp ~ "]" ^^ { case lb ~ e ~ rb => lb + e + rb }
def repetition: Parser[String] =
"{" ~ exp ~ "}" ^^ { case lb ~ e ~ rb => lb + e + rb }
def group: Parser[String] =
"(" ~ exp ~ ")" ^^ { case lb ~ e ~ rb => lb + e + rb }
def alternation: Parser[String] =
chainl1(epsilon
| terminal
| nonterminal
| opt
| repetition
| group,
"|" ^^^ { (lb: String, rb: String) => lb + "|" + rb })
// exp ~ "|" ~ exp ^^ { case left ~ _ ~ right => left + "|" + right }
def sequence: Parser[String] =
alternation.+ ^^ { _.reduce(_ + _) }
// alternation ~ alternation ^^ { case lb ~ rb => lb + rb }
// exp ~ exp ^^ { case left ~ right => left + right }
def exp: Parser[String] =
sequence.+ ^^ { _.reduce(_ + _) }
def goesTo: Parser[String] = """::="""
def rule: Parser[String] = nonterminal ~ goesTo ~ exp ~ ";" ^^ {
case nt ~ delim ~ e ~ semi => nt + delim + e + semi
}
def join[A](sep: String, list: Seq[A]): String = list match {
case h :: t => h.toString() + t.foldLeft("")(_.toString() + sep + _.toString())
case Nil => ""
}
def root: Parser[String] = phrase(
rep(rule) ^^ {
case rules =>
val joined = join(" ;\n", rules)
if (joined.isEmpty)
joined
else
joined + " ;"
}
)
}
object Main extends App {
val parser = new EbnfParserSimple()
val grammar = """<A> ::= ["a"|ε]"c" ; """
// <B> ::= <A>"b" ;
// <C> ::= {<B>}"$" ;
// <D> ::= "a""b""d" ;
// <E> ::= ("a"|"b")"c" ;
// """
val rule = parser.root
println(parser.parse(rule, grammar))
}