Почему этот набор комбинаторов синтаксического анализатора переполняет стек? - PullRequest
Новая
       67

Почему этот набор комбинаторов синтаксического анализатора переполняет стек?

5 голосов
/ 13 марта 2019

TL; DR

Мои синтаксические анализаторы для спецификации грамматики EBNF переполняют стек.Зачем?Как это исправить?

Фон

Я пытаюсь определить синтаксический анализатор из библиотеки scala для синтаксиса EBNF .На самом деле, код строит AST грамматики, но я убрал эти биты и выделил вспомогательный метод для создания MVCE (ниже).

Проблема

Кодкак написано, при запуске дает переполнение стека (также ниже).Что я не могу понять, так это то, что она кажется переполненной пропускаемой частью анализа.Как мне решить эту ошибку?Было бы очень жаль, если синтаксический анализ синтаксиса EBNF невозможен - я намереваюсь разработать некоторые инструменты для него.

MVCE 

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

Трассировка ошибок

Полный журнал можетбыть найденным как Гист . 

[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

1 Ответ

1 голос
/ 14 марта 2019

Я смог решить свою проблему, удалив левую рекурсию с помощью методов, найденных в этом ответе .Ниже приведен рабочий код.

Мне пришлось тщательно подумать о преобразованиях: особенно alternation.+ ^^ { _.reduce(_ + _) } и sequence.+ ^^ { _.reduce(_ + _) } - преобразование этих данных обратно в генератор AST может быть нетривиальным (поскольку конструкторы для них требуют тольколевый и правый).Повторение также немного беспокоит меня, но без извлечения вспомогательной функции это было единственное, что нужно было сделать. 

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