FISRT 集和 FOLLOW 集

#FIRST 集

$FIRST(\alpha)$ 是从 $\alpha$ 推导出的串的起始终结符的集合。

特殊情况：$\alpha\Rightarrow^{*}\varepsilon$ 时，规定 $\varepsilon\in FIRST(\alpha)$

若$X \rightarrow a...$，则将终结符 $a$ 加入 $FIRST(X)$ 中；
若$X \rightarrow\varepsilon$，则将 $\varepsilon$ 加入 $FIRST(X)$ 中；
若$X \rightarrow Y...$，且 $Y$ 属于非终结符，则将 $FIRST(Y)-\lbrace \varepsilon \rbrace$ 加入到 $FIRST(X)$ 中；
若$X \rightarrow Y_1Y_2...Y_K$,且 $Y_1,Y_2,..Y_{i-1}$ (2$\leqslant$i$\leqslant$k) 都是非终结符，且 $Y_1,Y_2,...Y_{i-1}$ 的 FIRST 集合中均包含 $\varepsilon$，则将 $FIRST(Y_j)$ 的所有非 $\varepsilon$ 元素加入到 $FIRST(X)$ 中，$(j=1,2,...i)$。特别地，若 $Y_1 \backsim Y_K$ 均有 $\varepsilon$ 产生式，则将 $\varepsilon$ 加到 $FIRST(X) 中。

FISRT 集中有 $\varepsilon$。

$FOLLOW(\alpha)$ 是在所有句型中紧跟在 $\alpha$ 后面的终结符集合。

特殊情况：如果 A 是某个句型的最右符号 $(S\Rightarrow^{*}\beta A)$，那么终结符 💲 属于 FOLLOW(A)。

对文法的开始符号 S，将 💲 加入到 FOLLOW(S) 中。
若有 $A\rightarrow\alpha B\beta$，则将 FIRST($\beta$)$-${$\varepsilon$} 加入到 FOLLOW(B) 中。$\alpha$ 可以为空串。
若 $A\rightarrow\alpha B$或$A\rightarrow\alpha B\beta$，且 $\beta\Rightarrow^{*}\varepsilon$，则将 FOLLOW(A) 加入 FOLLOW(B) 中。$\alpha$ 可以为空串。

FOLLOW 集中没有 $\varepsilon$。

安利一个求 FISRT 集和 FOLLOW 集的工具：Toolbox