一、FIRST集的定义

---

α的FIRST集，即FIRST(α)被定义为：可从α推导得到的串的首符号的集合，其中α是任意的文法符号串。如果α经过若干步的推导得到一个ε，那么ε也在FIRST(α)中。

比如： ①A=>cγ A可以推导出cγ这个串，这个串的首符号为c，因此c在FIRST(A)中。

②E=>+TE|ε E可以推导出+TE，而+TE的首符号为+，并且E经过推导之后可以得到一个ε，因此+、ε在FIRST(E)中，即FIRST(E)={+, ε}。

二、FIRST集的计算方式

计算各个文法符号X的FIRST(X)时，不断应用下列规则，直到再没有新的终结符号或ε可以被加入到任何FIRST集合中为止。 1）如果X是一个终结符号，那么FIRST(X) = X，即FIRST(a) = a

2）如果X是一个非终结符号，且X—>Y1Y2…Yk是一个产生式，其中k>=1，那么如果对于某一个Yi，它的产生式的首字符为一个终结符(比如为a)，且FIRST(Y1)、FIRST(Y2)、…、FIRST(Yi-1)中都有ε，那么就把a加到FIRST(X)中。

3）如果X是一个非终结符号，且X—>Y1Y2…Yk是一个产生式，其中k>=1。如果对于所有的j=1，2，3，…，k，   ε在FIRST(Yj)中，那么将ε加入到FIRST(X)中。

4）如果X—>ε是一个产生式，那么将ε加入到FIRST(X)中。

现在，我们可以计算串X1X2…Xn的FIRST集合。先向FIRST(X1X2…Xn)加入F(X1)中所有的非ε符号。如果ε在FIRST(X1)中，再加入FIRST(X2)中所有非ε符号。如果ε在FIRST(X2)，那么再加入FIRST(X3)中所有非ε符合，以此类推。如果对于所有的i，ε都在FIRST(Xi)中，那么就将ε添加到FIRST(X1X2…Xn)中。

FIRST集计算的伪代码实现

//对于每一个非终结符号，都进行初始化 foreach(nonterminal T) FIRST(T) = {} //如果有FIRST集在变化，那么就继续进行循环，直到所有的FIRST集合都不变 while(some set is changing) foreach(production P:N->β1...βn)//遍历N的每一条产生式 foreach(βi from β1 upto βn)//对于每一条产生式从左往右遍历 if(βi == a...)//如果βi首字符是一个终结符 FIRST(N) U= {a}//把a添加到N的FIRST集合中 if(βi == M...)//如果βi的首字符是一个非终结符 FIRST(N) U= FIRST(M)//把M的FIRST集添加到N的FIRST集中 if(M is not in NULLABLE)//如果M不能推导出ε //如果M可以推导出ε，那么要继续循环，对下一个符号进行判断 break;//跳出最内层的循环，进行一下条产生式的判断

三、FIRST集实例分析

我们给出一个文法G(E)： ①E → TE’ ②E’ → +TE’ ③E’ →ε ④T → F T’ ⑤T’ → *F T’ ⑥T’ →ε ⑦F → （E） ⑧F → id

首先，我们分析能推出ε的文法符号，它们为：{E’，T’ }

有上述的伪代码可知，一开始我们先进行初始化，因此每一个左侧非终结符号的FIRST集都为空。

N\FIRST0123E{ }E’{ }T{ }T’{ }F{ }

下面进行第一轮的迭代： 我们看第①个产生式：E → TE’ 首符号为T，T为非终结符，此时表中T的FIRST集为{}，因此，此时E的FIRST集仍为{}。

N\FIRST0123E{ }{ }E’{ }T{ }T’{ }F{ }

我们看第②个产生式：E’ → +TE’ 首符号为+，+为终结符，因此把+添加到E’的FIRST集中。

N\FIRST0123E{ }{ }E’{ }{+}T{ }T’{ }F{ }

我们看第③个产生式：E’ →ε 由规则4）可知，此时应将ε添加到E’的FIRST集中。

N\FIRST0123E{ }{ }E’{ }{+，ε}T{ }T’{ }F{ }

第④个产生式：T → F T’ 首符号为F，此时FIRST(F) = {}，因此FIRST(T) = {}。

N\FIRST0123E{ }{ }E’{}{+，ε}T{ }{ }T’{ }F{ }

第⑤个产生式：T’ → *F T’ 首符号为*，是一个终结符号，因此FIRST(T’) U= { * }。

N\FIRST0123E{ }{ }E’{ }{+，ε}T{ }{ }T’{ }{*}F{ }

第⑥个产生式：T’ →ε与第③个产生式同理：将ε添加到T’的FIRST集中。

N\FIRST0123E{ }{ }E’{ }{+，ε}T{ }{ }T’{ }{*，ε}F{ }

第⑦个产生式：F → （E） 首符号为（是一个终结符号，因此直接添加到FIRST(F)中。

N\FIRST0123E{ }{ }E’{ }{+，ε}T{ }{ }T’{ }{*，ε}F{ }{（}

第⑧个产生式：F → id 首符号为id是一个终结符号，因此直接添加到FIRST(F)中。

N\FIRST0123E{ }{ }E’{ }{+，ε}T{ }{ }T’{ }{*，ε}F{ }{（，id}

一轮循环之后，我们发现FIRST集发生了变化，因此我们需要继续进行一次迭代。

还是从第①个产生式E → TE’开始看起，此时首符号T的FIRST集仍然为空，因此E的FIRST集还是为{}。

N\FIRST0123E{ }{ }{ }E’{ }{+，ε}T{ }{ }T’{ }{*，ε}F{ }{（，id}

第②、③个产生式与第一次时一样

N\FIRST0123E{ }{ }{ }E’{ }{+，ε}{+，ε}T{ }{ }T’{ }{*，ε}F{ }{（，id}

第④个产生式T → F T’，首符号为F，此时FIRST(F)为{（，id}，因此FIRST(T) U= FIRST(F)，而F无法推出ε，因此不用继续看F的后跟符号T’。

N\FIRST0123E{ }{ }{ }E’{ }{+，ε}{+，ε}T{ }{ }{（，id}T’{ }{*，ε}F{ }{（，id}

第⑤、⑥、⑦、⑧产生式与上一次一样

N\FIRST0123E{ }{ }{ }E’{ }{+，ε}{+，ε}T{ }{ }{（，id}T’{ }{*，ε}{*，ε}F{ }{（，id}{（，id}

此时FIRST(T)中发生了变化，所以我们还要继续进行迭代

还是从第一个产生式E → TE’看起，首符号T的FIRST集此时不再为{ }，因此要把FIRST(T)中的元素添加到FIRST(E)中。

N\FIRST0123E{ }{ }{ }{（，id}E’{ }{+，ε}{+，ε}T{ }{ }{（，id}T’{ }{*，ε}{*，ε}F{ }{（，id}{（，id}

之后的产生式，产生的FIRST集并没有发生变化，所以这一次迭代之后，只有FIRST(E)发生了改变。

N\FIRST0123E{ }{ }{ }{（，id}E’{ }{+，ε}{+，ε}{+，ε}T{ }{ }{（，id}{（，id}T’{ }{*，ε}{*，ε}{*，ε}F{ }{（，id}{（，id}{（，id}

因为FIRST(E)发生了变化，所以我们还要进行一次迭代，这一次迭代后我们会发现与上一次迭代的结果完全相同，也就是所有的FIRST集都没有发生改变，所以迭代结束。 ∴最终的结果为：

NFIRST(N)E{（，id }E’{+，ε }T{（，id }T’{*，ε }F{（，id }