语法中的间接递归

Question

我正在尝试从以下语法中删除间接递归：

F -> P X
X -> R C
R -> C R | I R | epsilon

所有大写字母都是非终结符，我刚刚停止制作，因为它们不重要。

在此之后，您可以看到我将得到类似 F -> P (C | I)* C 的内容，这导致我的递归下降解析器出现问题。

任何有效的表达式都必须以 C 结尾，但是这个最终的 C 总是被重复使用 R 产生式所消耗，没有留下任何标记用于 X -> R C 产生式的最终 C。

以下面的token表达式为例："P C I C"

• 我们使用 F -> P X 产生式删除第一个 P 留下 "C I C"
• 然后 X -> R C -> C R C 这样我们就可以消耗 C 留下 "I C"
• 然后 R C -> I R C 所以我们可以消耗 I 离开 "C"

现在我们遇到了问题。递归体面的解析器将简单地选择继续扩展 R，如下所示：

• R C -> C R C 所以我们消耗了最后一个字符 C，没有留下剩余的标记！

此时，尽管输入有效，我的程序仍会出错，因为最终的 R C -> C（使用 epsilon 产生式）并且没有剩余的 C 可以匹配！

我认为我需要做的就是以某种方式巧妙地重新排列语法以消除这种歧义。非常感谢任何帮助！

Answer 1

您可以将P (C | I)<sup>*</sup> C重写为P I<sup>*</sup> C<sup>+</sup> (I<sup>+</sup> C<sup>+</sup>)<sup>*</sup>，这很容易实现为递归下降解析器。如果你将它写成右递归 BNF 语法，你最终会得到不正确的关联性，但通常你会使用上面的扩展 BNF 编写带循环的递归下降解析器。 [注1]

实际上，一旦你解析了 P，你最终会得到这样的结果：

do {
  while (try_parse(I)) {}
  parse(C);
  while (try_parse(C)) {}
} while (try_parse(I));

---

备注

1. 或者，至少，如果我再写递归下降解析器的话，我会的。作为左递归语法，这是更直接的，它是 LALR(1)，因此您可以使用 bison 生成解析器。