Scala解析器组合器:使用packratparsers获取stackoverflow

Question

由于这是我的第一篇文章,我想借此机会说:这是一个多么伟大的网站!

无论如何,对于这个问题:

我有点像Scala新手,我正在尝试用Scala中的解析器组合器解决数据提取和解析问题,我得到了java.lang.StackOverflowError异常.

我的真实世界的例子太大了,所以我没有重复使用来自另一个SO问题的代码同样的问题.虽然代码略有修改.我尝试使用PackratParsers解决问题,但没有成功.

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

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

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

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

  def main(args: Array[String]) {
    val times = 500
    val s = "(" * times + "1 + 1" + ")" * times
    val tokens = new PackratReader(new lexical.Scanner(s))
    println(phrase(expr)(tokens))
  }
}

我已经混合了PackratParsers的特性,将defs改为lazy vals而我正在使用PackratReader.我在这里误解了什么？阅读Daniel C. Sobrals回答SO问题的评论在使用Scala的解析器组合器时,如何忽略不匹配的前一文本？似乎PackratParsers应该做的伎俩.

参考:PackratParsers论文

Answer 1

问题

问题是你确实填满了堆栈.您的表达式包含500个左括号,"1 + 1",然后是500个右括号.在语法方面,你有500个术语"因子"相互嵌套,然后在一个术语"expr"中.

对于(嵌套)术语的每个开始,解析器必须在堆栈上推送一些东西(在这种情况下是函数调用).嵌套术语完成后,解析后会从堆栈中弹出这个东西(在这种情况下:函数返回).如果在最后一个令牌之后,堆栈是空的,如果堆栈永远不会消极(弹出太多),那么你的术语就会很好(在你的情况下:括号是平衡的).

简单来说:解析器使用堆栈来计算括号是否平衡.

您正在使用多种工具来加快解析速度.这些工具都不能帮助堆栈消耗.

你的助手:

使用packrat解析器

packrat解析器缓存已解析的部分,因此不需要再次解析它们.当你的语法有许多常见部分的替代方案时,这可以带来很好的加速.它对你的情况没有帮助,因为你没有其他选择.它对堆栈消耗没有帮助.

省略部分结果

您使用 <~ 和 ~> 省略已解析结果的某些部分.但这只会助长一个学期.当调用相应的规则时,解析器仍然必须在堆栈上推送一些东西.

使用令牌

在解析之前,您将分解标记中的输入流.这通常会加快解析速度,因为令牌化(非递归,通常是正则表达式)比解析(递归)便宜得多.但在你的情况下,问题在于嵌套术语的深度(递归问题).所以你的压力完全在解析部分,因此耗尽了堆栈.令牌化无助于解决该问题.

解

我认为你不能轻易解决这个问题.解析器必须使用某种堆栈数据结构.通常,内置堆栈用于性能问题.您必须在堆上使用一些堆栈结构.这通常会慢很多,并且与Scala Parser Combinators不兼容.

您可以尝试在延续传递样式(CPS)中包含"因子" .然后将在堆上跟踪调用,而不是在堆栈上.

开箱即用,没有简单的解决方案.