编译原理：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}。

综上所述：

啊今天的学习状态不太对，所以表述思绪稍有混乱，以上若有错误或表述不清的地方，望多多包涵、积极指出，谢谢您！