FIRST集和FOLLOW集的定义和计算方法

FIRST集的定义: 如果α是任意的文法符号串,则我们定义FIRST(α)是从α推导出的串的开始符号的终结符集合，即

FIRST(α)={a|α a… ,a是终结符}。如果α ε,则ε也属于FIRST(α)。

FOLLOW集的定义: 设A是一个非终结符,则定义FOLLOW(A)是包含所有在句型中紧跟在A后面的终结符a的集合，即FOLLOW(A)={a|S αAaβ , a是终结符}。注意，在推导的某一时刻，在A和a之间可能有符号，但如果是这样，它们将推导出ε并消失。如果A是某个句型的最右符号，那么$属于FOLLOW(A)。(注: $是输入串的结束符)

 

FIRST集的计算:

    首先，为了计算单个文法符号X的FIRST(X)，可以应用下列规则，直到没有终结符或ε可加到某个FIRST集合为止：

    1. 如果X是终结符，则FIRST(X)是 { X }。

    2. 如果X –> ε 是一个产生式，则将ε加到FIRST(X)中。

    3. 如果X是非终结符，且X –> Y₁Y₂…Y_k是一个产生式,其中k≥1。则当某终结符a∈FIRST(Y_i),(1<i≤k)且

        ε∈FIRST(Y₁),ε∈FIRST(Y₂)…,ε∈FIRST(Y_i-1)时，就把a加入到FIRST(X)中去，换句话说就是

        Y₁Y₂…Y_i-1 ε 。如果ε∈FIRST(Y_j) 其中j=1,2,…,k，就把ε也加入FIRST(X)中。

     知道了如何计算单个文法符号的FIRST集，那么我们就可以计算一组文法符号串的FIRST集。假设这一组文法符号串由X₁X₂…X_n构成。首先将集合FIRST(X₁)中的除ε的终结符号加入FIRST(X₁X₂…X_n).依次，如果

ε∈FIRST(X₁)，那么将集合FIRST(X₂)中除ε的终结符号也加入FIRST(X₁X₂…X_n),依次类推。最后，如果X₁,X₂,…X_n中每一个文法符号的FIRST集当中都有ε,那么把ε也加入到FIRST(X₁X₂…X_n)中。

 

FOLLOW集的计算:

     为了计算文法中每一个非终结符X的FOLLOW(X)，应用如下的三条规则，直到没有任何一个终结符能被添加到任何非终结符的FOLLOW集当中为止。

    1. 如果S是文法的开始符号,那么把$添加进FOLLOW(S)中。($是输入串的结束符)

    2. 如果有一个产生式A->αBβ，那么将集合FIRST(β)中除ε外的所有元素加入到FOLLOW(B)当中。

    3. 如果有一个产生式 A->αB , 或者A->αBβ且FIRST(β)中包含ε , 那么将集合FOLLOW(A)中的所有元素

       加入到集合FOLLOW(B)中。