编译原理:FIRST集和FOLLOW集

FIRST集

1

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

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

例

$$\begin{array}{cccc}\overline{)\text{1}}& E\to T{E}^{\prime }& \text{FIRST}(E)& =\{(,\text{id}\}\\ \overline{)\text{2}}& E^{\prime }\to +T{E}^{\prime }|\epsilon & \text{FIRST}(E^{\prime })& =\{+,\epsilon \}\\ \overline{)\text{3}}& T\to F{T}^{\prime }& \text{FIRST}(T)& =\{(,\text{id}\}\\ \overline{)\text{4}}& T^{\prime }\to \ast F{T}^{\prime }|\epsilon & \text{FIRST}(T^{\prime })& =\{\ast ,\epsilon \}\\ \overline{)\text{5}}& F\to (E)|\text{id}& \text{FIRST}(F)& =\{(,\text{id}\}\end{array}$$

算法

不断应用下列规则，直到没有新的终结符或 ε 可以被加入到任何 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) 中

计算$\text{串}{X}_1{X}_2..X_n$的FIRST集合

向$FIRST(X_1{X}_2{X}_3...X_n)\text{加}\text{入}FIRST(X_1)$中所有的非 $\epsilon$符号

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

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

FOLLOW集

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

例

$$\begin{array}{ccc}\overline{)\text{1}}& E\to T{E}^{\prime }& \text{FIRST}(E)=\{(,\text{id}\}\text{FOLLOW}(E)=\{\#,)\}\\ \overline{)\text{2}}& E^{\prime }\to +T{E}^{\prime }|\epsilon & \text{FIRST}(E^{\prime })=\{+,\epsilon \}\text{FOLLOW}(E^{\prime })=\{\#,)\}\\ \overline{)\text{3}}& T\to F{T}^{\prime }& \text{FIRST}(T)=\{(,\text{id}\}\text{FOLLOW}(T)=\{+,\#,)\}\\ \overline{)\text{4}}& T^{\prime }\to \ast F{T}^{\prime }|\epsilon & \text{FIRST}(T^{\prime })=\{\ast ,\epsilon \}\text{FOLLOW}(T^{\prime })=\{+,\#,)\}\\ \overline{)\text{5}}& F\to (E)|\text{id}& \text{FIRST}(F)=\{(,\text{id}\}\text{FOLLOW}(F)=\{\ast ,+,\#,)\}\end{array}$$