FIRST(α) = α 能推出的所有串的第一个终结符的集合;若 α 能推出空串(α⇒*ε),就把 ε 也放进去[1]。
① 终结符 a:FIRST(a)={a}。
② 对 X→Y₁Y₂…Yk:把 FIRST(Y₁)\{ε} 加入;若 ε∈FIRST(Y₁) 再看 Y₂……;若所有 Yᵢ 都含 ε,则 ε∈FIRST(X)。
③ X→ε:ε∈FIRST(X)。
FOLLOW(A)(只对非终结符)= 在各种句型中,紧跟在 A 后面的终结符集合;若 A 可能出现在句型的最右端,就把结束符 # 放进去。
① #∈FOLLOW(S)(S 是开始符号)。
② 对 B→αAβ:把 FIRST(β)\{ε} 加入 FOLLOW(A)。
③ 若 β⇒*ε(或 β 为空,即 B→αA):把 FOLLOW(B) 加入 FOLLOW(A)。
⚠️ 注意:FOLLOW 集里永远不会有 ε,只有终结符和 #。
SELECT(A→α) = FIRST(α) 若 ε∉FIRST(α)
(FIRST(α)\{ε})∪ FOLLOW(A) 若 ε∈FIRST(α)
E → T E′ E′ → + T E′ | ε T → F T′ T′ → * F T′ | ε F → (E) | i求 FIRST(从只含终结符的 F 往上推):
FIRST(F) = { ( , i } (F→(E) 给 ( ;F→i 给 i)
FIRST(T) = FIRST(F) = { ( , i } (T→FT′,F 不推空)
FIRST(E) = FIRST(T) = { ( , i }
FIRST(E′) = { + , ε } (E′→+TE′ 给 + ;E′→ε 给 ε)
FIRST(T′) = { * , ε }
| 非终结符 | FIRST | FOLLOW |
|---|---|---|
| E | ( , i | ) , # |
| E′ | + , ε | ) , # |
| T | ( , i | + , ) , # |
| T′ | * , ε | + , ) , # |
| F | ( , i | * , + , ) , # |
FOLLOW(E):E 是开始符 ⇒ # ;F→(E) 里 E 后面是 ) ⇒ ) ∴ { ) , # }
FOLLOW(T):E→TE′,T 后是 E′,FIRST(E′)\ε = {+} ⇒ + ;
E′ 能推 ε,故再并入 FOLLOW(E)={ ),# } ∴ { + , ) , # }
FOLLOW(F):T→FT′,F 后是 T′,FIRST(T′)\ε = {*} ⇒ * ;
T′ 能推 ε,故再并入 FOLLOW(T)={ +,),# } ∴ { * , + , ) , # }
{*,+,),#} 四个——很多人漏掉 + 和 )(它们是 T′ 可推空后"穿透"上来的)。