編譯原理：FIRST集、FOLLOW集、SELECT集的求法及LL（1）文法的判定——篇②FOLLOW集的求法

FIRST集求法參照篇①添加連結描述

本篇參考連結：添加連結描述

FOLLOW集

① FOLLOW（A）可能在某個句型中緊跟在A後邊的終結符的集合，若A是某句型的最右符号，則将結束符#添加到 FOLLOW（A）中。

②若存在A→αBβ，那麼FIRST（β）中除ε之外的所有符号放入FOLLOW（B）；

若存在A→αB或 A→αBβ且FIRST（β）包含ε，那麼FOLLOW（A）中所有符号都在FOLLOW（B）中。

求FOLLOW集時有兩種方法：第一種是上文①的概念法，第二種是上文②的公式法，接下來将通過兩個例子，分别講述這兩種方法的用法。

例子1：

設有文法G【A】：

① E -> TE’

② E’ -> +TE’|ε

③ T -> FT’

④ T’ -> *FT’|ε

⑤ F -> (E)|id

觀察以上五個式子，基本符合A→αBβ，是以在此情況下，可以使用②公式法，隻需直接套公式即可，具體步驟如下：

對于①：E是句型的最右符号，則将結束符#添加到 FOLLOW（E）中，又F → (E)|id，緊跟在A後邊的終結符為“）”，是以FOLLOW(E)= { # , ) }；又因為 E → TE’，存在A→αB（T對應α，E’對應B），那麼FOLLOW（E）中所有符号都在FOLLOW（E’）中，是以 FOLLOW(E’)= { # , ) }；

對于②： E’→ +TE’|ε，存在A→αBβ（+對應α，T對應B，E’對應β），是以FIRST（E’）中除ε之外的所有符号放入FOLLOW（T），又因為FIRST（E’）包含ε，那麼FOLLOW（E’）中所有符号都在FOLLOW（T）中，FOLLOW(T)= { +，# , ) }；

對于③：T → FT’，存在A→αB（F對應α，T’對應B），那麼FOLLOW（T）中所有符号都在FOLLOW（T’）中，是以FOLLOW(T’)= {+， # , ) }；

④與②同類型，是以FIRST（T’）中除ε之外的所有符号放入FOLLOW（F），FOLLOW（T’）中所有符号都在FOLLOW（F）中，是以FOLLOW(F)= {，+， # , ) }。

綜上所述：

——————————————————————————————

例子2：

設有文法G【A】：

① A -> BCc|gDB

② B -> bCDE|ε

③ C -> DaB|ca

④ D -> dD|ε

⑤ E -> gAf|c

此例題使用①概念法解題，具體步驟如下：

對于A：A是句型的最右符号，則将結束符#添加到 FOLLOW(A)中，又⑤ E -> gAf|c，A後緊跟的結束符為f。是以FOLLOW(A)={# , f }；

對于B：由A -> gDB可知，B後可直接跟#，又 E -> gAf，可得E -> ggDBf，是以f在FOLLOW（B）中；又 A -> BCc，是以B後緊跟的為C，是以C可推導出的所有串首終結符，均緊跟在B後，是以FIRST（C）全部在FOLLOW（B）中，則FOLLOW（B）可含有#，c，a，d；又因為C -> DaB，B -> bCDE，D -> ε，可得B ->bDaBE，是以E可推導出的所有串首終結符，均緊跟在B後，是以FIRST（E）全部在FOLLOW（B）中，則g也在FOLLOW（B）中。是以FOLLOW（B）= { #, c, a, d, g, f}；

對于C：因為A -> BCc，是以C後可跟c；又B -> bCDE，C後緊跟D，是以FIRST（D）在FOLLOW（C）中，即含有終結符d；又 D -> ε，是以E可緊跟在C後，則FOLLOW（C）含有g,是以FOLLOW（C）= { c, d, g}；

對于D：因為D -> dD，是以#在FOLLOW（D）中；又A -> gDB，是以FIRST（B）都在FOLLOW（D）中，即包含終結符b，又E -> gAf，B -> ε可推出E -> gDf，是以含有f；又C -> DaB，是以a在FOLLOW（D）中； B -> bCDE，是以FIRST（E）都在FOLLOW（D）中，即包含終結符g，c。是以FOLLOW（C）= { #, b, a, c, g, f}；

對于E：因為E除本身外，僅出現在B -> bCDE中，E是B中除#的最後一位，是以FOLLOW（B）=FOLLOW（E）={ #, c, a, d, g, f}。

綜上所述：

啊今天的學習狀态不太對，是以表述思緒稍有混亂，以上若有錯誤或表述不清的地方，望多多包涵、積極指出，謝謝您！