error-handling - 为什么解析器组合器在发生故障的情况下不回退？

Question

我在解析器组合器上浏览了Artima guide，它说我们需要将failure(msg)附加到语法规则中，以使错误报告对用户有意义

def value: Parser[Any] =
    obj | stringLit | num | "true" | "false" | failure("illegal start of value")

这破坏了我对这些解析器中使用的递归机制的理解。一方面，Artima指南有道理地说，如果所有制作均失败，则解析器将到达返回给用户的 failure("illegal start of value")。但是，一旦我们理解语法不是值选择的列表而是树，它就没有意义了。也就是说，值解析器是在输入端检测到值时调用的节点。这意味着同时也是父级的调用解析器将检测到值解析失败，并进行值同级替代。假设所有替代值(value)的方法也都失败了。然后，Grandparser将尝试其替代方案。依次失败，该过程向上展开，直到起始符号解析器失败。那么，错误消息将是什么？似乎报告了最高解析器的最后一个选择错误。

为了弄清楚谁是对的，我创建了一个演示，其中 program是最高的(起始符号)解析器

import scala.util.parsing.combinator._

object ExprParserTest extends App with JavaTokenParsers {

    // Grammar
    val declaration = wholeNumber ~ "to" ~ wholeNumber | ident | failure("declaration not found")
    val term = wholeNumber | ident ; lazy val expr: Parser[_] = term ~ rep ("+" ~ expr)
    lazy val statement: Parser[_] = ident ~ " = " ~ expr | "if" ~ expr ~ "then" ~ rep(statement) ~ "else" ~ rep(statement)
    val program  = rep(declaration) ~ rep(statement)

    // Test
    println(parseAll(program, "1 to 2")) // OK
    println(parseAll(program, "1 to '2")) // failure, regex `-?\d+' expected but `'' found at '2
    println(parseAll(program, "abc")) // OK


}

由于额外的 1 to '2勾号，它无法使用 '失败。是的，它似乎卡在了 program -> declaration -> num "to" num规则中，甚至没有尝试使用 ident和 failure("declaration not found")替代方法!出于相同的原因，我也不回溯到这些语句。因此，我的猜测和Artima指南对于解析器组合器的实际工作似乎都不正确。我想知道:解析器组合器中的规则检测，回溯和错误报告背后的真正逻辑是什么？为什么错误消息表明没有回溯到 declaration -> ident | failure()，也没有 statements发生？ Artima指南建议，如果未按我们所看到或忽略的方式到达failure()的末尾，那到底有什么意义？

解析器组合器不只是普通的哑PEG吗？它 behaves like predictive parser。我以为是PEG，因此，起始符号解析器应返回所有失败的分支，并想知道实际解析器为何/如何设法选择最合适的失败。

Answer 1

许多解析器组合器会回溯，除非它们处于“或”块中。作为速度优化，他们将致力于第一个成功的“或”项目，而不回溯。因此1)尽量避免使用'|'尽可能在语法上，以及2)如果使用“|”是不可避免的，请首先将最长或最不可能匹配的项目放在第一位。