编译原理 —— FOLLOW集

FOLLOW集

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

计算非终结符A的 FOLLOW集合

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

（2）如果存在一个产生式 $A→αBβ$A→αBβ ，那么FIRST（B）中除 $ε$ε 之外的所有符号都在FOLLOW（B）中

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

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

举例：

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

---

参考地址：

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