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遞歸

回答

相關問題