编译原理follow集与first集的计算

下面我将介绍一下我关于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)中）。

三，FIRST集求法

First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。

1. 直接收取：对形如U－>a…的产生式（其中a是终结符），把a收入到First(U)中

2. 反复传送：对形入U－>P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中【意思就是只需要把第一个非终结符的First集传过去~这个地方是要注意的地方，也是难点】。

四，FOLLOW集的求法

Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。注意Follow集合是从开始符号S开始推导。

1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。因a是紧跟在U后的终结符。

2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)直接收入到Follow(U)中【在这里，如果First（P）中有空字符，那么就要把左部（假设是S）的Follow（S）送入到Follow（U）中。还有就是Follow集中是没有空字符的】。

3. 直接收取：若S－>…U，即以U结尾，则#∈Follow(U)

4．*反复传送：对形如U－>…P的产生式（其中P是非终结符），应把Follow(U)中的全部内容传送到Follow(P)中。

---