Epsilon 集

给定文法 $G$, $\mathrm{EPS}$ 集定义为全体可经 0 步或者多步推导出空字符串的语法符号串的集合。

注: EPS 集一定是对于某个文法 $G$ 而言的，因为要判断一个文法符号串 $\alpha$ 能否推出空串，还要考虑文法中的语法产生式是如何定义的。

举例：考虑文法 $G$ 中的产生式

E ::= T E'
E' ::= + T | - T | eps

则，E’ 属于 $\mathrm{EPS}$.

First 集

给定文法 $G$, 文法符号串 $\alpha$ 的 First 集 $\mathrm{FIRST}(\alpha)$ 定义为 $\alpha$ 能够经 0 步或多步推导得到的字符串的首字符的集合。

举例：考虑文法 $G$ 中的产生式

E ::= T E'
E' ::= plusMinus T | eps
T ::= F T'
T' ::= timesDivide F | eps
F ::= number | id

则，number, id 属于 $\mathrm{FIRST}(\texttt{T})$, 也属于 $\mathrm{FIRST}(\texttt{T})$.

当 $|\alpha| > 1$, 并且首个文法符号属于 $\mathrm{EPS}$, 则情况稍微有些微妙：

考虑 $\mathrm{FIRST}(\texttt{T'E})$, 由于 $\texttt{T'} \in \mathrm{EPS}$, 所以 $\mathrm{FIRST}(\texttt{T'E}) = \mathrm{FIRST}(\texttt{T'}) \cup \mathrm{FIRST}(\texttt{E})$. 将 $\texttt{E}$ 替换为更一般的语法串（长度是 0 或者非 0）$\beta$, 该式子也是成立的，只要首符号能够推出空串。

Follow 集

给定文法 $G$, 文法符号 $\texttt{A}$ 的 Follow 集 $\mathrm{FOLLOW}(\texttt{A})$定义为

$$ \{ a | \alpha \Rightarrow \beta A a \in G \} $$

也就是说，若存在 $G$ 中的句式 $\alpha$, 它能经 1 步或多步推导得到句式 $\beta A a$, $a$ 是终结符，则 $a \in \mathrm{FOLLOW}(\texttt{A})$.

举例：考虑文法 $G$ 中的产生式

T ::= F T'
T' ::= * F | / F | eps
F ::= number | id

则显然 $\{ \texttt{*}, \texttt{/} \} \subset \mathrm{FOLLOW}(\texttt{F})$.