【预备知识】

FIRST集、FOLLOW集、SELECT集的异同：

同：求终结符的结合

异：FIRST集、FOLLOW集的对象是非终结符；SELECT的对象是产生式

【详细说明】

FIRST集：非终结符前面的终结符—组成的集合(非终结符能取ε时，ε也算)

FOLLOW集：非终结符后面紧跟着的终结符—组成的集合(如有ε，要写成#，代表停止)

SELECT集：产生式右端的第一个终结符组成的集合(如果是终结符，则直接写。如果是非终结符，一般为非终结符的FIRST集；若非终结符能取到ε，则ε后的第一个终结符也包括在内)

【例题】

考虑文法

G[S]：S → aSAb | Ab

           A → cA | ε

（1）求出该文法的每个非终结符的FIRST集、FOLLOW集

FIRST(S) = {a, c, ε}        FOLLOW(S) = {c, b, ε} (说明，由于S的后面没有终结符，只有非终结符A，所以先将A的first集算入，即c；而且A能取到ε，则先将ε算进来，然后将A → ε代入到S的两个产生式中，代入后S后面紧跟着的终结符就变成了b，所以b也算入S的FOLLOW集)

FIRST(A) = {c, ε}            FOLLOW(A) = {b, #}(说明，在S的产生式中，A后面跟着b,所以b算入其中，A能取到ε的情况，所以ε也算入其中，由于存在A → ε时，程序停止，所以在FOLLOW集中要将ε写成#，表示停止)

（2）求出各个产生式的SELECT集

SELECT(S → aSAb) = {a}

SELECT(S → Ab) = (A能推出ε) FIRST(A) - {ε} + FOLLOW(A) = {b, c}

SELECT( A → cA) = {c}

SELECT( A → ε) = (直接取FOLLOW，并且去掉#) {b}

（3）证明该文法是LL(1)文法

其实，我们求FIRST集、FOLLOW集、SELECT集的的目的就是为了判断文法是否是LL(1)文法

LL(1)文法的含义：

第一个L表明自顶向下分析是从左向右扫描输入串；

第二个L表示分析过程中将用最左推导，

1表示只需向右看一个符号便可决定选择哪个产生式进行推导。

所以，若存在一个产生式，向右看一个符号还不能决定选择哪个产生式的时候，该文法不是LL(1)文法。

在此题中，由于SELECT(S → aSAb) ∩ SELECT(S → Ab) = {a} ∩ {b, c} = ∅，

SELECT( A → cA) ∩ SELECT( A → ε) = {c} ∩ {b} = ∅，即向右看一个符号就能决定选择哪个产生式，所以是LL(1)文法。