如何在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，并且基本上无限地进行。我们可以通过将num放在div之前来解决这个问题，正如上面的评论中所建议的那样：

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)