【hit哈工大编译原理】语法分析Follow集和first集讲解
语法分析Follow集和first集讲解，需要
耐心和思考
看完了一定做题没问题，
相信我，没错滴！！！！！
对这个文法进行下列分析：
规则其实已经说的很清晰了，如下四种情况：1.假如X已经是一个终结符号了，也就是说如下面的形式求解：
求First（F），首先，F两个产生式的体，也就是F->(E)和F->id，这里面的id和(都已经是终结符了，从而F的First集就是{ ( , id }。2.假如X是一个非终结符，且X->Y1Y2Y3……Yk是一个产生式 ，且Y1不能推导出空e也就是说如下形式：
求First（T），首先，T只有一个产生式，T->FT’，按照规则，这里面的Y1就是F，Y2就是T’，先求Y1（也就是F）的First集，
上面已经求过了，可知是{ ( , id }，这里面没有空e，所以求到这里，{ ( , id }就是First（T）的集合。3.假如X是一个非终结符，且X->Y1Y2Y3……Yk是一个产生式 ，且Y1能推导出空e也就是说如下形式：
假设上面的求First（F）得到{ ( , e}，e表示空（注意这里纯属假设！！）
求First（T），首先，T只有一个产生式，T->FT’，按照规则，这里面的Y1就是F，Y2就是T’，先求Y1（也就是F）的First集，
这时候可以知道Y1（也就是First(F)）里面有空了，得再去找Y2（也就是T’的first集），如果First（T‘）里面不含空，就把First（T’）加进去，如果含空，就把空e也加进去。
那么问题来了，假如T只有一个产生式，T->FT’E呢？这时候First（T’）还是含有空，那就再加入了{First（T’）-e}之后，再求First（E），把First（E）也给加进去！！4.如果X->e是一个产生式，也就是说如下形式：
求First（E‘），首先，E‘两个产生式的体，也就是E‘->+TE’和E‘->e，含有一个产生e的产生式，所以first（E’）={ e , + } (这里的+号来自于E‘->+TE’，按照规则一得到)
下面是书上的总结：
说完了first集规则，再说一下follow集规则：
这里我的记法和下图书上的描述不太一样，但是结果都是一样的，随便你怎么记。
把规则分为三种情况：1.假如s是一个左边的符号：也就是说形如：
E->TE’，E‘->+TE’，等等
这里的E和E’就都是一个开始符号，2.假如存在A->aBp,那么First（p）除了空e之外的所有符号都在Follow（B）里面，如果First（p）包含了空e，那么Follow（A）中的符号也要加入到Follow（B）里面
也就是说形如：求解Follow（F）
这里F在右边有两个式子，T->FT’（这里的a就是空e）,T’->*FT’,（这里的a就是乘号）,出现时只有T‘跟在它的后面，
所以，根据规则，有First（T’）除了空e之外的符号都在Follow（F）里面，
而First(T’)根据上面求first集，可知：为{ 乘号，空e }，也就是包含了空，所以根据上面的规则，Follow（T’）和Follow（T）也要加入到Follow(F)里面，
也就是First(T’) U Follow（T’）U Follow（T）= {乘号，空e}-{空e} U {+，）,$} U Follow（T）
3.假如存在A->aB,那么Follow（A）中的符号要加入到Follow（B）里面
比如Follow（T‘），这里T’->*FT’，T->FT’，这两个式子里面，都是T‘结尾的，符合上面的形式，所以，要把Follow（T）加入到Follow（T’）里面，由于T‘自身就是T’，
所以Follow（T‘）=Follow（T）！
下面是书上的总结：
下面是书上给的一些例子的描述，（6）它给省略了，我写在上面的例子，Follow集的规则2里面了，看之前可以自己先理解一下。
下面是转载的一小部分内容，拓展一下：
SELECT集
1、定义：
给定上下文无关文法的产生式A→α, A∈VN,α∈V*, 若α不能推导出ε,则SELECT(A→α)=FIRST(α) 如果α能推导出ε则：SELECT(A→α)=（FIRST(α) –{ε}）∪FOLLOW(A) 需要注意的是，SELECT集是针对产生式而言的。
2、LL(1)文法：
① 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空集 其中α，β不同时能推导出ε。
② LL(1)文法的含义：
第一个L 从左到右扫描输入串
第二个L 生成的是最左推导
1 向右看一个输入符号便可决定选择哪个产生式。
③LL(1)文法的判别：当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。
3.求解示例：
1、文法G [S]为：
S→AB
S→bC
A→ε
A→b
B→ε
B→aD
C→AD
C→b
D→aS
D→c
求每个产生式的SELECT集，并判断文法G是否为LL(1)文法？
解：SELECT(S→AB)=（FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}
SELECT(S→bC)=FIRST(bC)={b}
SELECT(A→ε)=(FIRST(ε) -{ε})∪FOLLOW(A)={a,c,#}
SELECT(A→b)=FIRST(b)={b}
SELECT(B→ε)=(FIRST(ε) -{ε})∪FOLLOW(B)={#}
SELECT(B→aD)=FIRST(aD)={a}
SELECT(C→AD)=FIRST(AD)={a,b,c}
SELECT(C→b)=FIRST(b)={b}
SELECT(D→aS)=FIRST(aS)={a}
SELECT(D→c)=FIRST©={c}
由以上计算结果可得相同左部产生式的SELECT交集为：
SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩{b}={b}≠ф
SELECT(A→ε)∩SELECT(A→b)={a,c,#}∩{b}=ф
SELECT(B→ε)∩SELECT(B→aD)={#}∩{a}=ф
SELECT(C→AD)∩SELECT(C→b)＝{b,a,c}∩{b}＝{b}≠ф
SELECT(D→aS)∩SELECT(D→c)={a}∩{c}＝ф
由LL(1)文法定义知该文法不是LL(1)文法，因为具有相同左部其产生式的SELECT集的交集不为空。
小结：
1、Select集的作用是将first集和follow集进行合并，如果两个文法的左端都是A，若他们的select集交集为空，表明他们是两个无关的，不会产生不确定性的文法，反之，则表明文法不是LL(1)文法。