FIRST集
对$\alpha \in (V_T\bigcup V_N)^*$，有
$$ FIRST(\alpha)＝\{a|\alpha \stackrel{*}\Longrightarrow a \cdot \cdot \cdot, a\in V_T\} $$
特别的，若$\alpha \stackrel{*}\Longrightarrow \varepsilon$，则$\varepsilon \in FIRST(\alpha)$
因此对于每一文法符号$X\in{V_T}\bigcup{V_N}$，构造$FIRST(X)$的方法为:
使用下列规则，直至每个$FIRST$集不再增大为止：
- 若$X\in V_T$，则$FIRST(X)={X}$(意思是如果X是终结符，则其FIRST集合为其自身)；
若$X\in V_N$，那么$X$的产生式分以下三种情况:
- $X \to \varepsilon$，则$\varepsilon \in FIRST(X)$
- $X \to a \cdot \cdot \cdot$，则$a \in FIRST(X)$
- $X \to Y \cdot \cdot \cdot$，则$FIRST(Y) – \{\varepsilon\} \subseteq FIRST(X)$
- 特例:$X \to Y_1Y_2 \cdot \cdot \cdot Y_i$,且$Y_1,Y_2,\cdot \cdot \cdot Y_{i-1} \stackrel{*}\Rightarrow \varepsilon$,则$FIRST(Y_i) \subseteq FIRST(X)$
针对最后的特列，用文字说明一下，比方说
$$ A \to BCD \\ B \to b| \varepsilon\\ C \to c|\varepsilon\\ D \to d $$
那么FIRST(A)={b,c,d}，为什么会有c和d，就是因为B可以产生$\varepsilon$，此时相当于$A \to CD$，又因为C也可以产生$\varepsilon$，所以相当于$A \to D$
例题
$$ S \to MH|a \\ H \to LSo| \varepsilon\\ K \to dML| \varepsilon\\ L \to eHf \\ M \to K|bLM $$
计算所有非终结符的FIRST集
FIRST(S)={a,d,b,e,$\varepsilon$}
FIRST(H)={$\varepsilon$,e}
FIRST(K)={d,$\varepsilon$}
FIRST(L)={e}
FIRST(M)={d,b,$\varepsilon$}
FOLLOW集
我学FOLLOW集的时候，看了很多资料，书，博客，别的学校的慕课，感觉讲的都不是很好，没有一阵见血，所以我在这必须要总结一下
就三步：
- 设S为文法的开始符号，把(#)加入FOLLOW(S)中
- 若$A \to \alpha B \beta$是一个产生式，则把$FIRST(\beta)$的非空元素加入$FOLLOW(B)$中
- $A \to \alpha B \beta$，如果$\beta \stackrel{*}\Longrightarrow \varepsilon$，则把$FLLOW(A)$也加入到$FOLLOW(B)$中
用两句话总结就是：
- 如果求的$FOLLOW(A)$中A是语法的开始符号，则无条件将#加入到$FOLLOW(A)$中。
- 如果求$FOLLOW(A)$，先将所有产生式中直接跟在A右边的非终结符的FIRST集（不包括$\varepsilon$）加入FOLLOW(A)。如果该非终结符能通过n(n≥0)次推导出$\varepsilon$或A右边就没有任何符号，则把产生式左部的FOLLOW集也加入到FOLLOW(A)中。
例题
$$ S \to MH|a \\ H \to LSo| \varepsilon\\ K \to dML| \varepsilon\\ L \to eHf \\ M \to K|bLM $$
计算所有非终结符的FOLLOW集
先说FOLLOW(S)，因为S是语法的开始符号，并且S在第二个产生式右边是个终结符o，所以FOLLOW(S)就确定了
$$ FOLLOW(S)=\{o,\#\} $$
然后看FOLLOW(H)，因为H作为产生式右部只有产生式1和产生式4，产生式1中H的右边是空，所以要将FOLLOW(S)加入到FOLLOW(H)中，产生式4中H的右边是终结符f。最终FOLLOW(H)就确定了
$$ FOLLOW(H)=\{o,\#,f\} $$
最后再说一个例子——FOLLOW(L)，L作为产生式右部有产生式2，产生式3，产生式5。在产生式2中，L的右边紧跟着非终结符S，所以将FIRST(S)中的非空元素加入到FOLLOW(L)中，$FOLLOW(L)=FOLLOW(L)\bigcup \{FIRST(S)-\{\varepsilon\}\}$。在产生式3中L右边是空，所以将FOLLOW(K)加入到FOLLOW(L)中。在产生式5中，L右边是M，所以将FIRST(M)中的非空元素加入到FOLLOW(L)中
剩下的非终结符的FOLLOW集也是相同的方法求，因为一次扫描可能不够，比方说上面求FOLLOW(L)需要FOLLOW(K)，但是FOLLOW(K)暂时没求，所以要等第二次扫描L的时候才能加进来。
答案：
$$ FOLLOW(S)=\{\#,o\}\\ FOLLOW(M)=\{e,\#,o\}\\ FOLLOW(H)=\{\#,f,o\}\\ FOLLOW(L)=\{a,b,d,e,o,\#\}\\ FOLLOW(K)=\{e,\#,o\} $$
