JavaCC left recursion parsing question 关于分解语法的合法性

Question

我正在尝试在 javacc 上进行编译，但我不确定在删除左递归时以下内容是否合法：

A = B AP APP
      | C AP APP

AP = A AP | {}

APP = (D AP) APP | {}

Answer 1

我假设 B、C 和 D 是终端。我要再添加一个非终结符

START --> A <EOF>

A --> <B> AP APP
     | <C> AP APP

AP --> A AP | {}

APP --> <D> AP APP | {}

第一个选择显然可以通过向前看的方式来解决。对于第二个选择，我们需要 A AP 的第一组与 AP 的后续组不相交；前者是{<B>, <C>}，后者是{<EOF>,<D>}。对于第三种选择，我们需要<D>不在APP的后续集合中，即{<EOF>}。

我们现在知道语法是 LL(1)，所以它应该适用于 JavaCC。

注意：确定语法是否适用于 JavaCC 有点复杂，因为 JavaCC 不会完全按照理论所说的那样计算跟随集，而且因为 JavaCC 有很多机制允许它使用非 LL (1)语法。但通常如果你的语法是 LL(1)，JavaCC 会很好地处理它。此外，如果 JavaCC 无法运行，它会发出警告消息。

JavaCC left recursion parsing question about legality of breaking down a grammar