编译原理FIRST集、FOLLOW集、SELECT集求法通俗解释 & LL(1)文法判定

若 X∈VN ，那么 X 的产生式分以下三种情况:

则 FIRST(Y)–{ε}⊆FIRST(X)

特例: X→Y1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk     且 Y1,Y2,⋅⋅⋅Yi−1∈VN       Y1,Y2,⋅⋅⋅Yi−1⟹∗ε

特别地，当 Y1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk⟹∗ε

结论:针对无空产生式的文法G，同一非终结符的任两个产生式的右部符号串的FIRST集无交集，即可进行确定的自顶向下分析。

考虑文法G[S]: S→aA S→d A→bAS A→ε 求得各终结符和符号串的FIRST集合如下: FIRST(S)={a,d} FIRST(A)={b,ε} FIRST(aA)={a} FIRST(d)={d} FIRST(bAS)={b} FIRST(ε)={ε}   若输入串 W=abd ，则试图推导出abd串的推导过程为 S⇒aA⇒abAS⇒abS⇒abd   从以上推导过程中可以看到，在第2步到第3步的推导中，即 abAS⇒abS 时，因为当前面临的输入符号为 d ，但是最左非终结符A的产生式右部的开始符号集都不包含 d ，但有ε，因此对于 d 的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时候选用产生式 A→ε 向下推导。而当前 A 后面的符号为S， S 产生式右部的开始符号集包含了d，所以例子中可用 S→d 推导得到匹配。 语法树如下所示: 很显然，我们从以上叙述中可以得出:   当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的开始符号集两两不相交，并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。因此，引入了一个文法符号的后跟符号集合。 引入以下FOLLOW集的概念:

因此对于每一文法符号 A∈VN ，实际上求 FOLLOW(A) 就是考察A在产生式右端的出现情况，哪些终结符号可以跟随在A后面？

使用下列规则，直至每个FOLLOW集不再增大为止：

例题: A→BCc | gDB B→bCDE | ε C→DaB | ca D→dD | ε E→gAf | c

对于FIRST集合，解释其中的FIRST(A)的求解。

对于FOLLOW集合，有如下的计算情况:

由于从2中我们得出结论:   当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的开始符号集两两不相交，并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。   因此当文法中含有形如：

一个产生式的选择符号集SELECT。给定上下文无关文法的产生式 A→α,A∈VN,α∈V∗ ，若 α⇏∗ε ，则 SELECT(A→α)=FIRST(α) 。

如果 α⇒∗ε ，则 SELECT(A→α)=(FIRST(α)−{ε})⋃FOLLOW(A) 。

因此一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式， A→α，A→β ，满足

再次回到上述例题

A→BCc | gDB B→bCDE | ε C→DaB | ca D→dD | ε E→gAf | c

  因此根据以上所求得的FIRST集和FOLLOW集，可求得各产生式的SELECT集合如下：