当前位置: 动力学知识库 > 问答 > 编程问答 >

parsing - scala parser combinator stackoverflow recursion

问题描述:

The following code example crashes due to stack overflow when parsing an expression deeply nested in brackets.

Parser combinators are part of the standard library. Is there a way of making use of the library avoiding that?

(I'm not asking for the reason of why it crashes rather for the right way to deal with the standard library.)

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

}

}

网友答案:

I'm not sure how you would deal with it with scala parser combinators. My first thought was trampolining[1] - but a quick google search seems to say that the default library doesn't support this. Hence I think the main way around this would be to use -Xss which is less than ideal.

However https://github.com/djspiewak/gll-combinators supports trampolining, and it seems like it has a similar API to the standard library.

分享给朋友:
您可能感兴趣的文章:
随机阅读: