LL(1) 不能有歧义

如何证明 LL(1) 文法不能是二义性的？

我知道什么是二义性语法，但无法证明上述定理/引理。

这是我的校样初稿。它可能需要一些微调，但我认为它涵盖了所有情况。我认为许多解决方案都是可能的。这是一个直接的证明。

（旁注：遗憾的是，SO 不支持数学，例如 LaTeX。）

Proof

设 T 和 N 为终结符号和非终结符号的集合。

让下面的内容保持不变

MaybeEmpty(s) = true <=> s ->* empty
First(s) = X containing all x for which there exists Y such that s ->* xY
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ

请注意，如果以下对每对产生式 A -> B 和 A -> C 成立，则语法为 LL(1)：

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C))
2. (First(B) intersect First(C)) = empty
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty

考虑一种语言为 LL(1)，A -> B and A -> C。 也就是说，存在一些终端 TZ 字符串，它允许通过不同的解析树进行多个推导。

假设左导数达到S ->* TAY ->* TZ。下一步可能是TAY -> TBY, or TAY -> TCY。 因此，如果两者都存在，则语言是有歧义的BY ->* Z and CY ->* Z。 （请注意，由于 A 是任意非终结符，因此如果不存在这种情况，则该语言是明确的。）

情况 1：Z = 空

根据 LL(1) 语法的规则 1，最多 B 和 C 之一可以导出空（非二义情况）。

情况 2：Z 非空，并且 B 和 C 都不派生为空

根据 LL(1) 语法的规则 2，最多 B 和 C 之一可以允许进一步推导，因为 Z 的前导终结符不能同时存在于两者中First(B) and First(C)（不含糊的情况）。

情况 3：Z 非空，并且MaybeEmpty(B) or MaybeEmpty(C)

请注意，根据 LL(1) 语法的规则 1，B 和 C 不能同时导出空值。因此假设MaybeEmpty(C)是真的。

这给出了两个子情况。

情况3a：CY -> Y;和情况 3b：CY ->* DY，其中 D 不为空。

在 3a 中我们必须选择BY ->* Z and CY -> Y ->* Z，但请注意First(Y) subset-of Follow(A)。自从Follow(A)不相交First(B)，只能进行一种推导（无二义性）。

在 3b 中我们必须选择BY ->* Z and CY ->* DY ->* Z，但请注意First(D) subset-of First(C)。自从First(C)不相交First(B)，只能进行一种推导（无二义性）。

因此，在每种情况下，推导只能通过可用的产生式之一来扩展。因此语法并无二义性。