编译原理题型总结笔记

三个集合的求法

First 集

找到这个左部是该非终结符的展开式，看得到的第一个项。如果得到的是终结符，就加入 First 集；否则继续递归查询；如果得到的是 $\varepsilon$，就也加进来。First 可以有空串。

Follow 集

按下面的步骤来做：

1. 输入符首先有 $\#$。
2. 看右部，找到该非终结符，如果它后面跟着终结符，则把这个终结符加入 Follow 集；否则加入后面这个非终结符的 First 集减去 $\varepsilon$。
3. 看右部，找到该终结符，如果它后面的非终结符能够消失变成 $\varepsilon$，或者它后面没东西，那就加入左部的 Follow 集。

Follow 集不会有空串。

Predict 集

对于：

$$A\to b\dots$$

就是求 $\text{Predict}(A\to b\dots)=\begin{cases}\text{First}(b)&, \varepsilon\notin\text{First}(b)\\ [\text{First}(b)-\varepsilon]\cup\text{Follow}(A)&, \varepsilon\in\text{First}(b) \end{cases}$。

参考和注解