grammar - 使用成对不相交测试确定语法是否为 LL

Question

我有三个语法：

A -> aB | 乙 | CBB

B -> aB | 巴 | aBB

C->aaA | 乙 | 出租车

我需要“通过执行成对不相交测试来确定 [它们] 是否是 LL 语法，显示每个非终结符的每个 RHS 的第一组。

这是我目前所拥有的......

A -> aB | 乙 | CBB

第一(aB) = a

第一（b）= b

第一(CBB) = aaA = a

这是我遇到的麻烦。我正确地做 CBB 了吗？如果是这样，我会说它们相交并且规则未通过测试。（对？）

B -> aB | 巴 | aBB

第一(aB) = a

第一（ba）= b

第一(aBb) = a

它们相交，因此该规则未通过测试。

C->aaA | 乙 | 出租车

第一（aaA）=一个

第一（b）= b

第一(caB) = c

它们不相交，因此规则通过

Answer 1

测试的重点是看，查看第一个终端，您是否可以判断使用哪个规则（LL 的要求）。对于 B 来说，很明显有两条规则可以适用于终端 a；这也很明显，C 的每个规则都以不同的终端开始。您可以看到 C（以及因此 CBB）可能的第一个终端与 A 的其他规则重叠。

底线：看起来不错（尽管，如果您在 CBB 的一个航站楼停了下来并且碰巧选择了 c，那么您会得出错误的结论）。

Answer 2

我相信 A 规则的第一个集合是 {a}、{b} 和 {a,b,c}。该文法不是 LL，因为至少有一个交集，它没有通过成对离散检验。实际上，在这种情况下，有两个相交的终端，a 和 b。