编译器笔记10-语法分析-FIRST集和FOLLOW集的计算

计算文法符号X的FIRST(X)

FIRST(X)：可以从X推导出的所有串首终结符，如果 X=>*ε，那么ε∈FIRST(X)。

例.png

• 算法

不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

1. 如果X是一个终结符，那么FIRST(X)={X}。
2. 如果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)。
3. 如果X→ε ∈P，那么将ε加入到FIRST(X)。

• 计算串 X1 X2…Xn 的FIRST 集合

1. 向FIRST(X1 X2 …Xn)加入FIRST(X1)中所有的非ε符号
2. 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推。
3. 最后，如果对所有的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

1. 将$放入FOLLOW(S)中，其中S是开始符号$是输入右端的结束标记符。
2. 如果存在一个产生式A→αBβ，那么FIRST(β)中除ε之外的所有符号都在FOLLOW(B)中。
3. 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符号都在FOLLOW(B)中。

注意说明：

1. 上述例子中非终结符的FIRST是已知的而终结符的FOLLOW集是未知的，因此开始时要利用已知的FIRST集去求FOLLOW集。
2. 规则2 B的FOLLOW集包含β的FIRST集（当然ε除外）由产生式T→FT'以及F和T'的FOLLOW集可以验证该规则。FOLLOW(F)比FOLLOW(T')多出一个*
3. 规则3 FOLLOW(B)和FOLLOW(A)集是一致的？由最后E与E'和T与T'的FOLLOW集一致可以验证。
4. $也是终结符

表达式文法各产生式的SELECT 集

例.png

表预测分析

表预测分析.png