Scala解析器组合器stackoverflow递归问题

Question

以下代码示例由于在解析深度嵌套的括号中出现堆栈溢出而崩溃。

解析组合器是标准库的一部分。有没有一种方法可以利用该库避免这种情况？

（我不是在询问为什么它会崩溃，而是询问处理标准库的正确方式。）

解析： ((((((((... 1 + 1 ...)))))))))

代码：

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

- buerger

---

我无法重现崩溃。程序有多少层嵌套括号会导致异常抛出？ - paradigmatic

我也进行了尝试，并且（使用默认的 JVM 堆栈大小）不得不升到 3500 级（ = 括号对数），才遇到堆栈溢出！这为实际表达式留下了相当大的空间... @buerger：如果您在更合理的级别遇到堆栈溢出，或者其他情况需要那么多嵌套，请让我知道。 - Régis Jean-Gilles

改进解析器库的一种方法是使用显式堆栈。任何嵌套级别都是合理的，但并非所有修改库的假设方式都是合理的。 - buerger

理论上，解析的表达式的复杂度是没有限制的。但在实践中，计算机有着各种限制，无论是时间（某一时刻，某些东西需要计算的时间太长，以至于没有任何实际用途）还是内存（这肯定是有界的）。要明确一点，如果您尝试让scala编译器编译嵌套级别为3500的表达式 ((((((((... 1 + 1 ...)))))))))，它本身也会栈溢出。不妨试试。 - Régis Jean-Gilles

使用显式堆栈肯定会极大地帮助解决问题，但是在某个时刻，您的堆栈将占用整个内存，从而遇到瓶颈。我知道我可能看起来很学究，但我想说的是，您必须有限制。因此，唯一真正的问题是：3500级别是否是不可接受的限制？ - Régis Jean-Gilles

Answer 1

我不确定如何使用Scala解析器组合处理它。我的第一个想法是使用trampolining[1]，但是快速的谷歌搜索似乎表明默认库不支持这个功能。因此，我认为解决这个问题的主要方法是使用-Xss，但这并不是最理想的。

然而，https://github.com/djspiewak/gll-combinators 支持trampolining，并且它似乎具有与标准库类似的API。

- Ivan Meredith