如何避免 Fastparse 中的左递归无限循环？

Question

我有一个在 Scala Packrat 解析器组合器中运行良好的解析器。我想尝试使用 Fastparse 库更快一些。但是，它无法处理左递归无限循环。有什么标准的方法可以解决这个问题吗？

sealed trait Expr

case class Num(value: java.lang.Number) extends Expr

case class Div(a: Expr, b: Expr) extends Expr

def num[_: P] = P(CharIn("0-9").rep(1).!).map(n => Num(n.toInt))

def div[_: P] = P(expr ~ "/" ~ expr).map(Div.tupled)

def expr[_: P]: P[Expr] = P(div | num)

Answer 1

我对 Fastparse 了解不多，但我会尽量回答你的问题。现在，您的语法看起来像这样：

expr ::= div | num
div  ::= expr "/" expr
num  ::= 0 | 1 | ...

所以如果你想将1/2解析为一个表达式，它会首先尝试匹配div。为此，它会尝试再次匹配 expr，并且基本上会无限继续下去。我们可以通过在 div 之前放置 num 来解决这个问题，如上面评论中所建议的：

expr ::= num | div
Or
def expr[_: P]: P[Expr] = P(num | div)

成功！或者是吗？仔细查看结果后，您会发现它不是 Div(Num(1), Num(2))，而只是 Num(1)。要解决此问题，请使用 End

def expr[_: P]: P[Expr] = P((num | div) ~ End)

现在它失败了，说它找到了“/2”。它首先成功匹配 num，因此没有理由认为第一个数字是除法运算的一部分。因此，毕竟我们必须在 num 之前使用 div，以确保使用更大的模式，但需要做一些事情来避免递归。我们可以这样重构它：

expr ::= div
div  ::= num ("/" num)*

div 不仅匹配除法，它还可以匹配单个数字，但它会尽可能匹配除法。在 Scala 中，这将是：

def div[_: P] = P(num ~ ("/" ~/ num).rep).map {
  case (a, ops) => ops.foldLeft(a: Expr){ case (a, b) => Div(a, b) }
}

def expr[_: P]: P[Expr] = P(div ~ End)

这样，我们可以匹配“1/2”、“1/2/3”、“1/2/3/4”等

parse("1/2/3/4", expr(_)) 的输出是 Parsed.Success(Div(Div(Div(Num(1),Num(2)),Num(3)),Num(4)), 7)

如何避免 Fastparse 中的左递归无限循环？

How to avoid left-recursion infinite loops in Fastparse?

scala

parser-combinators

left-recursion

packrat

fastparse