FOLLOW集

对于一个非终结符号X，FOLLOW(X)表示推导过程中紧跟在X后的非终结符号的集合，举个例子，在推导过程中如果有形如S⇒αXaβ的推导，可以得到，非终结符号a∈FOLLOW(X)。因为X后面可能会有多个不同的终结符，但是在这条推导中，我们仅能分析出a∈FOLLOW(X)。

1.分析

根据X出现的不同位置，可以分为下面的两种情况

（1）X是开始符号

默认开始符号后有一个“界符”——“#或$” ，因此FOLLOW(X)={ # }或{ $ }

（2）形如S→αXβ

如果文法中存在上述的产生式，可以看到，使用这条产生式推导，β会跟在X后面，FOLLOW(X)就是X后面跟着得终结符，也就是β可以推导出得非终结符号（除了ε）也就是说，FIRST(β)-{ε}是FOLLOW(X)的子集FOLLOW(X)⊇FIRST(β)-{ε}

减去{ε}的原因：因为FOLLOW集中跟的是一个终结符号，即使可能存在ε∈FIRST(β)，β使用空串产生式进行推导后，X后面仍然会有其他终结符号，而不是ε，这种情况我们在下面讨论，总之，现在先下个结论——FOLLOW集中不会出现ε

（3）形如S→αX

如果出现上面的产生式，假设有下面的句型

…Sw… w为终结符，使用上述产生式进行一步推导...Sw...⇒...αXw，可以看到，在S后面的终结符号出现在了X后面，也就是说FOLLOW(S)是FOLLW(X)的子集FOLLOW(X)⊇FOLLOW(S)

（4）形如S→αXβ，且ε∈FIRST(β)

如果，ε∈FIRST(β)，则说明β可以推导出空串。如果β使用空串产生式进行推导，那么这样的情况就变成了上面的（3）

举个例子：

...Sw... ⇒ ...αXβw... ⇒ ...αXw...

可见，如果有形如S→αXβ的产生式，并且ε∈FIRST(β)，就变成了情况（3）。同时，ε∈FIRST(β)是情况（2）的特殊情况

对于情况（4）FOLLOW(X)⊇FIRST(β)-{ε}+FOLLOW(S)

2.总结

规则：

1. 如果S是开始符号，将#或$放入FOLLOW(S)
2. 如果存在产生式A→αBβ，将FIRST(β)中除了ε的所有元素加入FOLLOW(B)
3. 如果存在产生式A→αB，或A→αBβ且ε∈FIRST(β)，则将FOLLOW(A)加入FOLLOW(B)

求FOLLOW集：

假设要求FOLLOW(X)，则在文法中找到X在产生式右部的产生式，然后应用上面的三条规则，不断地将子集加入FOLLOW集，知道没有符号可以加入为止。

举例：

求FOLLOW(E)，首先，E是开始符号，将#加入FOLLOW(3)；找E出现在右部的产生式，发现只有F→(E) 这里，应用规则2，将FIRST())-{ε}加入FOLLOW(E)，也就是将“)”加入FOLLOW(E)，没有其他的产生式可以用于分析，所以，FOLLOW(E)的求解完成，综上FOLLOW(E)={#,)}

求FOLLOW(E’)，找出E’在右部的产生式，E→TE'和E'→+TE'。
关于产生式E→TE'，应用规则3，将FOLLOW(E)加入FOLLOW(E’)；
关于产生式E'→+TE'，应用规则3，将FOLLOW(E’)加入FOLLOW(E’)
综上，FOLLOW(E’)=FOLLOW(E)={#,)}

求FOLLOW(T)，找出T在右部的产生式，E→TE'和E'→+TE'
关于产生式E→TE'，既符合规则2，也符合规则3，所以，将FIRST(E’)-{ε}加入FOLLOW(T)，将FOLLOW(E)加入FOLLOW(T)；
关于产生式E'→+TE'，既符合规则2，也符合规则3，所以，将FIRST(E’)-{ε}加入FOLLOW(T)，将FOLLOW(E’)加入FOLLOW(T)。
FIRST集的求法上一篇博客写过，这里不再赘述，FISRT(E’)={+,ε}
综上，FOLLOW(T)=FIRST(E’)-{ε}+FOLLOW(E)+FOLLOW(E’)={+,#,)}