compiler-construction - 构造具有替换、分解和左递归删除的 LL(1) 文法

Question

使用任何技术（替换、因式分解、左递归删除），构造一个接受与 G 相同语言的 LL(1) 文法。

G over Σ = {0, 1, 2}:
    S → Y | 1X
    X → 1X | 0
    Y → Y0 | 1X1 | 2X2

到目前为止，我这样做了：

X 是左递归的，所以：

X -> 1F | 0F
F -> 1F | e

我还需要做什么来构造一个 LL(1)，我可以考虑 Y 吗？

Answer 1

首先，X 不是左递归的，因为它的 RHS 不是以 X 开头的。相反，它是尾递归的，没关系。然而 Y -> Y0 告诉你 Y 是左递归的。在这种情况下，您可以执行以下操作：

S -> Y | 1X
X -> 1X | 0
Y -> 1X1F | 2X2F
F -> 0F | e

您可能还想将和 epsilon 规则添加到 X 以及使其

X -> 1X | 0 | e

只是为了确保你永远不会得到无限的句子。