编译原理中Follow集的求法

时间:2023-03-09 16:34:49
编译原理中Follow集的求法

经过前阵子的各种百度以及对课本的反复研究,终于弄明白了follow集的求法,下面记录一下!

首先引用龙书里面的一段较为公式化的follow集求法的话:

计算所有非终结符号A的follow(A)集合时,不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。

(1)将

放到follow(S)中,其中S是开始符号,而
是输入右端的结束标记。

(2)如果存在一个产生式A→αBβ,那么first(β)中除ε之外的所有符号都在follow(B)中。

(3)如果存在一个产生式A→αB,或存在产生式A→αBβ且first(β)包含ε,那么follow(A)中的所有符号都在follow(B)中。

下面举个例子来说明下,假设有如下文法:

①E→TE’

②E’→+TE’ | ε

③T→FT’

④T’→*FT’ | ε

⑤F→(E)| id

对于每个非终结符号,我们都可以求出其follow集:

根据(1),首先将

加入到follow(E)中,即follow(E)={
},由⑤可知,)也应该在follow(E)中,即follow(E)={$,)};

对于E’,根据规则(3)以及产生式①,应该将follow(E)加入到follow(E‘)中,即follow(E’)={$,)};

对于T,根据规则(2)以及产生式①,应该将first(E’)加入到follow(T)中,即follow(T)={+},根据规则(3),由于first(E’)包含ε,所以应该将follow(E)加入到follow(T)中,即follow(T)={+,$,)};

对于T’,根据规则(3)以及产生式③,应该将follow(T)加入到follow(T‘)中,即follow(T’)={+,$,)};

对于F,根据规则(2)以及产生式③,应该将first(T’)加入到follow(F)中,即follow(F)={},根据规则(3),由于first(T’)包含ε,所以应该将follow(T)加入到follow(F)中,即follow(F)={,+,$,)};

以下是我自己对Follow集的理解,非转载内容:
Follow 集实际上就是我们父亲节点的兄弟节点的First集合。但是这不是全部。