当前位置：文江博客话题详情

LL(1) 不能有歧义

发布于 2024-08-29 09:28:36 字数 62 浏览 2 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

活雷疯 2024-09-05 09:28:36

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

（旁注：遗憾的是 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 -> A -> A 都成立，则语法为 LL(1)。 B和A-> C：

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 ->是的;情况 3b：CY ->* DY，其中 D 不为空。

在 3a 中，我们必须在 BY ->* Z 和 CY ->* 之间进行选择。 Y ->* Z，但请注意 Follow(A) 的 First(Y) 子集。由于 Follow(A) 与 First(B) 不相交，因此只能进行一次推导（无二义性）。

在 3b 中，我们必须在 BY ->* Z 和 CY ->* DY ->* Z 之间进行选择，但请注意 First(D) 子集-第一个(C)。由于 First(C) 与 First(B) 不相交，因此只能进行一次推导（无二义性）。

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

Here's my first draft at a proof. It might need some fine tuning, but I think it covers all the cases. I think many solutions are possible. This is a direct proof.

(Side note: it is a pity SO doesn't support math, such as in LaTeX.)

Proof

Let T and N be the sets of terminal and non-terminal symbols.

Let the following hold

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

Note that a grammar is LL(1) if the following holds for every pair of productions A -> B and A -> C:

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

Consider a language with is LL(1), with A -> B and A -> C.
That is to say there is some string of terminals TZ which admits multiple derivations by distinct parse trees.

Suppose that the left derivation reaches S ->* TAY ->* TZ. The next step may be either TAY -> TBY, or TAY -> TCY.
Thus the language is ambiguous if both BY ->* Z and CY ->* Z.
(Note that since A is an arbitrary non-terminal, if no such case exists, the language is non-ambiguous.)

Case 1: Z = empty

By rule 1 of LL(1) grammars, at most one of B and C can derive empty (non-ambiguous case).

Case 2: Z non-empty, and neither B nor C derive empty

By rule 2 of LL(1) grammars, at most one of B and C can permit further derivation because the leading terminal of Z cannot be in both First(B) and First(C) (non-ambiguous case).

Case 3: Z non-empty, and either MaybeEmpty(B) or MaybeEmpty(C)

Note the by rule 1 of LL(1) grammars, B and C cannot both derive empty. Suppose therefore that MaybeEmpty(C) is true.

This gives two sub-cases.

Case 3a: CY -> Y; and Case 3b: CY ->* DY, where D is not empty.

In 3a we must choose between BY ->* Z and CY -> Y ->* Z, but notice that First(Y) subset-of Follow(A). Since Follow(A) does not intersect First(B), only one derivation can proceed (non-ambiguous).

In 3b we must choose between BY ->* Z and CY ->* DY ->* Z, but notice that First(D) subset-of First(C). Since First(C) does not intersect First(B), only one derivation can proceed (non-ambiguous).

Thus in every case the derivation can only be expanded by one of the available productions. Therefore the grammar is not ambiguous.

回复收藏 0 原文