GroupBlog

FIRST集

怎样理解FIRST集呢？顾名思义就是一段文法所有可能的出现的开始符号的集。
求FIRST集的步骤如下：

若X->a..，则将终结符ａ加入FIRST(X)中;
若X->e ,则将终结符e加入FIRST(X)中(e表示空集)；
若 X->BCD…E,则将First（B）所有元素（除了空集）加入 First（X），然后检测First（B），若First（B）中不存在空集, 即e,则停止，若存在则向B的后面查看，将First（C）中所有元素（除了空集）加入First（X），然后再检测First（C）中是否有e…直到最后，若E之前的所有非终结符的First集中都含有e,则检测到E时，将First（E）也加入First（X），若First（E）中含有e,则将 e加入First（X）。

前两条都挺容易理解的，第三条解释一下：一段文法，如果前面的非终结符号不能推出空集，那么后面的非终结符号所产生的终结符号就永远不可能成为文法的首符，于是就需要特殊考虑空集的情况。

FOLLOW集

对Follow集，其实也差不多，指的是非终结符推出的字串最末端后可能出现的所有字符的集合。还有，“#”代表识别符的后随符号
求Follow集的步骤：

对文法开始符号S,置#于FOLLOW(S)中；
对于产生式：A->aBC,将除去空集e的First（C）加入Follow（B）中;
对于产生式：A->aB或者A->aBC,(其中C可以推导出空串，C=>*e),则将Follow（A）加入Follow（B）中。

Follow（B）是B推出的串末端后的字符集合，在A->aBC的情形下，B推出串末端后的字符集，也就是C推出串首部字符的集合，即First（C）中除去e的集合。
A->aB ,那么A推出字串的末端后字符集合，与B推出字串的末端后字符集合，是等价的，FOLLOW(A) = FOLLOW(B)。
下面来个例子（e 代表空）：

E => TE`
E`=> FT`| e 
T => FT`
T`=>*FT`|e
F =>(E)|i

Follow(E) = (#,))
Follow(E`) = (#,))
Follow(T) = (#,+,))
Follow(T`) = (#,+,))
Follow(F) = (#,*,),+)

本文固定链接：http://blog.dreamchasinger.cn/?p=619
欢迎访问我的自建博客：http://blog.dreamchasinger.cn