3

我有一个在 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)
4

1 回答 1

3

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

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

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

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

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

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

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

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)

于 2020-07-22T15:33:01.610 回答