FIRST 與 FOLLOW 集(FIRST and FOLLOW sets)
為了預測該用哪條文法規則,由上而下剖析器對每個非終端符號問兩個自然的問題:「它可能以哪些詞符開頭?」以及「若它什麼都不產生,緊接其後可能出現什麼?」FIRST 回答第一個問題,FOLLOW 回答第二個。它們是讓預測式剖析器往前瞄一個詞符、便知該觸發哪條規則的小型查找表。
FIRST(X) 是能作為由 X 推導出之某字串「最前面那個詞符」出現的終端符號集合。對規則 A -> num B,num 屬於 FIRST(A);對 A -> B c 而 B 可能為空時,FIRST(A) 包含 FIRST(B),並可能包含 c。若某非終端符號能推導出空字串,也會記下表示空的特殊標記。FOLLOW(A) 是在某句型中能合法緊接於 A 之後出現的終端符號集合;計算方法是看每條 A 出現在右側的規則 X -> alpha A beta,加入 FIRST(beta),並在 beta 能消失時加入 FOLLOW(X)。這些集合以不動點過程計算:從空開始,不斷加入直到不再有新元素。一旦得知,LL(1) 表便靠單一規則填寫:把 A -> alpha 放在 FIRST(alpha) 的每個詞符底下,而若 alpha 能為空,也放在 FOLLOW(A) 的每個詞符底下。
FIRST 與 FOLLOW 是預測式與 LL 剖析背後的引擎:沒有它們,你無法建出無衝突的剖析表,也無法判斷文法是否為 LL(1)。它們也精確地暴露衝突:若某非終端符號的兩個選項 FIRST 集重疊,或一個能推導空的選項與 FOLLOW 相撞,表中同一格就會出現兩個項目,這正是文法非 LL(1)、必須重做的形式警訊。
對 E -> T E'、E' -> + T E' | epsilon、T -> num:FIRST(T) = {num}、FIRST(E') = {+, 空}、FIRST(E) = {num}。FOLLOW(E) = {輸入結束, )}(任何能跟在整個運算式之後的),且 FOLLOW(E') = FOLLOW(E)。因為 FIRST(+ T E') = {+} 而 FOLLOW(E') 不含 +,E' 的選擇無衝突。
FIRST = 一個符號能以什麼開頭;FOLLOW = 緊接其後能出現什麼。
只有對能推導出空字串的產生式才需查 FOLLOW;對一般產生式只需 FIRST。搞混這點是手填 LL(1) 表時最常見的錯誤。