目录

• FIRST的计算
• FOLLOW的计算
• SELECT的计算

FIRST的计算

first表示的是串首终结符
计算方法比较简单：

• 终结符开头，写入集合
• 空，写入集合
• 非终结符开头，递归向上，写入集合

例子：

表达式	FIRST集合
E->TE'	( 、id
E'->+TE'|ε	+、 ε
T->FT'	（ 、id，
T'->*FT'|ε	* 、ε
F->(E)|id	( 、id

演算步骤：

• T' E' F 都是以终结符开头的，直接将开头的终结符加入到FIRST集合中
• T' E' 都是有空集的，直接加进去
• 看E，E的第一个是非终结符T，T的第一个是F，F的是（ 、id，直接将这两个加到E里面去
• 看T，T是F，F是（ 、id，加

结束了

FOLLOW的计算

FOLLOW比较复杂：

• 表示的是可能在某个句型中紧跟着的终结符的集合
• 如果句型是最右符号，则将以结束符$添加到FOLLOW中

表达式	FIRST集合	FOLLOW集合
E->TE'	( 、id	$ 、）
E'->+TE'|ε	+、 ε	$ 、）
T->FT'	（ 、id，	+、$ 、）
T'->*FT'|ε	* 、ε	+、$ 、）
F->(E)|id	( 、id	*、+、$ 、）

运算过程

• E开头，E本身就是一个句型，就这一个字符，本身就是句型的最右符号，直接将FOLLOW(E)上$，所以此时FOLLOW(E)={$}
• 看TE' ,可以看到T的后面紧跟着E'，E'就是T的后继，查E'，E'的第一个字符是+，说明T后面跟着的可能是+，把+写到FOLLOW(T)的里面去。其次，E'可以为空，为空的话就是E后面跟着啥，T后面就跟着啥，E后面跟着的是$，那就把$写入FOLLOW(T)中去。所以此时FOLLOW(T)={+,$}
• 看E'->+TE'|ε 和上面E->TE'都是TE'结尾，所以都是一样的，FOLLOW(E')={$}
• 且看FT',T'可以为空，那么T后面跟什么F后面就跟什么，所以F上+,$，当T'不为空的时候，F后面紧跟着*，所以此时可以说明:FOLLOW(F)={*,+,$}
• T'->*FT'|ε和T->FT'一样，所以FOLLOW(T')={+,$}
• F->(E)|id中，表明E的后面可以跟),所以需要更新FOLLOW(E)={$，）}
• 于是需要进行第二轮计算，所有和E有关的都需要更新
• T和E有关，更新：FOLLOW(T)={+,$，）}
• 经过多次更新，更新之后如图所示

SELECT的计算

SELECT的计算更为简单：

• 如果是以终结符打头的，就是终结符本身
• 如果是以非终结符打头的，则查看它的Frist集合，就是SELECT
• 如果是空串，则是FOLLOW集

例
刚才计算的结果如下：

表达式	FIRST集合	FOLLOW集合
E	( 、id	$ 、）
E'	+、 ε	$ 、）
T	（ 、id，	+、$ 、）
T'	* 、ε	+、$ 、）
F	( 、id	*、+、$ 、）

可以按照上面的方法很容易得到SELECT集

表达式	SELECT集合
E->TE'	( 、id
E'->+TE'	+
E'->ε	$ 、）
T->FT'	( 、id
T'->*FT'	*
T'->ε	+、$ 、）
F->(E)	(
F->id	id

记住，写的时候需要全都拆开