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\} $$
