将文法转换为LL(1)，判断是否为LL(1)

Question

我不太明白如何判断语法是不是LL(1)。我学到了以下语法：

S → Y | 1X 
X → 1X | 0
Y → Y0|1X1|2X2

我声明这个语法不是LL(1)，因为它的Y0是左递归的。

因此，我想出了以下解决方案：

S → Y | 1X
X → 1X | 0
Y → 1X1F | 2X2F
F → ε | 0F

但我仍然不确定这是否正确。我仍然认为我一定是遗漏了一些规则，比如某种因式分解。我必须把1X和2X作为不同的变量吗？

提前感谢您的帮助。我还想知道是否有更简单的方法来确定语法是否为LL(1)我遇到了很多“第一”和“跟随”表，但实际上我自己还没有成功地构建一个。

Answer 1

如果因数我们的1X，那么我得到以下结果：

S → Y | Z
X → Z | 0
Y → Z1F | 2X2F
F → ε | 0F
Z → 1X | ε

这意味着S→Y|Z，我认为这是不允许的。

Answer 2

LL(1)语法需要能够基于单个((1))先行标记来预测结果。但是，Y和1X都可以以1开头，因此不可能在给定第一个输入符号1的情况下预测是使用S→Y还是S→1X。因此，原始语法和转换后的语法都不是LL(1)。