编译原理：FIRST集与FOLLOW集
2018-12-13 20:28阅读：
一、First集合
定义：
First集合是对产生式右部的字符串而言的，求取的是非终结符VT（或终结符、空字符、文法符号串）的开始符号集合，集合中包含的是由左部非终结符VT推导得到的终结符VN或空字符ε。以α表示一个文法的字符串，FIRST(
α ）表示由α推导出的串的首个终结符或空字符组成的集合。
规则
求文法符号X的FIRST( X
) ，直到没有终结符或空字符可以加入。
如果X属于终结符VT，则FIRST(X)
= { X } 。
如果X属于非终结符VN，且有产生式形如X
→ a…，则FIRST( X ) = { a
}。
如果X属于非终结符VN，且有产生式形如X
→
ABCdEF…（A、B、C均属于非终结符且包含
ε，d为终结符），需要把d、FIRST(
A )、FIRST( B
)、FIRST( C
)加入到FIRST( X)中。
如果X经过一步或多步推导出空字符ε，将ε加入FIRST(
X )。
一组文法符号串
由规则可知单个文法字符的FIRST集，黑道学生那么一组文法字符串的FIRST集也可以求取了。假设文法符号串S由X1X2X3……Xn组成，则将每个文法符号Xi的FIRST集加入到FIRST(
S )中，包括空字符ε。
举例1
设有文法G[A]：
A→BCc | gDB
B→bCDE | ε
C→DaB | ca
D→dD | ε
E→gAf | c
解：
FIRST( A ) = FIRST( BCc ) ∪ FIRST(
gDB ）
=FIRST( B )∪FIRST( C
)∪{ c }∪{ g
}
由规则规则可知
FIRST( A ) =FIRST( B )∪FIRST( D
)∪{ a }∪{ c
}∪{ c }∪{ g
}
={
b，ε }∪{
d，ε }∪{ a
}∪{ c }∪{ g
}
={
a，b，c，d，g
，ε }
FIRST( B ) = { b，ε }
FIRST( C ) = FIRST( D )∪{ a
}∪{ c }= {
a，c，d，ε
}
FIRST( D ) = { d，ε }
FIRST( E ) = { g，c }
对于A来说：有两种选择 BCc
与
gDB，BCc用规则，gDB用规则。
对于B来说：有两种选择
bCDE 与 ε，均用规则。
对于C来说：有两种选择 DaB
与
ca，由于D存在空字符，52小说网所以
DaB用规则，ca用规则。
对于D来说：有两种选择dD 与
ε ，分别用规则与规则。
对于E来说：有两种选择gAf 与 c ，均用规则。
举例2
设有文法G[S]:
S→aBS | bAS | ε
A→bAA | a
B→aBB | b
解：
FIRST( S ) = FIRST( aBS )∪FIRST(
bAS )∪{ ε }={
a，b，ε
}
FIRST( A ) = { a，b }
FIRST( B ) = { a，b }
对于S来说：有三种选择
aBS与bAS、ε，分别用与规则。
对于A来说：有两种选择bAA与
a，均用规则。
对于B来说：有两种选择aBB与
b，均用规则。
二、Follow集合
定义：
Follow集合是对某个非终结符而言的，求取的是非终结符VT的后继符号集合，集合中包含的是由非终结符VT后面紧跟的终结符VN和结束符$，不能出现空字符ε
。以X表示一个非终结符，FOLLOW(
X
）表示当X通过规约出现时，接下来的输入可能是哪些终结符。
规则
求非终结符X的FOLLOW( X
) ，直到没有终结符可以加入。
如果X是开始符号，则将$加入到FOLLOW(X)中
。
如果存在一个产生式S->αXβ，那么将集合FIRST(β)中除ε外的所有元素加入到FOLLOW(X)当中。
如果存在一个产生式 S->αX
,
或者S->αXβ且FIRST(β)中包含ε
,
那么将集合FOLLOW(S)中的所有元素加入到集合FOLLOW(X)中。
举例1
设有文法G[A]：
A→BCc | gDB
B→bCDE | ε
C→DaB | ca
D→dD | ε
E→gAf | c
解：
FOLLOW( A ) ={ f ，$ }
FOLLOW( B ) = FIRST( C )∪FOLLOW( A
)∪FOLLOW( C )
={
a，c，d
}∪{ f ，$
}∪{
c，d，g，$
}
={
a，c，d，f，g，$
}
FOLLOW( C ) = { c }∪FIRST( D
)∪FIRST( E )
={ c }∪{ d
}∪{ g，c
}
={
c，d，g
}
FOLLOW( D ) = FIRST( B )∪FOLLOW(A
)∪FIRST( E )∪{
a }
={ b } ∪{
g，c }∪{
f ，$ }∪{ a
}
={
a，b，c，g，f，$
}
FOLLOW( E ) = FOLLOW( B )
={
a，c，d，f，g，$
}
其中，A,B,C,D,E都是非终结符，A是开始符号。
对于A的出现来说：A是开始符号，规则需要加入$；E→gAf，规则将f加入FOLLOW(
A )。
对于B的出现来说：有 A→BCc，规则将FIRST(
C
)除ε以外加入进去；有A→gDB，规则将FOLLOW(
A
)加入进去；有C→DaB，规则将FOLLOW(
C )加入进去。
对于C的出现来说：有 A→B
