compiler-construction - LL(1) 不能有歧义

Question

如何证明没有 LL(1) 文法可以是二义性的？

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

Answer 1

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

(旁注:很遗憾 SO 不支持数学，例如在 LaTeX 中。)

证明

设 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和 A -> C .
也就是说，存在一些终端 TZ 字符串，它允许不同的解析树进行多次推导。

假设左推导达到 S ->* TAY ->* TZ .下一步可能是 TAY -> TBY , 或 TAY -> TCY .
因此，如果同时 BY ->* Z，则语言是模棱两可的。和 CY ->* Z .
(请注意，由于 A 是任意非终结符，如果不存在这种情况，则该语言是无歧义的。)

情况 1:Z = 空

根据 LL(1) 文法的规则 1，B 和 C 中最多有一个可以派生出空(非歧义案例)。

情况 2:Z 非空，且 B 和 C 均不导出为空

根据 LL(1) 文法的规则 2，B 和 C 中最多有一个可以允许进一步推导，因为 Z 的前导终结符不能同时在 First(B) 中。和 First(C) (非歧义的情况)。

情况 3:Z 非空，或者 MaybeEmpty(B)或 MaybeEmpty(C)
注意 LL(1) 文法的规则 1，B 和 C 不能都导出为空。因此假设 MaybeEmpty(C)是真的。

这给出了两个子案例。

案例 3a: CY -> Y ;和案例 3b: CY ->* DY ，其中 D 不为空。

在 3a 中，我们必须在 BY ->* Z 之间进行选择和 CY -> Y ->* Z ，但请注意 First(Y) subset-of Follow(A) .自 Follow(A)不相交 First(B) ，只能进行一个推导(非歧义)。

在 3b 中，我们必须在 BY ->* Z 之间进行选择和 CY ->* DY ->* Z ，但请注意 First(D) subset-of First(C) .自 First(C)不相交 First(B) ，只能进行一个推导(非歧义)。

因此，在每种情况下，推导只能通过可用的产生式之一进行扩展。因此，语法没有歧义。