编译原理:FIRST集和FOLLOW集

FIRST集

1

FIRST(X): 可以从X推导出的所有串首终结符构成的集合

如果$X \Rightarrow {}^* \varepsilon$.那么 $\varepsilon \in FIRST(X)$

例

$$\begin{align*} \textcircled{1} &\ E \to TE' & \text{FIRST}(E) &= \lbrace (, \text{id} \rbrace \\ \textcircled{2} &\ E' \to +TE' \mid \varepsilon & \text{FIRST}(E') &= \lbrace +, \varepsilon \rbrace \\ \textcircled{3} &\ T \to FT' & \text{FIRST}(T) &= \lbrace (, \text{id} \rbrace \\ \textcircled{4} &\ T' \to *FT' \mid \varepsilon & \text{FIRST}(T') &= \lbrace *, \varepsilon \rbrace \\ \textcircled{5} &\ F \to (E) \mid \text{id} & \text{FIRST}(F) &= \lbrace (, \text{id} \rbrace \end{align*}$$

算法

不断应用下列规则，直到没有新的终结符或 ε 可以被加入到任何 FIRST 集合中为止
▶ 如果 X 是一个终结符，那么 FIRST(X) = {X}
▶ 如果 X 是一个非终结符，且 X→Y₁…Yₖ ∈ P（k≥1），那么：

• 如果对于某个 i，a 在 FIRST(Yᵢ) 中，且 ε 在所有的 FIRST(Y₁), …, FIRST(Yᵢ₋₁) 中（即 Y₁…Yᵢ₋₁ ⇒* ε），就把 a 加入到 FIRST(X) 中。
• 如果对于所有的 j = 1, 2, …, k，ε 在 FIRST(Yⱼ) 中，那么将 ε 加入到 FIRST(X) 中。
  ▶ 如果 X→ε ∈ P，那么将 ε 加入到 FIRST(X) 中

计算$串X_1X_2..X_n$的FIRST集合

向$FIRST(X_1X_2X_3...X_n)加入FIRST(X_1)$中所有的非 $\varepsilon$符号

如果 $\varepsilon$ 在$FIRST(X_1)$中,再加入$FIRST(X_2)$中的所有非 $\varepsilon$符号;

如果 $\varepsilon$ 在$FIRST(X_1)$和$FIRST(X_2)$中,再加入$FIRST(X_3)$中的所有非$\varepsilon$符号,以此类推

FOLLOW集

FOLLOW(A):可能在某个句型中,紧跟在A后边的非终结符a的集合

例

$$\begin{array}{lcl} ① & E \to TE' & \text{FIRST}(E) = \{ (, \text{id} \} \quad \text{FOLLOW}(E) = \{ \#, ) \}\\ ② & E' \to +TE' \mid \varepsilon & \text{FIRST}(E') = \{ +, \varepsilon \} \quad \text{FOLLOW}(E') = \{ \#, ) \}\\ ③ & T \to FT' & \text{FIRST}(T) = \{ (, \text{id} \} \quad \text{FOLLOW}(T) = \{ +, \#, ) \}\\ ④ & T' \to *FT' \mid \varepsilon & \text{FIRST}(T') = \{ *, \varepsilon \} \quad \text{FOLLOW}(T') = \{ +, \#, ) \}\\ ⑤ & F \to (E) \mid \text{id} & \text{FIRST}(F) = \{ (, \text{id} \} \quad \text{FOLLOW}(F) = \{ *, +, \#, ) \} \end{array}$$