2

我从几个来源了解到 LL(1) 语法是：

  1. 毫不含糊，
  2. 不是左递归的，
  3. 并且，确定性（左分解）。

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

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

4

2 回答 2

4

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

我们首先编写 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)。∎</p>

命题 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)。∎</p>

命题 3： 歧义文法不是 LL(1)。

证明：

虽然上述证明是我的，但这个不是，它是Kevin A. Naudé的，我从他的回答中得到，链接如下：

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

于 2019-01-06T19:19:21.360 回答
1

这些问题的答案（它们对于任何有限 k 的 LL(k) 都有效）与解析堆栈在 LL 解析器中的工作方式有关。

在语法中一个非终结符的开头处，解析器必须通过仅向前查看 k（LL(1) 中为 1）个案例标记来确定是否将特定规则推入堆栈或使用其他规则解析文本。所以，让我们看看这些案例中的每一个，看看它如何影响这个决定。

  1. 左递归。有两种左递归情况。

    一个。左递归在递归之后没有标记。类似的规则：

非长期的：非长期的；

这样的规则没有任何效果，无论你递归多少都不会改变你正在解析的内容。

b. The left-recursion has tokens in it after the recursion.  A rules something like:

非术语：非术语“X”；

在此规则中，您需要将非术语规则推入堆栈，其 X 数与非术语后的 X 数相同。只有 k 个前瞻标记，您无法确定有多少个 X。如果你猜测并且猜测太小，你最终会留下 X，对于任何猜测，语言中都会有一个案例，其中 X 标记的数量超过了那么多。如果你猜测并且你猜测的太大，你最终会在堆栈上得到 extern nonterm 规则。你不能删除它们。无论哪种情况，你都错了。

  1. 非确定性的。非确定性文法具有与左递归文法相同的特征。你是否应该推动是不确定的。回文语言是典型的非确定性例子，但不是唯一的例子。在回文语言中，您不知道是应该将另一个非终结符推入堆栈还是使用您看到的令牌来帮助您从堆栈中弹出。如果您做出错误的选择，您将再次错误解析输入。

  2. 模糊的。同样的问题是相似的。在这种情况下，有两种可能的解析。一个推送一个非终端并成功解析输入，另一个解析没有（可能现在或稍后在解析中推送另一个非终端）。任何一个都会产生正确的解析。现在，在模棱两可的情况下，推送非终结符不一定会导致解析错误，您只需选择一个潜在的解析而忽略另一个。如果您的语义要求选择另一个解析，那么问题将在稍后出现。请注意，当然，最模棱两可的语法也是非确定性的。

现在，如果您查看这些情况，您会看到，如果您能以某种方式将非终结符推入堆栈，而不会将非终结符推入堆栈，则可以使用语法解析输入。并且，在模棱两可的情况下，生成一组与输入匹配的解析。有一些技术可以做到这一点，我相信它们被认为是 GLL（广义 LL）——与 LR 解析器生成器等效的技术称为 GLR。结果输出通常被认为是“解析森林”（或者有时是解析 dag，有向无环图）。

[注意：我首先在 Quora 上看到了上述问题，这个答案是从那里复制的。]

于 2019-01-07T13:09:49.370 回答