为什么这个文法是 LL(1)，即使所有的 FIRST 集都相同？
Why is this grammar LL(1) even though all the FIRST sets are the same?
考虑以下 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
B → b | c
C → b | c
请注意，A、B 和 C 三个都具有相同的第一个集合，即 {b, c}。但是这个语法也是 LL(1)。虽然您可以通过写出实际的 LL(1) 解析 table 来让自己正式相信这一点，但您也可以换一种方式来考虑这一点。假设您正在读取非终结符 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，则不会。也就是说
- 在读取 a 时，我们选择 A → aA，并且
- 在阅读 b o r c 时，我们选择 A → ε。
请注意，在本次讨论中，我们从来不需要考虑 FIRST(B) 或 FIRST(C) 是什么。事实上，我们甚至不需要查看 FIRST(A) 是什么！所以这就是为什么不一定有冲突的原因。如果我们遇到需要比较 FIRST(A) 与 FIRST(B) 或类似情况的场景，那么是的，我们肯定会发生冲突。但这从来没有发生过，所以不存在冲突。
考虑以下 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
B → b | c
C → b | c
请注意，A、B 和 C 三个都具有相同的第一个集合，即 {b, c}。但是这个语法也是 LL(1)。虽然您可以通过写出实际的 LL(1) 解析 table 来让自己正式相信这一点，但您也可以换一种方式来考虑这一点。假设您正在读取非终结符 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，则不会。也就是说
- 在读取 a 时，我们选择 A → aA，并且
- 在阅读 b o r c 时，我们选择 A → ε。
请注意，在本次讨论中，我们从来不需要考虑 FIRST(B) 或 FIRST(C) 是什么。事实上，我们甚至不需要查看 FIRST(A) 是什么！所以这就是为什么不一定有冲突的原因。如果我们遇到需要比较 FIRST(A) 与 FIRST(B) 或类似情况的场景，那么是的，我们肯定会发生冲突。但这从来没有发生过，所以不存在冲突。