编译原理与实践：节中的FOLLOW集

当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件时，仍然不一定能进行有效的自上而下分析。

例4.8 判断输入串w=abd是否为如下文法的句子

S→aA|d

A→bAS|ε

文法满足相同左部的候选式终结首符集两两不相交，此外还包含特殊的产生式A→ε。输入串语法分析树的构造过程如图4-8所示。在推导的第二步到第三步，即abAS⇒abS时，最左侧的非终结符A面临输入符号‘d’的匹配工作，然而A的候选式的首符集都不包含‘d’。但是，A具有空产生式，可以利用产生式A→ε进行推导，此时，对于‘d’的匹配依赖于A后面的S。S的第二个候选式的终结首符集合包含‘d’，所以匹配成功。

图4-8　输入串w=abd确定的自上而下语法分析

由上述推导过程可以看出，‘d’是在句型或句子推导过程中，紧跟在非终结符A后面出现的终结符。为了能够使用空产生式，需要判断非终结符的后跟终结符是否与下一输入符号相匹配。

定义4.2 文法非终结符A的后跟符号集FOLLOW（A）如下

当非终结符A面临输入符号a，且a不属于A的任意候选首符集，但A的某个候选首符集包含ε时，只有当a∈FOLLOW（A），则允许A自动匹配。(www.xing528.com)

如果在例4.8的基础上，为非终结符A增加一个产生式A→d，将文法稍加修改为

FOLLOW集

S→a A|d

A→b AS|ε|d

文法依然满足相同左部的候选式终结首符集两两不相交的条件。但是，为输入串abd构造语法分析树的第二步到第三步时，非终结符A面临输入符号d的匹配工作。A的第三个候选式的首符集包含d；此外，A具有空产生式，S能够推导出的d属于A的后跟终结符集。此时

FIRST(A)∩FOLLOW(A)={d}

那么，A应该自己完成d的推导工作，还是应该利用空产生式将工作交由S来完成，无法立即决定。在尝试用A的第三个候选式进行推导后，将出现语法树构造失败而产生回溯。

由此可以看出，当某非终结符含有空产生式时，其非空产生式右部的首符集两两不相交，而且与推导过程中紧跟其右边可能出现的终结符集也不相交，则仍可构造确定的自上而下分析。