考虑以下 CFG：
S := AbC
A := aA | epsilon
C := Ac
这里，FIRST(A) = FIRST(B) = FIRST(C) = {a, ε}，所以所有的 FIRST 集合都是一样的。然而，这个文法应该是 LL(1)。这怎么可能？这不是意味着到处都会有一堆FIRST/FIRST冲突吗？
拥有多个具有相同 FIRST 集合的非终结符从根本上来说并没有错。如果在必须在多个生产选项之间进行选择的上下文中，您有多个具有重叠 FIRST 或 FOLLOW 集的非终结符，事情只会变得有问题。
例如，考虑这个简单的语法：
A → bB | cc
乙 → 乙 | C
C → b | C
请注意，A、B 和 C 三个都具有相同的 FIRST 集，即 {b, c}。但是这个文法也是 LL(1)。虽然您可以通过写出实际的 LL(1) 解析表来正式说服自己，但您也可以用另一种方式来考虑这一点。想象一下，您正在阅读非终结符 A，并且您看到了字符 b。你应该选择哪个产生式：A → bB，还是 A → cC？好吧，没有理由选择 A → cC，因为这会将 c 放在字符串的前面。所以不要选那个。相反，选择 A → bB。类似地，假设您正在阅读 A 并看到字符 c。你应该选择哪个生产？您永远不想选择 A → bB，因为这会将 b 放在字符串的前面。相反，您会选择 A → cC。
请注意，在本次讨论中，我们从未停止思考 FIRST(B) 或 FIRST(C) 是什么。它根本没有出现，因为我们从不需要知道可以在那里制作哪些角色。
现在，让我们看看你的例子。如果您尝试扩展 S，则只能应用一种可能的产生式，即 S → AbC。所以这里不可能有冲突；当您看到 S 时，您总是应用该规则。同样，如果您要扩展 C，则别无选择。你必须展开 C → Ac。
所以现在让我们考虑非终结符 A，在那里确实可以选择下一步做什么。如果你看到字符 a，那么我们必须决定——我们是展开 A → aA，还是展开 A → ε？在回答这个问题时，我们必须考虑 A 的 FOLLOW 集，因为产生式 A → ε 只有在我们看到一个终端符号时才有意义，我们基本上只想让 A 不碍事。这里，FOLLOW(A) = {b, c}，b 来自产生式 S → AbC，c 来自产生式 C → Ac。因此，如果我们看到 b 或 c，我们只会选择 A → ε，而不是看到 a。这意味着
请注意，在此讨论中，我们从不需要考虑 FIRST(B) 或 FIRST(C) 是什么。事实上，我们甚至都不需要看 FIRST(A) 是什么！所以这就是为什么不一定有冲突的原因。如果我们遇到需要将 FIRST(A) 与 FIRST(B) 或类似情况进行比较的情况，那么是的，我们肯定会发生冲突。但这从来没有出现过，所以不存在冲突。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句