语法分析

FIRST集合
F I R S T ( α ) = { a ∣ α ⇒ ∗ a … , a ∈ V T } FIRST(α) = \{a| α \overset{*}{\Rightarrow} a…,a\in V_T \} FIRST(α)={ a∣α⇒∗a…,a∈VT}

求某一非终结符A的首终结符集First(A)的算法为：
1.若有产生式 A → a α , a ∈ V T A \rightarrow aα,a∈V_T A→aα,a∈VT，把a加到First(A)中；
2.若有产生式 A → ε A \rightarrow ε A→ε, 把ε加到First(A)中；
3.若有产生式 A → X α ， X ∈ V N A\rightarrow Xα，X∈V_N A→Xα，X∈VN，把First(X)中非ε元素加到First(A)中；
4.若有产生式 A → X 1 X 2 X 3 . . . X k α A\rightarrow X_1X_2X_3…X_kα A→X1X2X3…Xkα,其中 X 1 X 2 . . . X k ∈ V N X_1X_2…X_k∈V_N X1X2…Xk∈VN。则{
当 X 1 X 2 X 3 . . . X i ⇒ ∗ ε ( 1 ≤ i ≤ k ) 时，把 F i r s t ( X i + 1 . . . X k ) 的非 ε 元素加到 F i r s t ( A ) 中 X_1X_2X_3…X_i\overset{*}{\Rightarrow} ε(1≤i≤k)时，把First(X_{i+1}…X_k)的非ε元素加到 First(A)中 X1X2X3…Xi⇒∗ε(1≤i≤k)时，把First(Xi+1…Xk)的非ε元素加到First(A)中；
当 X 1 X 2 X 3 . . . X k ⇒ ∗ ε X_1X_2X_3…X_k\overset{*}{\Rightarrow} ε X1X2X3…Xk⇒∗ε时，把First(α)加入First(A)中
5.重复执行上述过程，直到First(A)不再增大

若 α ⇒ ∗ ε ，则 ε ∈ F I R S T ( α ) 若α \overset{*}{\Rightarrow} ε ，则ε \in FIRST(α) 若α⇒∗ε，则ε∈FIRST(α)

FOLLOW集合
F O L L O W ( A ) = { a ∣ S ⇒ ∗ … A a … ， a ∈ Ｖ T } FOLLOW(A)=\{a|S \overset{*}{\Rightarrow}…Aa…，a \in Ｖ_T \} FOLLOW(A)={ a∣S⇒∗…Aa…，a∈ＶT}
特别，若 S ⇒ ∗ … A ，则， # ∈ F O L L O W ( A ) S \overset{*}{\Rightarrow} …A，则，\# ∈FOLLOW(A) S⇒∗…A，则，#∈FOLLOW(A)
其中’#’ 为文本结束符号
构造FOLLOW(U)的算法为：
对文法的识别符号Z，令#∊FOLLOW(U)；
若文法中有形如A→αUβ的规则，则FIRST(β)中的非ε元素∊FOLLOW(U);
若文法中有形如A→αU或A→αUβ而FIRST(β)中含有ε的规则，则FOLLOW(A) ⊆ \subseteq ⊆FOLLOW(U)

1.如果A是开始符号，＃∈Follow(A)
2.若有产生式 B → α A a β , a ∈ V T B\rightarrow αAaβ,a∈V_T B→αAaβ,a∈VT，则
把a加入到Follow(A)中；
3.若有产生式 B → α A X β ， X ∈ V N B \rightarrow αAXβ，X∈V_N B→αAXβ，X∈VN，则
把First(Xβ)中非ε元素加入Follow(A)中；
4.若 B → α A 或 B → α A β ， β ⇒ ∗ ε B \rightarrow αA 或 B\rightarrow αAβ，β \overset{*}{\Rightarrow} ε B→αA或B→αAβ，β⇒∗ε，则
把Follow(B)加入到Follow(A)中；
5.连续使用上述规则，直到Follow(A)不再增大。

SELECT集合
给定上下文无关文法的规则 A → α （ A ∈ V N , α ∈ V ∗ ） A→α（A\in V_N, α\in V^*） A→α（A∈VN,α∈V∗）的SELECT集合为
若 α ⇏ ∗ ε α \overset{*}{\nRightarrow} \varepsilon α⇏∗ε，则SELECT(A→α)=FIRST(α)
若 α ⇒ ∗ ε α \overset{*}{\Rightarrow} \varepsilon α⇒∗ε，则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)
注意
小结：