Question

编译原理中如何求first集合和follow集合

Answer 1

关于First集合、Follow集合以及select集合的求法
First集合：
定义：令X为一个文法符号（终止符或非终止符）或ε，则集合First（X）有终止符组成，此外可能还有ε，它的定义如下：
1. 若X是终止符或ε，则First（X）= {X}。
2. 若X是非终结符，则对于每个产生式X—>X1X2…Xn，First（X）包含了First（X1）-{ε}。
若对于某个i < n，所有的集合First（X1），... ，First（Xi）都包含了ε，则First（X）也包 括了First（Xi+1）- {ε}。若所有集合First（X1），...，First（Xn）都包括了ε，则First（X）也包括了ε。

Follow集合：
给出一个非终结符A，那么集合Follow（A）则是由终结符组成，此外可能还含有#（#是题目约定的字符串结束符）。集合Follow（A）的定义如下：
1. 若A是开始符号，则#在Follow（A）中。
2. 若存在产生式B—>αAγ，则First（γ）- {ε}在Follow（A）中。
3. 若存在产生式B—>αAγ，且ε在First（γ）中，则Follow（A）包括Follow（B）。

Select集合：
对于产生式A—>α。集合select（A—>α）定义如下：
1. 若α不能推出ε，则select（A—>α） = first（α）。
2. 若α能推出ε，则select（A—>α）= first（α）∪ follow(A)。

具体例题：判段G1[E]是否是LL（1）文法。
G1[E]：E ® －E | [ E ] | V F
F ® －E | ε
V ® t X
X ® [ E ] | ε
说明：其中，终结符号集 = {t, [ , ] , －}。
解：G1[E]：E ® －E ①| [ E ] ②| V F③
F ® －E ④| ε ⑤
V ® t X ⑥
X ® [ E ] ⑦| ε ⑧
Select（①） = first（-E）= {-} (1)//因为-是终止符，所以－E不能为空。
Select（②）= first（[E]） = {[} (2) //理由同上
Select(③) = first(VF) = {t} (3)//VF的第一个符号V是非终止符，故要判断V的first集，由产生式⑥只V的first集为{t}，故first（VF）= {t}。
Select（④）= first（-E）= {-} (4)
Select（⑤）= follow（F）= {], #} (5)//产生式⑤中的α为ε（即空），故等于Follow（F）。由产生式③知F后为空，故E的follow集也包含在F的follow集中（理由见follow集定义第三条）。再看E的follow集。首先E是开始符，故“#”在follow（E）中，又由②或⑦知“]”也在follow（E）中。故Select(③) = {}，#}。
Select（⑥）= first（tX）= {t} (6)
Select（⑦）= first（[E]）= {[} (7)
Select（⑧）= follow（X）= {-,],#} (8) //求X的follow集，由⑥知V的follow集在follow（X）中，又由③知first（F）- {ε }在follow（X）中，又由⑤知ε 在first（F）中（或者可以认为F可以推出ε ），故follow（F）也在follow（X）中（follow集定义第三条）。所以Select（⑧）= {-,],#}。

因为同一个非终止符的不同产生式（即①②③，④⑤，⑥，⑦⑧这四组）所对应的select集(即(1)(2)(3),(4)(5),(6),(7)(8))都没有交集，所以该文法是LL(1)文法。
此文引用magiczgz