parsing - 为什么左递归、非确定性或二义性文法不能是 LL(1)？

Question

我从多个来源了解到 LL(1) 语法是:

1. 明确，
2. 不是左递归，
3. 并且确定性(左因式分解)。

我无法完全理解的是为什么上述对于任何 LL(1) 语法都是正确的。我知道 LL(1) 解析表在某些单元格将有多个条目，但我真正想要得到的是以下命题的正式和一般(没有示例)证明:

左递归 (1)、非确定性 (2) 或二义性 (3) 语法不是 LL(1)。

Answer 1

我做了更多的研究，我想我已经找到了第一个问题和第二个问题的解决方案，至于第三个问题，我在这里找到了一个现有的解决方案，证明尝试写在下面:

我们首先编写 LL(1) 语法定义的三个规则:

对于每一个作品A -> α | β与 α ≠ β :

1. FIRST(α) ∩ FIRST(β) = Ø .
2. 如果β =>* ε然后FIRST(α) ∩ FOLLOW(A) = Ø (另外，如果 α =>* ε 那么 FIRST(β) ∩ FOLLOW(A) = Ø )。
3. 包括ε规则 (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α | β

这里出现了三种情况:

1. 如果 FIRST(β) ≠ {ε}那么:

       FIRST(β) ⊆ FIRST(S)

   =>  FIRST(β) ∩ FIRST(Sα) ≠ Ø

   这与定义的规则(1)相矛盾。

2. 如果 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é 提供的。这是我从他的回答中得到的，链接如下:

https://stackoverflow.com/a/18969767/6275103