为什么左递归、非确定性或歧义语法不能是 LL(1)？
Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?
我从多个来源了解到 LL(1) 文法是：
- 不含糊，
- 不是左递归的，
- 并且，确定性的（左因式分解）。
我不能完全理解的是为什么以上对于任何 LL(1) 语法都是正确的。我知道 LL(1) 解析 table 将在某些单元格中有多个条目，但我真正想要得到的是以下命题的正式和一般（没有示例）证明：
左递归 (1)、非确定性 (2) 或歧义 (3) 文法不是 LL(1)。
我做了更多的研究，我想我已经找到了第一个和第二个问题的解决方案，至于第三个问题，我在 SO 上找到了一个现有的解决方案，写了证明尝试下面：
我们首先写下 LL(1) 文法定义的三个规则：
对于每个作品A -> α | β α ≠ β:
FIRST(α) ∩ FIRST(β) = Ø.- If
β =>* ε then FIRST(α) ∩ FOLLOW(A) = Ø (also, if α =>* ε then FIRST(β) ∩ FOLLOW(A) = Ø).
- 在规则（1）中包含
ε意味着最多α和β之一可以导出ε.
命题 1: 非分解文法不是 LL(1)。
证明：
如果文法 G 是非因式分解的，则 G 中存在以下形式的产生式：
A -> ωα1 | ωα2 | ... | ωαn
（其中 αi 是 i-th α，不是符号 α 和 i），与 α1 ≠ α2 ≠ ... ≠ αn。然后我们可以很容易地证明：
∩(i=1,..,n) FIRST(ωαi) ≠ Ø
这与定义的规则 (1) 相矛盾，因此，非分解文法不是 LL(1)。 ∎
命题 2: 左递归文法不是 LL(1).
证明：
如果文法是左递归的，则 G 中存在以下形式的产生式：
S -> Sα | β
这里出现三种情况：
如果FIRST(β) ≠ {ε}那么：
FIRST(β) ⊆ FIRST(S)
=> FIRST(β) ∩ FIRST(Sα) ≠ Ø
这与定义的规则 (1) 相矛盾。
如果FIRST(β) = {ε}那么：
2.1。如果 ε ∈ FIRST(α) 那么：
ε ∈ FIRST(Sα)
这与定义的规则 (3) 相矛盾。
2.2。如果 ε ∉ FIRST(α) 那么：
FIRST(α) ⊆ FIRST(S)（因为β =>* ε）
=> FIRST(α) ⊆ FIRST(Sα) ........ (I)
我们还知道：
FIRST(α) ⊆ FOLLOW(S) ........ (II)
通过 (I) 和 (II)，我们有：
FIRST(Sα) ∩ FOLLOW(S) ≠ Ø
并且由于 β =>* ε，这与定义的规则 (2) 相矛盾。
在每种情况下我们都会得出矛盾，因此，左递归文法不是 LL(1)。 ∎
命题 3: 歧义语法不是 LL(1).
证明：
虽然上面的证明是我的，但这个不是，它是由 Kevin A. Naudé 我从下面链接的他的回答中得到的：
这些问题的答案（它们对任何有限 k 的 LL(k) 都有效）与解析堆栈在 LL 解析器中的工作方式有关。
在文法中一个非终结符的开头处，解析器必须先向前看 k（在 LL(1) 中为 1）个 case 标记，然后再决定是否推送到堆叠特定规则或使用其他规则解析文本。那么，让我们看看这些案例中的每一个，看看它如何影响该决定。
左递归。有两种左递归情况。
一个。左递归在递归之后没有标记。规则类似于：
nonterm: nonterm;
这样的规则没有效果，无论你递归多少都不会改变你正在解析的内容。
b. The left-recursion has tokens in it after the recursion. A rules something like:
nonterm: nonterm “X”;
在这个规则中，您需要将非术语规则压入堆栈，以获得与非术语后面一样多的 X。您无法仅使用 k 个前瞻标记来确定有多少个 X。如果您猜测并且猜测得太小，您最终会剩下 Xs，并且对于任何猜测，在语言中都会有超过那么多 X 标记的情况。如果您猜测并且猜测太大，您最终会在堆栈上使用 extern nonterm 规则。你不能删除它们。无论哪种情况，你都错了。
不确定。非确定性文法与左递归文法具有相同的特征。是否应该推送是不确定的。回文语言是典型的非确定性例子，但不是唯一的例子。在回文语言中，您不知道是应该将另一个非终结符压入堆栈还是使用您看到的标记来帮助您返回堆栈。如果您做出了错误的选择，您将再次错误地解析输入。
模棱两可。同样的问题是相似的。在这种情况下，有两种可能的解析。一个推送一个非终结符并成功解析输入，另一个解析不成功（可能现在或稍后在解析中推送另一个非终结符）。任何一个都会产生正确的解析。现在，在模棱两可的情况下，推送非终结符不一定会导致解析错误，您只需选择其中一个潜在的解析而忽略另一个。如果您的语义要求选择其他解析，则问题将在稍后出现。注意，当然，最有歧义的文法也是非确定性的。
现在，如果您查看这些情况，您会发现，如果您能以某种方式将非终结符压入和不压入堆栈，您就可以使用语法解析输入。并且，在模棱两可的情况下，生成一组与输入匹配的解析。有一些技术可以做到这一点，我相信它们被认为是 GLL（广义 LL）——与 LR 解析器生成器等效的技术称为 GLR。生成的输出通常被认为是“解析森林”（或者有时是解析 dag，有向无环图）。
[注：我首先在知乎上看到了上面的问题，这个答案是从那里复制的。]
我从多个来源了解到 LL(1) 文法是：
- 不含糊，
- 不是左递归的，
- 并且，确定性的（左因式分解）。
我不能完全理解的是为什么以上对于任何 LL(1) 语法都是正确的。我知道 LL(1) 解析 table 将在某些单元格中有多个条目，但我真正想要得到的是以下命题的正式和一般（没有示例）证明：
左递归 (1)、非确定性 (2) 或歧义 (3) 文法不是 LL(1)。
我做了更多的研究，我想我已经找到了第一个和第二个问题的解决方案，至于第三个问题，我在 SO 上找到了一个现有的解决方案，写了证明尝试下面：
我们首先写下 LL(1) 文法定义的三个规则：
对于每个作品A -> α | β α ≠ β:
FIRST(α) ∩ FIRST(β) = Ø.- If
β =>* εthenFIRST(α) ∩ FOLLOW(A) = Ø(also, ifα =>* εthenFIRST(β) ∩ FOLLOW(A) = Ø). - 在规则（1）中包含
ε意味着最多α和β之一可以导出ε.
命题 1: 非分解文法不是 LL(1)。
证明：
如果文法 G 是非因式分解的，则 G 中存在以下形式的产生式：
A -> ωα1 | ωα2 | ... | ωαn
（其中 αi 是 i-th α，不是符号 α 和 i），与 α1 ≠ α2 ≠ ... ≠ αn。然后我们可以很容易地证明：
∩(i=1,..,n) FIRST(ωαi) ≠ Ø
这与定义的规则 (1) 相矛盾，因此，非分解文法不是 LL(1)。 ∎
命题 2: 左递归文法不是 LL(1).
证明：
如果文法是左递归的，则 G 中存在以下形式的产生式：
S -> Sα | β
这里出现三种情况：
如果
FIRST(β) ≠ {ε}那么：FIRST(β) ⊆ FIRST(S)=> FIRST(β) ∩ FIRST(Sα) ≠ Ø这与定义的规则 (1) 相矛盾。
如果
FIRST(β) = {ε}那么：2.1。如果
ε ∈ FIRST(α)那么：ε ∈ FIRST(Sα)这与定义的规则 (3) 相矛盾。
2.2。如果
ε ∉ FIRST(α)那么：FIRST(α) ⊆ FIRST(S)（因为β =>* ε）=> FIRST(α) ⊆ FIRST(Sα) ........ (I)我们还知道：
FIRST(α) ⊆ FOLLOW(S) ........ (II)通过
(I)和(II)，我们有：FIRST(Sα) ∩ FOLLOW(S) ≠ Ø并且由于
β =>* ε，这与定义的规则 (2) 相矛盾。
在每种情况下我们都会得出矛盾，因此，左递归文法不是 LL(1)。 ∎
命题 3: 歧义语法不是 LL(1).
证明：
虽然上面的证明是我的，但这个不是，它是由 Kevin A. Naudé 我从下面链接的他的回答中得到的：
这些问题的答案（它们对任何有限 k 的 LL(k) 都有效）与解析堆栈在 LL 解析器中的工作方式有关。
在文法中一个非终结符的开头处，解析器必须先向前看 k（在 LL(1) 中为 1）个 case 标记，然后再决定是否推送到堆叠特定规则或使用其他规则解析文本。那么，让我们看看这些案例中的每一个，看看它如何影响该决定。
左递归。有两种左递归情况。
一个。左递归在递归之后没有标记。规则类似于：
nonterm: nonterm;
这样的规则没有效果，无论你递归多少都不会改变你正在解析的内容。
b. The left-recursion has tokens in it after the recursion. A rules something like:
nonterm: nonterm “X”;
在这个规则中，您需要将非术语规则压入堆栈，以获得与非术语后面一样多的 X。您无法仅使用 k 个前瞻标记来确定有多少个 X。如果您猜测并且猜测得太小，您最终会剩下 Xs，并且对于任何猜测，在语言中都会有超过那么多 X 标记的情况。如果您猜测并且猜测太大，您最终会在堆栈上使用 extern nonterm 规则。你不能删除它们。无论哪种情况，你都错了。
不确定。非确定性文法与左递归文法具有相同的特征。是否应该推送是不确定的。回文语言是典型的非确定性例子，但不是唯一的例子。在回文语言中，您不知道是应该将另一个非终结符压入堆栈还是使用您看到的标记来帮助您返回堆栈。如果您做出了错误的选择，您将再次错误地解析输入。
模棱两可。同样的问题是相似的。在这种情况下，有两种可能的解析。一个推送一个非终结符并成功解析输入，另一个解析不成功（可能现在或稍后在解析中推送另一个非终结符）。任何一个都会产生正确的解析。现在，在模棱两可的情况下，推送非终结符不一定会导致解析错误，您只需选择其中一个潜在的解析而忽略另一个。如果您的语义要求选择其他解析，则问题将在稍后出现。注意，当然，最有歧义的文法也是非确定性的。
现在，如果您查看这些情况，您会发现，如果您能以某种方式将非终结符压入和不压入堆栈，您就可以使用语法解析输入。并且，在模棱两可的情况下，生成一组与输入匹配的解析。有一些技术可以做到这一点，我相信它们被认为是 GLL（广义 LL）——与 LR 解析器生成器等效的技术称为 GLR。生成的输出通常被认为是“解析森林”（或者有时是解析 dag，有向无环图）。
[注：我首先在知乎上看到了上面的问题，这个答案是从那里复制的。]