3

考虑

import util.parsing.combinator._
object TreeParser extends JavaTokenParsers {

    lazy val expr: Parser[String] = decimalNumber | sum
                                                  //> expr: => TreeParser.Parser[String]
    lazy val sum: Parser[String] = expr ~ "+" ~ expr ^^ {case a ~ plus ~ b => s"($a)+($b)"}
                                                  //> sum: => TreeParser.Parser[String]
    println(parseAll(expr, "1 + 1"))                       //> TreeParser.ParseResult[String] = [1.3] failure: string matching regex 
                                              //| `\z' expected but `+' found
}

与 fastparse 相同的故事

import fastparse.all._
val expr: P[Any] = P("1" | sum)
val sum: P[Any] = expr ~ "+" ~ expr
val top = expr ~ End
println(top.parse("1+1")) // Failure(End:1:2 ..."+1")

解析器很高兴发现采用第一个文字是一个坏主意，但不要试图回退到求和生产。为什么？

我知道解析器采用第一个可以成功吃掉输入字符串的一部分并退出的分支。这里，表达式的“1”匹配第一个输入字符，解析完成。为了获取更多，我们需要将 sum 设为第一个选择。然而，愚蠢至极

惰性 val expr: Parser[String] = sum | “1”

以堆栈溢出结束。因此，图书馆作者从另一面接近它

val sum: P[Any] = P( num ~ ("+".! ~/ num).rep )
val top: P[Any]   = P( sum ~ End )

在这里，我们从终端开始求和，这很好，但这种语法更冗长，此外，它产生一个终端，然后是一个列表，这对于一个归约运算符很有用，比如 sum，但很难映射到一个系列二元运算符。

如果您的语言定义了允许二元运算符的表达式怎么办？您想匹配每个出现的expr op expr并将其映射到相应的树节点

expr ~ "op" ~ expr ^^ {case a ~ _ ~ b => BinOp(a,b)"}

你是怎样做的？简而言之，我想要一个贪婪的解析器，它会消耗整个字符串。这就是我所说的“贪婪”而不是贪婪的算法，它跳进第一辆马车并最终陷入死胡同。

4

2 回答 2

2

正如我在这里发现的那样，我们需要|用秘密替换替代运算符|||

//lazy val expr: Parser[String] = decimalNumber | sum
lazy val backtrackGreedy: Parser[String] =  decimalNumber ||| sum

lazy val sum: Parser[String] = decimalNumber ~ "+" ~ backtrackGreedy ^^ {case a ~ plus ~ b => s"($a)+($b)"}

println(parseAll(backtrackGreedy, "1 + 1")) // [1.6] parsed: (1)+(1)

选项的顺序与此运算符无关。要停止堆栈溢出，我们需要消除左递归sum = expr + expr=> sum = number + expr。

另一个答案说我们需要规范化，而不是

  def foo = "foo" | "fo"
  def obar = "obar"

  def foobar = foo ~ obar

我们需要使用

def workingFooBar = ("foo" ~ obar) | ("fo" ~ obar)

但第一个解决方案更引人注目。

于 2016-01-13T23:21:44.780 回答
1

解析器会回溯。试一试val expr: P[String] = P(("1" | "1" ~ "+" ~ "1").!)，expr.parse("1+1")例如。

问题出在你的语法上。expr解析1，根据您的定义，它是一个成功的解析。然后sum失败了，现在你想把expr发生的事情归咎于尽职尽责的人吗？

有很多关于如何处理二元运算符的例子。比如这里的第一个例子：http: //lihaoyi.github.io/fastparse/

于 2015-11-25T14:48:53.107 回答