计算文法符号X的FIRST(X)
FIRST(X)：可以从X推导出的所有串首终结符，如果 X=>*ε，那么ε∈FIRST(X)。
例.png
- 算法
不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止
- 如果X是一个终结符，那么FIRST(X)={X}。
- 如果X是一个非终结符，且X→Y1 …Yk ∈ P (k≥1)，那么如果对于某个i，a在FIRST(Yi)中且ε在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1 ...Yi-1 =>* ε) ，就把a加入到FIRST(X)的中。如果对于所有的j = 1,2, . . . , k，ε在FIRST(Yj)中，那么将ε加入到FIRST(X)。
- 如果X→ε ∈P，那么将ε加入到FIRST(X)。
- 计算串 X1 X2…Xn 的FIRST 集合
- 向FIRST(X1 X2 …Xn)加入FIRST(X1)中所有的非ε符号
- 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推。
- 最后，如果对所有的i，ε都在FIRST(Xi)中，那么将ε加入到FIRST(X1 X2 …Xn)中。
计算非终结符A的FOLLOW(A)
FOLLOW(A)：可能在某个句型中紧跟在A后边的终结符a的集合
FOLLOW(A)={a| S=>*αAaβ, a∈VT, α,β∈(VT∪VN)*}
如果A是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A) 中。
例.png
- 算法
不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW
- 将$放入FOLLOW(S)中，其中S是开始符号$是输入右端的结束标记符。
- 如果存在一个产生式A→αBβ，那么FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中。
- 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中。
注意说明：
- 上述例子中非终结符的FIRST是已知的而终结符的FOLLOW集是未知的，因此开始时要利用已知的FIRST集去求FOLLOW集。
- 规则2 B的FOLLOW集包含β的FIRST集（当然ε除外）由产生式T→FT'以及F和T'的FOLLOW集可以验证该规则。FOLLOW(F)比FOLLOW(T')多出一个*
- 规则3 FOLLOW(B)和FOLLOW(A)集是一致的？由最后E与E'和T与T'的FOLLOW集一致可以验证。
- $也是终结符
表达式文法各产生式的SELECT 集
例.png
表预测分析
表预测分析.png
