編譯原理（五）

（一）FIRST集和FOLLOW集的計算

1.計算文法符號X的FIRST(X )

FIRST ( X )：可以從X推導出的所有串首終結符構成的集合

如果 X=>* ε，那麼 ε∈FIRST ( X )

（1）首先觀察產生式的右部，如果有終結符，直接把終結符加入First集中，這裡產生式2，4，5可以直接看出該式由終結符開頭，所以把開頭的終結符分別加入到各自的First集中。

① E → TE FIRST ( E ) = { }

② E → +TE |ε FIRST ( E ) = { + }

③ T → FT FIRST ( T ) = { }

④ T → *FT |ε FIRST ( T ) = {* }

⑤ F → (E)|id FIRST ( F ) = {( id }

（2）繼續觀察可以發現產生式2，4可以直接推出空串，根據定義，把空串加入到各自的First集中。

① E → TE FIRST ( E ) = { }

② E → +TE |ε FIRST ( E ) = { + ε }

③ T → FT FIRST ( T ) = { }

④ T → *FT |ε FIRST ( T ) = {* ε }

⑤ F → (E)|id FIRST ( F ) = { ( id }

（3）接著觀察產生式右部，發現剩下的產生式均以非終結符開頭，那麼產生式右部開頭的第一個非終結符中所有終結符都是該該式左部可以推導出的串首終結符。例如第一個產生式中的E的First集，就是該式右部第一個非終結符T中的First集中的終結符都是E可以推導出的首終結符，當然此時T的first集為空。

① E → TE FIRST ( E ) = { }

② E → +TE |ε FIRST ( E ) = { + ε }

③ T → FT FIRST ( T ) = { }

④ T → *FT |ε FIRST ( T ) = {* ε }

⑤ F → (E)|id FIRST ( F ) = { ( id }

（4）繼續看第三個產生式，這時我們可以把F的first集中的所欲元素都加入到T的first集中。

① E → TE FIRST ( E ) = { }

② E → +TE |ε FIRST ( E ) = { + ε }

③ T → FT FIRST ( T ) = { ( id }

④ T → *FT |ε FIRST ( T ) = {* ε }

⑤ F → (E)|id FIRST ( F ) = { ( id }

（5）此時T的first中有了元素，因此可以把T的first集中的元素加入到E的first集中。

① E → TE FIRST ( E ) = { ( id }

② E → +TE |ε FIRST ( E ) = { + ε }

③ T → FT FIRST ( T ) = { ( id }

④ T → *FT |ε FIRST ( T ) = { * ε }

⑤ F → (E)|id FIRST ( F ) = { ( id }

2.計算非終結符A的FOLLOW(A)

FOLLOW(A)：可能在某個句型中緊跟在A後邊的終結符a的集合

FOLLOW(A)={a| S =>* αAaβ, a∈Vt，α,β∈(Vt∪Vn)*}

如果A是某個句型的的最右符號，則將結束符「$」添加到FOLLOW(A)中

我們如果要計算T的Follow集，那麼跟在T後的E 的First集中的所有元素都是T的Follow集中的元素。

（1）首先看第一個產生式，文法的開始符號E，既是一個句型，又是該句型的最右符號，因此需要把$符號加入到E的Follow集中

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { }

(2)繼續觀察①產生式的右部，非終結符T後面跟著非終結符E，此時應把E的Fisrt集中的+加入到T的Follow集中。

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { + }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { }

（3）接下觀察T後面的E ，由於E 的First集中存在空串，也就是說E 可以為空，那麼跟在E後面的符號都能跟在T後面。此時把$ 添加到T的Follow集中。

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { + $ }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { }

（4）繼續觀察E，由於E是產生式右部最後一個符號，那麼能跟在E後面的符號，也能跟在E後面。此時把$ 添加到E的Follow集中。

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { $ }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { + $ }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { }

(5)由於第二個產生式和第一個產生式類似，所以結果也是一樣的。

(6)接下來看第三個產生式，該式和第一個產生式類型相仿不做贅述。

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { $ }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { + $ }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { + $ }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { * + $ }

(7)第五個產生式中，E後面跟著終結符 )，把 ）加入到 E的Follow集中。

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ ） }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { $ }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { + $ }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { + $ }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { * + $ }

（8）進行多次依賴更新最終得到完整的 Follow集。

① E → TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ ） }

② E → +TE |ε FIRST ( E ) = { + ε } FOLLOW( E) = { $ ） }

③ T → FT FIRST ( T ) = { ( id } FOLLOW( T ) = { + $ ） }

④ T → *FT |ε FIRST ( T ) = { * ε } FOLLOW( T ) = { + $ ） }

⑤ F → (E)|id FIRST ( F ) = { ( id } FOLLOW( F ) = { * + $ ） }

3.表達式文法各產生式的SELECT集

（1）根據定義，第一個產生式中的select集應該是產生式右部第一個非終結符T的First集

（2）第二個產生式，由於產生式的右部為一個終結符，所以第二個產生式的Selec集應該為該終結符

（3）第三個產生式為一個空產生式，所以該產生式的Select集就為E 的Follow集

（4）最終得到下圖

（5）觀察上圖，可以發現，產生式2，3具有相同的左部，但它們的select集並不相交，

產生式5，6也具有相同的左部，select集也不相交，因此該文法為LL（1）文法。

（6）由select可以構造相應的預測分析表，預測分析表的每一行對應一個非終結符，每一列，對應一個輸入符號

（7）觀察上圖1第一行，產生式的select集為｛（，id｝，也就是說E遇見（，id 時可以選用該產生式。