求解FIRST集合的2个步骤+求解FOLLOW集合的5个步骤（保证不会有遗漏！！）

╰+攻爆jí腚メ 2022-12-23 11:10 60阅读 0赞

## 写在前面 ##

网上看了很多求解FIRST集合和FOLLOW集合的方法，但是用起来有时候还是会有所遗漏，于是总结了以下方法，只要严格按照这个方法操作，肯定不会找漏。

我们知道，找漏的原因其实就是各种推导总是搞错，如果我们只看产生式就能找到所有集合，而不需要去具体推导，那么就不会遗漏。

## 求解FIRST集合 ##

由于求解FOLLOW集合涉及到求解FIRST集合，因此先讲下怎么求解FIRST集合。  
根据FIRST集合的定义：  
![在这里插入图片描述][20201124181015940.gif_pic_center]  
简单来说就是一个非终结符（这里只讨论非终结符）能够推导出一个以终结符开头的串，那么该终结符就属于该非终结符的FIRST集合。由此得到以下算法，两个步骤：

1.  遍寻所有产生式，找到所有右边为一个终结符开头的产生式A->a…，这里尤其注意，一定不要遗忘产生式右边只有一个终结符的！！很多人看到A->a…就想当然地以为a后边一定要有东西，这是不对的。最后把a加入FIRST(A)。
2.  遍历所有产生式，找到右边以一个非终结符开头的，这里也要注意A->B也是允许的，B后边不一定要有东西，然后将FIRST(B)加入到FIRST(A)中。

重点在于求FOLLOW集合，我把这个步骤分解成五个步骤：

1.  将\#加入到FOLLOW(S)中，S为文法开始符号。
2.  遍寻所有产生式，找到所有类似A->…Ba…的产生式，将a加入到FOLLOW(B)中，这里也要注意：B的前面和a的后面可以没有任何东西！！
3.  遍寻所有产生式，找到所有两个类似A->…BC…的产生式，BC都为非终结符。这里举一个极端例子：A->BCDE，我们将任意两个相邻非终结符对中，后面非终结符的FIRST集合中除空串以外的所有加入到前面非终结符的FOLLOW集合中！简单来说，这里需要分别将C、D、E的FIRST集合加入到B、C、D的FOLLOW集合中。
4.  遍寻所有产生式，找到类似A->…B的产生式，这里要注意：一定不要遗忘产生式右边只有一个非终结符的，比如A->B这种。然后我们将FOLLOW(A)加入到FOLLOW(B)中。
5.  遍寻所有产生式，找到所有类似A->…BC的产生式。还是以A->BCDE为例，这里只需要考虑DE的关系，因为必须要求这两个相邻非终结符在最后！！如果FIRST(E)中含有空串，就将FOLLOW(A)加入到FOLLOW(D)中。步骤5其实是步骤4的特殊情况。

## 注意以上所有过程最好都重复至少两次，防止存在这种情况：比如S要加入E中，S在这一轮加入了新的，E中最后却没有更新。 ##

## 实战演练一下 ##

![在这里插入图片描述][20201124183304474.png_pic_center]

### 1.求解FIRST集合 ###

1). 根据上面的算法，首先找到所有右边为一个终结符开头的产生式A->a…。我们发现S=\{a\},D=\{  ϵ \\epsilon ϵ\},T=\{b\},M=\{b\},H=\{  ϵ \\epsilon ϵ\}。  
2). 遍历所有产生式，找到右边以一个非终结符开头的。D->STe，于是将S加入D中，D=\{  ϵ \\epsilon ϵ,a\}；H->M,将M加入H中，于是H=\{  ϵ \\epsilon ϵ,b\}  
3). 综上：S=\{a\},D=\{  ϵ \\epsilon ϵ,a\},T=\{b\},M=\{b\},H=\{  ϵ \\epsilon ϵ,b\}。

### 2.求解FOLLOW集合 ###

1). S=\{\#\}。  
2). 寻找所有产生式右边非终结符身后跟着一个终结符的产生式。我们发现：D->STe，所以T=\{e\}。  
3). 找寻所有右边有两个非终结符相邻的产生式。我们发现：D->STe，所以将FIRST(T)加入S，S=\{\#,b\}。  
4). 找寻所有右边以一个非终结符结尾的产生式。我们发现：S->aD，所以将S加入D中，D=\{\#,b\}；T->bM，将T加入M中，M=\{e\}；M->bH，将M加入H中，H=\{e\}；H->M，将H加入M中，M不变。  
5). 找寻所有右边以两个相邻非终结符结尾的产生式，没找到。  
6). 综上：S=\{\#,b\}，D=\{\#,b\}，T=M=H=\{e\}。

[20201124181015940.gif_pic_center]: /images/20221120/bb50828a78bc4ab9a900cb33a3f494fa.png
[20201124183304474.png_pic_center]: /images/20221120/d591c19b2acd4264976c090b179073b0.png