LL（1）不能模棱两可 [英] LL(1) cannot be ambiguous

问题描述

如何证明没有LL（1）语法是模棱两可的？

How can it be shown that no LL(1) grammar can be ambiguous?

我知道模棱两可的语法是什么，但无法证明上述定理/引理。

I know what is ambiguous grammar but could not prove the above theorem/lemma.

推荐答案

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

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.

（请注意：很可惜，它不支持数学运算，例如LaTeX。）

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

证明

让T和N为终端符号和非终端符号的集合。

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

保持以下状态

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

请注意，如果语法为LL（1）对于每对生产A-> B和A-> C，以下成立：

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

考虑语言为LL（1 ），并带有 A-> B 和 A-> C 。
也就是说，有一串终端TZ允许通过不同的解析树进行多次推导。

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.

假设左推导达到 S-> * TAY-> * TZ 。下一步可以是 TAY-> TBY 或 TAY-> TCY 。
因此，如果 BY-> * Z 和 CY-> * Z 。
（请注意，由于A是任意的非终结符，因此，如果不存在这种情况，则该语言是明确的。）

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.)

情况1：Z =空

根据LL（1）语法的规则1，B和C中的一个最多可以得出空（无歧义的情况）。

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

情况2：Z为非空值，B和C都不得出空

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

根据LL（1）语法的规则2，最多B和C中的一个可以允许进一步推导，因为Z的首端不能同时位于 First（B）和 First（C）（无歧义的情况）。

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).

案例3：Z为非空，且 MaybeEmpty（B）或 MaybeEmpty（C）

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

请注意LL（1）语法，B和C不能都得出空。因此，假设 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.

这给出了两个子情况。

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

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

在3a中，我们必须选择在 BY-> * Z 和 CY->之间； Y-> * Z ，但请注意，第一个（Y）子集的Follow（A）。由于跟随（A）不与 First（B）相交，因此只能进行一次推导（明确）。

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).

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

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.

这篇关于LL（1）不能模棱两可的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！