scala解析器组合器stackoverflow递归

下面的代码示例在解析深度嵌套在括号中的表达式时由于堆栈溢出而崩溃。scala解析器组合器stackoverflow递归

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

（我不是要求的，为什么它崩溃，而对于处理标准库的正确方法的原因。）

解析：（（（（（（（（... 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)) 
    } 
}

来源

2012-10-13 buerger

我无法重现崩溃。多少级别的嵌套括号使程序引发异常？ – paradigmatic

我也试过了，并且（在默认的jvm堆栈大小的情况下）在我遇到堆栈溢出之前必须达到3500级别（=括号对数）！这为真实世界的表达式留下了相当大的空间...... @buerger：我有兴趣知道你是否有一个更合理的堆栈溢出，否则哪些用例需要嵌套。 –

改进解析器库的一种方法是使其使用显式堆栈。任何级别的嵌套都是合理的。但是没有任何修改这个库的假设方式是合理的。 – buerger

我不知道你将如何处理它与Scala的解析器组合。我的第一个想法是蹦床[1] - 但快速谷歌搜索似乎说，默认库不支持这一点。因此，我认为主要的解决办法是使用-Xss这并不理想。

但是https://github.com/djspiewak/gll-combinators支持蹦床，它好像有一个类似于标准库的API。

来源

2012-10-13 21:45:50

scala解析器组合器stackoverflow递归

回答

相关问题