Scala Parser Kombinator stackoverflow Rekursion

Question

Das folgende Codebeispiel stürzt aufgrund eines Stacküberlaufs ab, wenn ein tief geschachtelter Ausdruck geparst wird.

Parser-Kombinatoren sind Teil der Standardbibliothek. Gibt es eine Möglichkeit, die Bibliothek zu nutzen, ohne dass dies passiert?

(Ich frage nicht nach dem Grund für den Absturz, sondern nach dem richtigen Umgang mit der Standardbibliothek.)

parsing: ((((((((... 1 + 1 ...)))))))))

code:

import scala.util.parsing.combinator.syntactical.StandardTokenParsers

object ArithmeticParser1 extends StandardTokenParsers {   
  lexical.delimiters ++= List("(", ")", "+", "-", "*", "/")

  val reduceList: Int ~ List[String ~ Int] => Int = {
    case i ~ ps => (i /: ps)(reduce) 
  }

  def reduce(x: Int, r: String ~ Int) = (r: @unchecked) match {
    case "+" ~ y => x + y
    case "-" ~ y => x - y
    case "*" ~ y => x * y
    case "/" ~ y => x / y
  }

  def expr  : Parser[Int] = term ~ rep ("+" ~ term | "-" ~ term) ^^ reduceList
  def term  : Parser[Int] = factor ~ rep ("*" ~ factor | "/" ~ factor) ^^ reduceList
  def factor: Parser[Int] = "(" ~> expr <~ ")" | numericLit ^^ (_.toInt)

  def main(args: Array[String]) {
    val s = scala.io.Source.fromFile(args(0)).mkString
    val tokens = new lexical.Scanner(s)
    println(s)
    println(phrase(expr)(tokens))
  }
}

Answer 1

Ich bin mir nicht sicher, wie du damit umgehen würdest mit Scala Parser Combinators. Mein erster Gedanke war Trampolinierung[1] - aber eine schnelle Google-Suche scheint zu besagen, dass die Standardbibliothek dies nicht unterstützt. Daher denke ich, dass der Hauptweg um dies zu umgehen wäre, -Xss zu verwenden, was weniger als ideal ist.

Allerdings unterstützt https://github.com/djspiewak/gll-combinators Trampolining, und es scheint, dass es eine ähnliche API wie die Standardbibliothek hat.