FIRST集、FOLLOW集、SELECT集

【预备知识】

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)文法。

First（A）为A的开始符或者首符号集。

如果两个A产生式 A ->α | β ，且FIRST(α)和FIRST(β)不相交；

下一个输入符号是x，若x∈FIRST(α)，则选择 A->a ，若x∈FIRST(β)，则选择 A->b 。

计算FIRST(X)的方法携轿

如果算法看不懂，那我们来根据算法来模拟一下！

因为求FIRST集合如果有终结符号会比较好处理，所以我们逆顺序进行实施；

应该一看明白了！

Follow(A)指的是在某些句型中紧跟虚隐凳在A右边的 终结符号 的集合

一步一步来看

2.1 第一次迭代

第一种情况： FOLLOW(T)=FIRST(E')={ + }

第二种情况 ： FOLLOW(E')=FOLLOW(E)={ $ }

第一种情况： FOLLOW(T)=FIRST(E')={ + }

第二种情况 ： FOLLOW(T)=FOLLOW(E')={ + , $ }

第一种情况： FOLLOW(F)=FIRST(T')={ * }

第二种情况 ： FOLLOW(T')=FOLLOW(T)={ + , $ }

第一种情况： FOLLOW(F)=FIRST(T')={ * }

第二种情况 ： FOLLOW(F)=FOLLOW(T')={ + , * , $ }

第一种情况 ： FOLLOW(E)={ $ , ) }

2.2 第二次迭代

由于我们列出了等值关系，所以只需要再走一次第一次迭代的过程就可以了！

因为主要是FOLLOW可能在变，所以我们只需要找到FOLLOW的等值关系即可

我在上面标出了第一次迭代的FOLLOW的最新版

下面我只要列出更新的即可

2.3 第三次迭代

第三次迭差旅代就会发现 FOLLOW集合 不再发生改变，这时候规则结束，求出FOLLOW集合。

Follow比较容易出错，出错的点主要在迭代过程的第二种情况的： A ->αBβ 且FIRST(β)包含ε

我们容易忽略这种情况。

只要把每一次迭代过程都写在纸上，尤其注重 Follow集合 的等值！

FIRST集合和FOLLOW集合

一、First集合

定义：

First集合是对产生式右部的字符串而言的，求取的是非终结符VT（或终结符、空字符、文法符号串）的开始符号集合，集合中包含的是由左部非终结符VT推导得到的终结符VN或空字符ε。以α表示一个文法的字符串，FIRST( α ）表示由α推导出的串的首个终结符或空字符组成的集陪档合。

规则

求文法符号X的FIRST( X ) ，直到没有终结符或空字符可以加入。

① 如果X属于终结符VT，则FIRST(X) = { X } 。

② 如果X属于非终结符VN，且有产生式形如X → a…，则FIRST( X ) = { a }。

③ 如果X属于非终结符VN，且有产生式形如X → ABCdEF…（A、B、C均属于非终结符且包含 ε，d为终结符），需要把d、FIRST( A )、FIRST( B )、FIRST( C )加入到FIRST( X)中。

④ 如果X经过一步或多步推导出空字符ε，将ε加入FIRST( X )。

一组文法符号串

由规则可知单个文法字符的FIRST集，那么一组文法字符串的FIRST集也可以求取了。假设文法符号串S由X1X2X3……Xn组成，则将每个文法符号Xi的FIRST集加入到FIRST( S )中，包括空字符ε。

举例1

设有文法G[A]： 

   A→BCc | gDB      

   B→bCDE | ε     

   C→DaB | ca      

   D→dD | ε      

   E→gAf | c 

解：

FIRST( A ) = FIRST( BCc ) ∪ FIRST( gDB ）

=FIRST( B )∪FIRST( C )∪{ c }∪{ g }

由规则③规则②可知

FIRST( A ) =FIRST( B )∪FIRST( D )∪{ a }∪{ c }∪{ c }∪{ g }

={ b，ε }∪{ d，ε }∪{ a }∪{ c }∪{ g }

={ a，b，c，d，g ，ε }

FIRST( B ) = { b，ε }

FIRST( C ) = FIRST( D )∪{ a }∪{ c }= { a，c，d，ε }

FIRST( D ) = { d，ε }

FIRST( E ) = { g，c }

对于A来说：有两种选择 BCc 与 gDB，BCc用规则③，gDB用规则②。

对于B来说：有两种选择 bCDE 与 ε，均用规则②。

对于C来说：有两种选择 DaB 与 ca，由于D存在空字符，所以 DaB用规则③，ca用规则②。

对于D来说：有两种选择dD 与 ε ，分别用规则②与规则④。

对于E来说：有两种选择gAf 与 c ，均用规则②。

举例2

设有文法G[S]:

   S→aBS | bAS | ε

   A→bAA | a

   B→aBB | b

解：

FIRST( S ) = FIRST( aBS )∪FIRST( bAS )∪{ ε }={ a，b，ε }

FIRST( A ) = { a，b }

FIRST( B ) = { a，b }

对于S来说：有三种选择 aBS与bAS、ε，分别用②与规则④。

对于A来说：有两种选择bAA与 a，均用规则②。

对于B来说：有两种选择aBB与 b，均用规则②。

二、Follow集合

定义：

Follow集合是对某个非终结符而言的，求取的是非终结符VT的后继符号集合，集衫首合中包含的是由非终结符VT后面紧跟的终结符VN和结束符$，不能出现空字符ε 。以X表示一个非终结符，FOLLOW( X ）表示当X通过规约出现时，接下来的输入可能是哪些终结符。

规则

求非终结符X的FOLLOW( X ) ，直到没有终结符可以加入。

① 如果X是开始符号，则将$加入到FOLLOW(X)中 。

② 如果存在一个产生式S->αXβ，那么将集合FIRST(β)中除ε外的所有元素加入到FOLLOW(X)当中。

③如果芦塌乱存在一个产生式 S->αX , 或者S->αXβ且FIRST(β)中包含ε , 那么将集合FOLLOW(S)中的所有元素加入到集合FOLLOW(X)中。

举例1

设有文法G[A]： 

   A→BCc | gDB      

   B→bCDE | ε     

   C→DaB | ca      

   D→dD | ε      

   E→gAf | c 

解：

FOLLOW( A ) ={ f ， }∪{ c，d，g， }

FOLLOW( C ) = { c }∪FIRST( D )∪FIRST( E )

             ={ c }∪{ d }∪{ g，c }

             ={ c，d，g }

FOLLOW( D ) = FIRST( B )∪FOLLOW(A )∪FIRST( E )∪{ a }

             ={ b } ∪{ g，c }∪{ f ， }

FOLLOW( E ) = FOLLOW( B )

             ={ a，c，d，f，g， ；E→gAf，规则②将f加入FOLLOW( A )。

对于B的出现来说：有 A→BCc，规则②将FIRST( C )除ε以外加入进去；有A→gDB，规则③将FOLLOW( A )加入进去；有C→DaB，规则③将FOLLOW( C )加入进去。

对于C的出现来说：有 A→BCc，规则②将c加入进去；有B→bCDE，规则③将FOLLOW( D )加入进去，由于D存在空字符ε，所以需要把FIRST( E )除ε以外也加入进去。

对于D的出现来说：有A→gDB，规则②将FIRST( B )除ε以外加入进去，由于B存在空字符ε，所以规则③将FOLLOW( A )加入进去；有B→bCDE，规则②将FIRST( E )除ε以外加入进去；有C→DaB，规则②将a加入进去。

对于E的出现来说：有B→bCDE，规则③将FOLLOW( B )加入进去。

举例2

设有文法G[S]:

   S→aBS | bAS | ε

   A→bAA | a

   B→aBB | b

解：

FOLLOW( S ) = {}∪{ a，b }

             ={ a，b， }∪{ a，b }

             ={ a，b， 加入进去。

对于A的出现来说：有S→bAS，规则②将FIRST( S )除ε以外加入进去,由于S存在空字符ε，规则③将FOLLOW( S )加入进去；有A→bAA，规则②将FIRST( A )除ε以外加入进去。

对于B的出现来说：有S→aBS，规则②将FIRST( S )除ε以外加入进去,由于S存在空字符ε，规则③将FOLLOW( S )加入进去；有B→aBB，规则②将FIRST( B )除ε以外加入进去。

第三部分·如何构造LL(1)分析表

首先画出表格，表格的左列是每一个产生式的左部（不重复），表格的横行是每一个终结符号。

接着逐个考察所有产生式。

抽象算法：

对于G中的每一个产生式， A ->α ,执行以下2步：

1.for ∀ a ∈ FIRST(α)， 将 A ->α 填入 M [A, a ]

//对逐个产生式进行考察，考察产生式的FIRST集合的元素，在找到的元素的对应表格中填写该产生式

//如果发现产生式的FIRST集中包含空符号，就查找该产生式头部的FOLLOW集合中的元素，在元素的对应表格中填写空产生式

原文： https://blog.csdn.net/Cielyic/article/details/82941014

---