FOLLOW集

• FOLLOW（A）：紧跟在非终结符A后边的终结符α的集合
• 如果A是某个句型的的最右符号，则将结束符 $＄$ 添加到 FOLLOW（A）中

计算非终结符A的 FOLLOW集合

（1）将$＄$放入 FOLLOW（S）中，其中S是开始符号，$＄$是输入右端的结束标记

（2）如果存在一个产生式 $A\to \alpha B\beta$ ，那么FIRST（β）中除 $\epsilon$ 之外的所有符号都在FOLLOW（B）中
（因为B可以由A推导出来，且位于最右边，所以A的FOLLOW集也是B的FOLLOW集）

（3）如果存在一个产生式 $A\to \alpha B$，或存在产生式 $A\to \alpha B\beta$且FIRST（β）包含 $\epsilon$ ，那么FOLLOW（A）中的所有符号都在FOLLOW（B）中

（4）重复上述过程，直到没有新的终结符可以加入

举例：

1. $E$ 本身就是一个句型，它是该句型的最右符号，故将结束符 $＄$添加到FOLLOW$(A)$中
2. 由式子①
   1. $E^{\prime }$ 紧跟在 $T$ 后面，故 FOLLOW$(T)$ 中包含 FIRST$(E^{\prime })$中的终结符 +
   2. FIRST$(E^{\prime })$中包含 $\epsilon$，$T$可能是产生式①右部的最后一个符号，故 $T$ 依赖于 $E$，FOLLOW$(E)$ ∈ FOLLOW$(T)$
   3. $E^{\prime }$ 可能是产生式①右部的最后一个符号，故 $E^{\prime }$ 依赖于 $E$，FOLLOW$(E)$ ∈ FOLLOW$(E^{\prime })$
3. 式子②中，$T$ 和 $E^{\prime }$ 所处位置与式子①相同，分析结果也将相同
4. 由式子③
   1. $T^{\prime }$ 紧跟在 $F$ 后面，故 FOLLOW$(F)$ 中包含 FIRST$(T^{\prime })$中的终结符 *
   2. FIRST$(T^{\prime })$中包含 $\epsilon$，$F$ 可能是产生式③右部的最后一个符号，故 $F$ 依赖于 $T$，FOLLOW$(T)$ ∈ FOLLOW$(F)$
   3. $T^{\prime }$ 可能是产生式③右部的最后一个符号，故 $T^{\prime }$ 依赖于 $T$，FOLLOW$(T)$ ∈ FOLLOW$(T^{\prime })$
5. 式子④中，$F$ 和 $T^{\prime }$ 所处位置与式子③相同，分析结果也将相同
6. 式子⑤中，$E$ 的后面跟着终结符 $）$，故将 $）$添加到FOLLOW$(E)$中
7. 验证是否满足所有的依赖关系

参考地址：

https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce