FIRST集合和FOLLOW集合
一、First集合
定義：
First集合是對產(chǎn)生式右部的字符串而言的，求取的是非終結(jié)符VT（或終結(jié)符、空字符、文法符號串）的開始符號集合，集合中包含的是由左部非終結(jié)符VT推導(dǎo)得到的終結(jié)符VN或空字符ε。以α表示一個文法的字符串，F(xiàn)IRST( α ）表示由α推導(dǎo)出的串的首個終結(jié)符或空字符組成的集合。
規(guī)則
求文法符號X的FIRST( X ) ，直到?jīng)]有終結(jié)符或空字符可以加入。
① 如果X屬于終結(jié)符VT，則FIRST(X) = { X } 。
② 如果X屬于非終結(jié)符VN，且有產(chǎn)生式形如X → a…，則FIRST( X ) = { a }。
③ 如果X屬于非終結(jié)符VN，且有產(chǎn)生式形如X → ABCdEF…（A、B、C均屬于非終結(jié)符且包含 ε，d為終結(jié)符），需要把d、FIRST( A )、FIRST( B )、FIRST( C )加入到FIRST( X)中。
④ 如果X經(jīng)過一步或多步推導(dǎo)出空字符ε，將ε加入FIRST( X )。
一組文法符號串
由規(guī)則可知單個文法字符的FIRST集，那么一組文法字符串的FIRST集也可以求取了。假設(shè)文法符號串S由X1X2X3……Xn組成，則將每個文法符號Xi的FIRST集加入到FIRST( S )中，包括空字符ε。
舉例1
設(shè)有文法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 }
由規(guī)則③規(guī)則②可知
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用規(guī)則③，gDB用規(guī)則②。
對于B來說：有兩種選擇 bCDE 與 ε，均用規(guī)則②。
對于C來說：有兩種選擇 DaB 與 ca，由于D存在空字符，所以 DaB用規(guī)則③，ca用規(guī)則②。
對于D來說：有兩種選擇dD?與 ε?，分別用規(guī)則②與規(guī)則④。
對于E來說：有兩種選擇gAf?與?c?，均用規(guī)則②。
舉例2
設(shè)有文法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、ε，分別用②與規(guī)則④。
對于A來說：有兩種選擇bAA與 a，均用規(guī)則②。
對于B來說：有兩種選擇aBB與 b，均用規(guī)則②。
二、Follow集合
定義：
Follow集合是對某個非終結(jié)符而言的，求取的是非終結(jié)符VT的后繼符號集合，集合中包含的是由非終結(jié)符VT后面緊跟的終結(jié)符VN和結(jié)束符$，不能出現(xiàn)空字符ε 。以X表示一個非終結(jié)符，F(xiàn)OLLOW( X ）表示當(dāng)X通過規(guī)約出現(xiàn)時，接下來的輸入可能是哪些終結(jié)符。
規(guī)則
求非終結(jié)符X的FOLLOW( X ) ，直到?jīng)]有終結(jié)符可以加入。
① 如果X是開始符號，則將$加入到FOLLOW(X)中 。
② 如果存在一個產(chǎn)生式S->αXβ，那么將集合FIRST(β)中除ε外的所有元素加入到FOLLOW(X)當(dāng)中。
③如果存在一個產(chǎn)生式 S->αX , 或者S->αXβ且FIRST(β)中包含ε , 那么將集合FOLLOW(S)中的所有元素加入到集合FOLLOW(X)中。
舉例1
設(shè)有文法G[A]：?
???A→BCc?|?gDB??????
???B→bCDE?| ε?????
???C→DaB?|?ca??????
???D→dD?| ε??????
???E→gAf?|?c?
解：
FOLLOW( A ) ={ f ， }∪{ c，d，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 ， }
FOLLOW( E ) = FOLLOW( B )
?????????????={ a，c，d，f，g，；E→gAf，規(guī)則②將f加入FOLLOW( A )。
對于B的出現(xiàn)來說：有?A→BCc，規(guī)則②將FIRST( C )除ε以外加入進(jìn)去；有A→gDB，規(guī)則③將FOLLOW( A )加入進(jìn)去；有C→DaB，規(guī)則③將FOLLOW( C )加入進(jìn)去。
對于C的出現(xiàn)來說：有?A→BCc，規(guī)則②將c加入進(jìn)去；有B→bCDE，規(guī)則③將FOLLOW( D )加入進(jìn)去，由于D存在空字符ε，所以需要把FIRST( E )除ε以外也加入進(jìn)去。
對于D的出現(xiàn)來說：有A→gDB，規(guī)則②將FIRST( B )除ε以外加入進(jìn)去，由于B存在空字符ε，所以規(guī)則③將FOLLOW( A )加入進(jìn)去；有B→bCDE，規(guī)則②將FIRST( E )除ε以外加入進(jìn)去；有C→DaB，規(guī)則②將a加入進(jìn)去。
對于E的出現(xiàn)來說：有B→bCDE，規(guī)則③將FOLLOW( B )加入進(jìn)去。
舉例2
設(shè)有文法G[S]:
???S→aBS | bAS | ε
???A→bAA | a
???B→aBB | b
解：
FOLLOW( S ) = { }∪{ a，b }
?????????????={ a，b， }∪{ a，b }
?????????????={ a，b，加入進(jìn)去。
對于A的出現(xiàn)來說：有S→bAS，規(guī)則②將FIRST( S )除ε以外加入進(jìn)去,由于S存在空字符ε，規(guī)則③將FOLLOW( S )加入進(jìn)去；有A→bAA，規(guī)則②將FIRST( A )除ε以外加入進(jìn)去。
對于B的出現(xiàn)來說：有S→aBS，規(guī)則②將FIRST( S )除ε以外加入進(jìn)去,由于S存在空字符ε，規(guī)則③將FOLLOW( S )加入進(jìn)去；有B→aBB，規(guī)則②將FIRST( B )除ε以外加入進(jìn)去。
第三部分·如何構(gòu)造LL(1)分析表
首先畫出表格，表格的左列是每一個產(chǎn)生式的左部（不重復(fù)），表格的橫行是每一個終結(jié)符號。
接著逐個考察所有產(chǎn)生式。
抽象算法：
對于G中的每一個產(chǎn)生式， A -> α ,執(zhí)行以下2步：
1.for ? a ∈ FIRST(α)， 將 A -> α 填入 M [A, a ];
//對逐個產(chǎn)生式進(jìn)行考察，考察產(chǎn)生式的FIRST集合的元素，在找到的元素的對應(yīng)表格中填寫該產(chǎn)生式
-
if（ε ∈ FIRST(α)）
? a ∈ FOLLOW (A) ， 將 A -> ε 填入 M [A, a ];
//如果發(fā)現(xiàn)產(chǎn)生式的FIRST集中包含空符號，就查找該產(chǎn)生式頭部的FOLLOW集合中的元素，在元素的對應(yīng)表格中填寫空產(chǎn)生式
