LL(1)
文法判别之
First
集合、
Follow
集合、
Select
集合求法
说明：
所有大写字母代表非终结符，小写字母代表终结符，省略号代表未知数目（可能为
0
）的不确定类型的文法符号。
First
集合：
First
集合顾名思义就是求一个文法符号串所可能推导出的符号串的第一个终结符的集合。
First
（
X
）就是求
X
所有推导出的符号串的第一个符号的集合。
求
First
集合可分如下几种情况
:
单个符号的
First
集合：
单个终结符的
First
集合就是它自己。
单个非终结符的
First
集合：
A–>a
… 产生式右部以终结符开头
根据定义，这种情况下显然可以看出
a
属于
First(A)
。
A–>B
… 产生式右部以非终结符开头
根据定义，既然可以把
A
替换成
B
……，也可以看出
First
（
B
）属于
First
（
A
）。
这是一个递归的推导。
多个符号形成的符号串的
First
结合：
符号串
ABC
…，并且
A
不能推导出空串
ε
当
A
不能推导出空串
ε，显然根据定义
First
（
ABC
…）
=First
（
A
）
符号串
ABC
…，并且
A
可能推导出空串
ε
当A
不是空串的时候，显然
First
（
A
）属于
First
（
ABC
…），但当
A
是空串的时候，
ABC
…就成了
BC
…，此时根据
B
是否能推出空串来决定是否将
First
（
B
）加入
First
（
ABC
…）。这是一个递归的推导，综上所述，符号串中的第一个不能推出空串的符 号前面所有符号的
First
集合减去空串
ε都属于
First
（
ABC
…），第一个不能推出空串的 符号的
First
集合也属于
First
（
ABC
…）。也就是假设
A
、
B
都可以推出空串，
C
不能推 出空串，
First
（
ABC
…）
=First
（
A
）
–
ε∪First
（
B
）
–
ε∪First
（
C
）。
符号串
ABC
…，并且所有的符号
ABC
…都可能推导出空串
ε
此时First
（
ABC
…）就是所有符号的
First
集合的并集
注意：
First
集合中的符号一定是终结符，终结符也包括空串
ε。
Follow
集合：
Follow
集合也是顾名思义的，就是文法符号后面可能跟随的终结符的集合（不包括空 串
ε）。
Follow(X)
就是求
X
后面可能跟随的符号集合。
求
Follow
集合可分如下几种情况
:
终结符的
Follow
集合没有定义，只有非终结符才会有
Follow
集合。
A–>
…
Ua
… 要求的
Follow
集合的非终结符后跟终结符
根据定义，显然
a
属于
Follow
（
U
）。这种情况下，
Follow
（
U
）和
A
没有任何关系，产 生式左边是什么无所谓。
A–>
…
UP
… 要求的
Follow
集合的非终结符后跟非终结符
根据定义，显然
P
的第一个符号属于
Follow
（
U
），也就是
First
（
P
）属于
Follow
（
U
）。
A–>
…
UP
并且
ε属于First
（
P
） 要求的
Follow
集合的非终结符后跟非结尾的终结符， 并且结尾非终结符的
First
集合包含空串。
这是上一种情况的一种特例，除了要按上一种情况处理，
First
（
P
）属于
Follow
（
U
） 以外还要进行分析；因为当
P
推导为空串时，空串不能出现在
Follow
集合中，所以
U
后面跟随的应该是
P
后面的东西，可
P
已经是结束的符号，此时
U
后面显然就是
A
后 面跟随的东西了。所以在这种情况下
Follow
（
A
）也属于
Follow
（
U
）。
A–>
…
U
要求的
Follow
集合的非终结符在产生式结尾
这时候又要递归推导，
U
是
A
的结尾，所以
U
后面跟随的东西也就是
A
后面跟随的东 西。所以
Follow
（
A
）属于
Follow
（
U
）。
注意：
Follow
集合中的符号一定是终结符，并且不能包括空串
ε，而且定义开始符号 的Follow
集合初始为
{#(
句子括号
)}
。
Select
集合：
Select
集合就是产生式左部的可能的推导结果的起始符号。
Select
（
A–>B
）就是求这个产生式中
A
可能推导出起始符号集合（不包含空串
ε）。
求
Select
集合可分如下几种情况
:
A–>X
（
X
为任意文法符号串，不限于非终结符或单个符号），并且
X
不能推导出空串
ε
根据定义，显然A
推出的符号串起始就是
X
的起始，也就是
First
（
X
）
.
Select
（
A–>X
）
= First
（
X
）
A–>X
（
X
为任意文法符号串，不限于非终结符或单个符号），并且
X
能推导出空串
ε
根据定义，显然
First
（
X
）属于
Select
（
A–>X
），此外，当
X
推导为空串时，显然
A
也推导为空串，那么此时推导出的符号串就会是
A
后面的符号的推导结果。也就是
Follow
（
A
）
,
所以，此时
Follow
（
A
）也属于
Select
（
A–>X
）。
注意：
Select
集合中不包括空串
ε，但有可能会包含#(
句子括号
)
。