文法FIRST与FOLLOW集计算疑问：Follow(A)结果不符的原因

嗨，这个问题其实是因为你和书里用的是不同版本的文法——一个是消除左递归后的，一个是原始文法，两者的Follow集自然会有差异，我给你一步步拆解清楚：

首先明确：Follow集是针对具体文法结构的属性，即使两个文法生成的语言完全等价（比如原始文法和消除左递归后的文法），它们的Follow集也可能不一样。

先看原始文法的Follow(A)计算 #

原始文法：

A → B C
B → A x | x
C → y C | y

先快速梳理Follow集的核心计算规则：

• 开始符号的Follow集默认包含结束符$
• 如果产生式中有X → αYβ，那么FIRST(β) - {ε}的所有符号都加入Follow(Y)
• 如果产生式是X → αY，或者X → αYβ且ε ∈ FIRST(β)，那么Follow(X)的所有符号都加入Follow(Y)

现在计算原始文法的Follow(A)：

1. A是开始符号，所以$ ∈ Follow(A)
2. 看产生式B → A x：这里A的后面直接跟着x，根据规则，x要加入Follow(A)
3. 没有其他产生式涉及A的右部出现，所以最终原始文法的Follow(A) = {x, $}——这就是书里给出的答案。

再看你消除左递归后文法的Follow(A)计算 #

你消除左递归后的文法：

A → B C
B → x B'
B' → C x B' | ε
C → y C | y

在这个文法里，你会发现A只出现在产生式的左部，没有任何产生式的右部包含A，所以：

1. A是开始符号，$ ∈ Follow(A)
2. 没有其他产生式能给Follow(A)添加新符号，所以你算出的Follow(A) = {$}是完全正确的。

总结 #

书里的答案是基于原始未消除左递归的文法计算的，而你用的是消除左递归后的等价文法，两者结构不同，导致Follow集的差异。等价文法只是生成的语言相同，但文法层面的属性（比如Follow集、FIRST集）不一定完全一致，这是很正常的情况。

内容的提问来源于stack exchange，提问作者Num1337