Fastparse 不会回溯

Question

编辑（概括问题）：

我想解析语法，其中

<prefix> ::= [a-z]*
<middle> ::= xxx
<suffix> ::= b+
<grammar> ::= <prefix><middle><suffix>

我希望（例如）以下单词通过：aaaaxxxbb、axxxaaxxxbbb、xxxxxxbb

原文post:

我希望下面的解析器回溯并最终找到解决方案：

val before = P(AnyChar.rep.!)
val content = P("xxx".!)
val after = P("b".rep.!)
val all = P(before ~ content ~ after ~ End)
def test() = {
  val r = all.parse("aaaaxxxbbb")
  println(r)
}

相反，before 部分贪婪地解析了所有文本，解析器在没有回溯的情况下失败了。

我是不是漏掉了什么？

Answer 1

最终我解决了这个问题。

这是合理的，解析器不会在正则表达式中回溯，所以我认为我应该将 AnyChar.rep 部分重写为递归规则，如下所示：

val before: P[Any] = P(AnyChar | (AnyChar ~ before))

但这还不够，fastparse 似乎仍然没有回溯。

我偶然发现了 this question about parsing ambiguous grammar。所以我尝试使用 GLL combinators 而不是 Fastparse，这让它起作用了。

object TestParser1 extends Parsers with RegexParsers {

  lazy val before: Parser[String] = (".".r | (".".r ~ before)) ^^ {
    case a ~ b => a.toString + b.toString
    case x => x.toString
  }
  lazy val content: Parser[String] = "xxx"
  lazy val after: Parser[String] = "b+".r
  lazy val all: Parser[String] = before ~ content ~ after ^^ {
    case (b, c, a) => s"$b $c $a"
  }

  def test() = {
    val r = all("aaaaxxxbbb")
    r.toList foreach println
  }

}

Fastparse 不会回溯

Fastparse doesn't backtrack

scala

parsing

backtracking

fastparse