视频字幕
在编译原理中，FOLLOW集和SELECT集是构建LL(1)预测分析器的重要概念。FOLLOW集表示可能紧跟在某个非终结符后面的终结符集合，而SELECT集则表示选择某个产生式时的输入符号集合。让我们通过一个简单的算术表达式文法来理解这些概念。
FOLLOW集的定义是：对于文法中的非终结符A，FOLLOW(A)包含所有可能紧跟在A后面的终结符。计算FOLLOW集有四个基本规则：首先将美元符号加入开始符号的FOLLOW集；然后对于产生式A推导出αBβ，将FIRST(β)中除空串外的终结符加入FOLLOW(B)；如果空串属于FIRST(β)，则将FOLLOW(A)加入FOLLOW(B)；最后重复应用这些规则直到所有FOLLOW集不再变化。
SELECT集用于确定在给定输入符号时应该选择哪个产生式。对于产生式A推导出α，如果空串不属于FIRST(α)，则SELECT集就等于FIRST(α)；如果空串属于FIRST(α)，则SELECT集等于FIRST(α)去掉空串后与FOLLOW(A)的并集。通过计算我们的示例文法，可以得到每个产生式的SELECT集，这些集合将用于构建LL(1)分析表。
使用SELECT集可以构建LL(1)分析表。对于每个产生式A推导出α，在分析表的[A, a]位置填入该产生式，其中a属于SELECT(A推导出α)。LL(1)文法要求同一非终结符的所有产生式的SELECT集必须两两不相交。通过检查我们的示例文法，所有SELECT集确实两两不相交，因此这是一个有效的LL(1)文法，可以用于构建确定性的预测分析器。
总结一下我们学习的内容：FOLLOW集表示可能紧跟在非终结符后面的终结符集合，主要用于处理包含空串的产生式。SELECT集用于确定在给定输入符号时应该选择哪个产生式进行推导。LL(1)文法要求同一非终结符的所有产生式的SELECT集必须两两不相交。这些概念是构建预测分析器的重要理论基础，在编译器设计中具有重要的实际应用价值。