如何计算first集合

关于First集合、Follow集合以及select集合的求法 First集合：定义：令X为一个文法符号（终止符或非终止符）或ε，则集合First（X）有终止符组成，此外可能还有ε，它的定义如下： 1. 若X是终止符或ε，则First（X）= {X}。 2. 若X是非终结符，则对于每个产生式X—>X1X2…Xn，First（X）包含了First（X1）-{ε}。若对于某个i n，所有的集合First（X1），... ，First（Xi）都包含了ε，则First（X）也包 括了First（Xi+1）- {ε}。若所有集合First（X1），...，First（Xn）都包括了ε，则First（X）也包括了ε。 Follow集合：给出一个非终结符A，那么集合Follow（A）则是由终结符组成，此外可能还含有#（#是题目约定的字符串结束符）。集合Follow（A）的定义如下： 1. 若A是开始符号，则#在Follow（A）中。 2. 若存在产生式B—>αAγ，则First（γ）- {ε}在Follow（A）中。 3. 若存在产生式B—>αAγ，且ε在First（γ）中，则Follow（A）包括Follow（B）。 Select集合：对于产生式A—>α。集合select（A—>α）定义如下： 1. 若α不能推出ε，则select（A—>α） = first（α）。 2. 若α能推出ε，则select（A—>α）= first（α）∪ follow(A)。具体例题：判段G1[E]是否是LL（1）文法。 G1[E]：E ? －E | [ E ] | V F F ? －E | ε V ? t X X ? [ E ] | ε 说明：其中，终结符号集 = {t, [ , ] , －}。解：G1[E]：E ? －E ①| [ E ] ②| V F③ F ? －E ④| ε ⑤ V ? t X ⑥ X ? [ E ] ⑦| ε ⑧ Select（①） = first（-E）= {-} (1)//因为-是终止符，所以－E不能为空。 Select（②）= first（[E]） = {[} (2) //理由同上 Select(③) = first(VF) = {t} (3)//VF的第一个符号V是非终止符，故要判断V的first集，由产生式⑥只V的first集为{t}，故first（VF）= {t}。 Select（④）= first（-E）= {-} (4) Select（⑤）= follow（F）= {], #} (5)//产生式⑤中的α为ε（即空），故等于Follow（F）。由产生式③知F后为空，故E的follow集也包含在F的follow集中（理由见follow集定义第三条）。再看E的follow集。首先E是开始符，故“#”在follow（E）中，又由②或⑦知“]”也在follow（E）中。故Select(③) = {}，#}。 Select（⑥）= first（tX）= {t} (6) Select（⑦）= first（[E]）= {[} (7) Select（⑧）= follow（X）= {-,],#} (8) //求X的follow集，由⑥知V的follow集在follow（X）中，又由③知first（F）- {ε }在follow（X）中，又由⑤知ε 在first（F）中（或者可以认为F可以推出ε ），故follow（F）也在follow（X）中（follow集定义第三条）。所以Select（⑧）= {-,],#}。因为同一个非终止符的不同产生式（即①②③，④⑤，⑥，⑦⑧这四组）所对应的select集(即(1)(2)(3),(4)(5),(6),(7)(8))都没有交集，所以该文法是LL(1)文法。此文引用magiczgz

下面我将介绍一下我关于LL（1）文法部分的计算文法非终结符First集以及Follow集两个知识点的理解。

首先是First集的计算部分，计算First集首先看我们原文法的左边，原文法左边不重复的都要进行First集的计算，计算时具体有以下三种情况：

（1）先看产生式后面的第一个符号，如果是终结符，那就可以直接把它写到这个产生式的First集中，例如：产生式为M->nDc,那在First集中我们就可以直接写上First (M)={ n }；

（2）如果产生式后面的第一个符号是非终结符，就看这个非终结符的产生式，看的时候同样利用前面的两种看法；但是当产生式为ε时，则需要把ε带入到待求First集的元素的产生式中再判断。例如：A->Bc； B->aM；B->ε，求First(A)时，我们看到A的第一个产生式中的第一个符号是B，B是一个非终结符，所以我们就要接着看B的产生式，B的第一个产生式的第一个符号为a，a是一个终结符，直接把a写入First(A)，B的第二个产生式为ε，把ε带入A->Bc中，A->c(注意：如果将B->ε带入表达式后A的产生式为A->ε，ε不可以忽略)，c是终结符，所以把c也写入First(A)，最后First (A)={ a，c }。

（3）当产生式右边全为非终结符，且两个非终结符又都可以推出ε时，我们需要把这个产生式的所有情况都列出来，再分析。例如：A->BCB->b|εC->c|ε。我们把A的所有产生式利用上述两种方法列出来就是A->bc,A->bA->c,A->ε最后First (A)={b,c, ε}。

接下来介绍一下Follow集的部分，先简单介绍一下计算Follow集的大致规则。比如我们要求Follow(X)，文法中多个产生式中含有X，则需要考虑多种情况，以下是具体计算时的三种情况：

（1）文法开始符：所有文法开始符的Follow集中都有一个#。

（2）S->αB的形式：求Follow(B)，因为B的后面为空，把Follow(S)写入B的Follow集中。

（3）S->αBβ的形式：求Follow(B)，B后部不为空。

①当β是终结符时，直接把β写入Follow(B)。

②当β是非终结符时，将First (β)（如果First(B)中有ε，就把ε删掉）写入Follow(B)中。（需要注意的是：如果β->ε，那么原产生式就变成了S->αB,也就是第二种情况，这两种情况都要算在Follow(B)中）。

---