計(jì)算文法符號X的FIRST(X)

FIRST(X)：可以從X推導(dǎo)出的所有串首終結(jié)符，如果 X=>*ε，那么ε∈FIRST(X)。

例.png

• 算法

不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符或ε可以被加入到任何FIRST集合中為止

1. 如果X是一個(gè)終結(jié)符，那么FIRST(X)={X}。
2. 如果X是一個(gè)非終結(jié)符，且X→Y1 …Yk ∈ P (k≥1)，那么如果對于某個(gè)i，a在FIRST(Yi)中且ε在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1 ...Yi-1 =>* ε) ，就把a(bǔ)加入到FIRST(X)的中。如果對于所有的j = 1,2, . . . , k，ε在FIRST(Yj)中，那么將ε加入到FIRST(X)。
3. 如果X→ε ∈P，那么將ε加入到FIRST(X)。

• 計(jì)算串 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)中。

計(jì)算非終結(jié)符A的FOLLOW(A)

FOLLOW(A)：可能在某個(gè)句型中緊跟在A后邊的終結(jié)符a的集合

FOLLOW(A)={a| S=>*αAaβ, a∈VT, α,β∈(VT∪VN)*}

如果A是某個(gè)句型的的最右符號，則將結(jié)束符“$”添加到FOLLOW(A) 中。

例.png

• 算法

不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符可以被加入到任何FOLLOW

1. 將$放入FOLLOW(S)中，其中S是開始符號$是輸入右端的結(jié)束標(biāo)記符。
2. 如果存在一個(gè)產(chǎn)生式A→αBβ，那么FIRST(β)中除ε之外的所有符號都在FOLLOW(B)中。
3. 如果存在一個(gè)產(chǎn)生式A→αB，或存在產(chǎn)生式A→αBβ且FIRST(β)包含ε，那么FOLLOW(A)中的所有符號都在FOLLOW(B)中。

注意說明：

1. 上述例子中非終結(jié)符的FIRST是已知的而終結(jié)符的FOLLOW集是未知的，因此開始時(shí)要利用已知的FIRST集去求FOLLOW集。
2. 規(guī)則2 B的FOLLOW集包含β的FIRST集（當(dāng)然ε除外）由產(chǎn)生式T→FT'以及F和T'的FOLLOW集可以驗(yàn)證該規(guī)則。FOLLOW(F)比FOLLOW(T')多出一個(gè)*
3. 規(guī)則3 FOLLOW(B)和FOLLOW(A)集是一致的？由最后E與E'和T與T'的FOLLOW集一致可以驗(yàn)證。
4. $也是終結(jié)符

表達(dá)式文法各產(chǎn)生式的SELECT 集

例.png

表預(yù)測分析

表預(yù)測分析.png