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

Question

我有三种语法:

A -> aB |乙| CBB

B -> aB |巴| aBb

C -> aaA |乙| caB

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

这就是我到目前为止所拥有的......

A -> aB |乙| CBB

第一个(aB) = a

第一个(b) = b

第一个(CBB) = aaA = a

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

B -> aB |巴| aBb

第一个(aB) = a

第一个(ba) = b

第一个(aBb) = a

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

C -> aaA |乙| caB

第一个(aaA) = a

第一个(b) = b

第一个(caB) = c

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

Answer 1

测试的重点是查看第一个终端是否可以告诉您使用哪个规则(LL 的要求)。对于 B 来说，很明显有 2 条规则可以适用于终端 a；很明显，C 的每个规则都以不同的终端开始。您可以看到 C(以及 CBB)可能的第一个终结点与 A 的其他规则重叠。

底线:看起来不错(不过，如果您停在 CBB 的单个航站楼并碰巧选择了 c，您就会得出错误的结论)。