写在前面

编译原理，关于FIRST集和FOLLOW集部分的笔记，本文参考了另一篇博客，在此基础上加入了一些个人的理解。

FIRST集

定义

设文法 $G= (V_T,V_N,S,P)$是上下文无关文法，则有 $$FIRST(\alpha) ={a|\alpha\Rightarrow^*a…,a\in V_T} $$

例子

  1. 后面是终结符

    1
    2
    3
    4
    5
    >   A->aB|ε
    >   A->c
    >   
    >   FIRST(A) = {a,c,ε}
    >

因为A能直接得到的第一个终结符包括a，c，ε，所以把他们加入。

  1. 后面是非终结符（一）

    1
    2
    3
    4
    5
    >   A->Ba
    >   B->b
    >   
    >   FIRST(A) = {b}
    >

A能直接得到的是一个非终结符，而这个非终结符只能得到一个终结符b，所以把b加入。

  1. 后面是非终结符（二）

    1
    2
    3
    4
    5
    >   A->Bc
    >   B->b|ε
    >   
    >   First(A)={b,c}
    >

注意，这里没有把ε也加入到First集中，是因为A通过B得到ε时，还能继续向后，也就是说将ε代换到第一个式子里面，后面还有一个非终结符c，所以不能把ε加入。

我们可以说$First(B)={b,ε}$，这是显然的。

  1. 后面是非终结符（三）

    1
    2
    3
    4
    5
    6
    >   A->BC
    >   B->b|ε
    >   C->c|ε
    >   
    >   First(A)={b,c,ε}
    >

对比第3条，为什么这里又把ε加入了，是因为将ε代换B后，继续向后，发现C也能被ε代换，于是应用了课本第三条规则，即$A->ε$,此时可以将ε加入到First集。

FOLLOW集

定义

设S是文法G的开始符号，对于G中的任何一个非终结符A，则有 $$FOLLOW(A) ={a|S\Rightarrow^*…Aa…,a\in V_T} $$

理解

$FOLLOW(A)$就是紧跟在A后面的终结符集和或者结束符$’$‘$

求解规则
  1. 对于文法的开始符号S,则把$$$放进Follow（S）中；
  2. 若$A->αBβ$是一个产生式，则把$First(β)$中除了ε以外的符号加入到Follow（B）中；
  3. 若$A->αB$是一个产生式，或$A->αBβ$是一个产生式且$First(\beta)$中包含ε，则把$Follow(A)$加入到$Follow(B)$中