scala - 为什么解析器组合器不回溯？

Question

考虑

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”

endы up with stack overflow .因此，库作者从另一个角度来处理它

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

在这里，我们从终端开始求和，这很好，但这种语法更冗长，而且，它会产生一个终端，后跟一个列表，这对于像求和这样的归约运算符很有用，但很难映射到一系列二元运算符。

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

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

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

Answer 1

因为我有 found here ，我们需要将 | 替代运算符替换为 secret |||

//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。

Another answer 表示我们需要归一化，即代替

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

  def foobar = foo ~ obar

我们需要使用

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

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