FIRST集合和FOLLOW集合
一吐绵、First集合
定義：
First集合是對產生式右部的字符串而言的，求取的是非終結符VT（或終結符尼斧、空字符长踊、文法符號串）的開始符號集合，集合中包含的是由左部非終結符VT推導得到的終結符VN或空字符ε。以α表示一個文法的字符串毫别，F(xiàn)IRST( α ）表示由α推導出的串的首個終結符或空字符組成的集合娃弓。
規(guī)則
求文法符號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 )假褪。
一組文法符號串
由規(guī)則可知單個文法字符的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 }
由規(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
設有文法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集合是對某個非終結符而言的叮叹，求取的是非終結符VT的后繼符號集合艾栋，集合中包含的是由非終結符VT后面緊跟的終結符VN和結束符$，不能出現(xiàn)空字符ε 衬横。以X表示一個非終結符裹粤，F(xiàn)OLLOW( X ）表示當X通過規(guī)約出現(xiàn)時，接下來的輸入可能是哪些終結符蜂林。
規(guī)則
求非終結符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 债朵， }∪{ 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 )除ε以外加入進去结窘；有A→gDB很洋，規(guī)則③將FOLLOW( A )加入進去；有C→DaB隧枫，規(guī)則③將FOLLOW( C )加入進去喉磁。
對于C的出現(xiàn)來說：有?A→BCc谓苟，規(guī)則②將c加入進去；有B→bCDE协怒，規(guī)則③將FOLLOW( D )加入進去涝焙，由于D存在空字符ε，所以需要把FIRST( E )除ε以外也加入進去斤讥。
對于D的出現(xiàn)來說：有A→gDB纱皆，規(guī)則②將FIRST( B )除ε以外加入進去，由于B存在空字符ε芭商，所以規(guī)則③將FOLLOW( A )加入進去；有B→bCDE搀缠，規(guī)則②將FIRST( E )除ε以外加入進去铛楣；有C→DaB，規(guī)則②將a加入進去艺普。
對于E的出現(xiàn)來說：有B→bCDE簸州，規(guī)則③將FOLLOW( B )加入進去。
舉例2
設有文法G[S]:
???S→aBS | bAS | ε
???A→bAA | a
???B→aBB | b
解：
FOLLOW( S ) = { }∪{ a岸浑，b }
?????????????={ a，b瑰步， }∪{ a，b }
?????????????={ a缩焦，b读虏，加入進去盖桥。
對于A的出現(xiàn)來說：有S→bAS，規(guī)則②將FIRST( S )除ε以外加入進去,由于S存在空字符ε题翻，規(guī)則③將FOLLOW( S )加入進去揩徊；有A→bAA，規(guī)則②將FIRST( A )除ε以外加入進去嵌赠。
對于B的出現(xiàn)來說：有S→aBS塑荒，規(guī)則②將FIRST( S )除ε以外加入進去,由于S存在空字符ε，規(guī)則③將FOLLOW( S )加入進去猾普；有B→aBB袜炕，規(guī)則②將FIRST( B )除ε以外加入進去。
第三部分·如何構造LL(1)分析表
首先畫出表格初家，表格的左列是每一個產生式的左部（不重復）偎窘，表格的橫行是每一個終結符號乌助。
接著逐個考察所有產生式。
抽象算法：
對于G中的每一個產生式陌知， A -> α ,執(zhí)行以下2步：
1.for ? a ∈ FIRST(α)他托， 將 A -> α 填入 M [A, a ];
//對逐個產生式進行考察，考察產生式的FIRST集合的元素仆葡，在找到的元素的對應表格中填寫該產生式
-
if（ε ∈ FIRST(α)）
? a ∈ FOLLOW (A) 赏参， 將 A -> ε 填入 M [A, a ];
//如果發(fā)現(xiàn)產生式的FIRST集中包含空符號，就查找該產生式頭部的FOLLOW集合中的元素沿盅，在元素的對應表格中填寫空產生式
