MENU

FIRST集和FOLLOW集

October 15, 2018 • Read: 237 • 编译原理

FIRST集

对$\alpha \in (V_T\bigcup V_N)^*$,有
$$
FIRST(\alpha)=\{a|\alpha \stackrel{*}\Longrightarrow a \cdot \cdot \cdot, a\in V_T\}
$$
特别的,若$\alpha \stackrel{*}\Longrightarrow \varepsilon$,则$\varepsilon \in FIRST(\alpha)$

因此对于每一文法符号$X\in{V_T}\bigcup{V_N}$,构造$FIRST(X)$的方法为:
使用下列规则,直至每个$FIRST$集不再增大为止:

  • 若$X\in V_T$,则$FIRST(X)={X}$(意思是如果X是终结符,则其FIRST集合为其自身);
  • 若$X\in V_N$,那么$X$的产生式分以下三种情况:

    • $X \to \varepsilon$,则$\varepsilon \in FIRST(X)$
    • $X \to a \cdot \cdot \cdot$,则$a \in FIRST(X)$
    • $X \to Y \cdot \cdot \cdot$,则$FIRST(Y) – \{\varepsilon\} \subseteq FIRST(X)$
    • 特例:$X \to Y_1Y_2 \cdot \cdot \cdot Y_i$,且$Y_1,Y_2,\cdot \cdot \cdot Y_{i-1} \stackrel{*}\Rightarrow \varepsilon$,则$FIRST(Y_i) \subseteq FIRST(X)$

针对最后的特列,用文字说明一下,比方说
$$
A \to BCD \\
B \to b| \varepsilon\\
C \to c|\varepsilon\\
D \to d
$$
那么FIRST(A)={b,c,d},为什么会有c和d,就是因为B可以产生$\varepsilon$,此时相当于$A \to CD$,又因为C也可以产生$\varepsilon$,所以相当于$A \to D$

例题

$$
S \to MH|a \\
H \to LSo| \varepsilon\\
K \to dML| \varepsilon\\
L \to eHf \\
M \to K|bLM
$$
计算所有非终结符的FIRST集
FIRST(S)={a,d,b,e,$\varepsilon$}
FIRST(H)={$\varepsilon$,e}
FIRST(K)={d,$\varepsilon$}
FIRST(L)={e}
FIRST(M)={d,b,$\varepsilon$}

FOLLOW集

我学FOLLOW集的时候,看了很多资料,书,博客,别的学校的慕课,感觉讲的都不是很好,没有一阵见血,所以我在这必须要总结一下
就三步:

  • 设S为文法的开始符号,把(#)加入FOLLOW(S)中
  • 若$A \to \alpha B \beta$是一个产生式,则把$FIRST(\beta)$的非空元素加入$FOLLOW(B)$中
  • $A \to \alpha B \beta$,如果$\beta \stackrel{*}\Longrightarrow \varepsilon$,则把$FLLOW(A)$也加入到$FOLLOW(B)$中

用两句话总结就是:

  • 如果求的$FOLLOW(A)$中A是语法的开始符号,则无条件将#加入到$FOLLOW(A)$中。
  • 如果求$FOLLOW(A)$,先将所有产生式中直接跟在A右边的非终结符的FIRST集(不包括$\varepsilon$)加入FOLLOW(A)。如果该非终结符能通过n(n≥0)次推导出$\varepsilon$或A右边就没有任何符号,则把产生式左部的FOLLOW集也加入到FOLLOW(A)中。

例题

$$
S \to MH|a \\
H \to LSo| \varepsilon\\
K \to dML| \varepsilon\\
L \to eHf \\
M \to K|bLM
$$
计算所有非终结符的FOLLOW集

先说FOLLOW(S),因为S是语法的开始符号,并且S在第二个产生式右边是个终结符o,所以FOLLOW(S)就确定了
$$
FOLLOW(S)=\{o,\#\}
$$
然后看FOLLOW(H),因为H作为产生式右部只有产生式1和产生式4,产生式1中H的右边是空,所以要将FOLLOW(S)加入到FOLLOW(H)中,产生式4中H的右边是终结符f。最终FOLLOW(H)就确定了
$$
FOLLOW(H)=\{o,\#,f\}
$$
最后再说一个例子——FOLLOW(L),L作为产生式右部有产生式2,产生式3,产生式5。在产生式2中,L的右边紧跟着非终结符S,所以将FIRST(S)中的非空元素加入到FOLLOW(L)中,$FOLLOW(L)=FOLLOW(L)\bigcup \{FIRST(S)-\{\varepsilon\}\}$。在产生式3中L右边是空,所以将FOLLOW(K)加入到FOLLOW(L)中。在产生式5中,L右边是M,所以将FIRST(M)中的非空元素加入到FOLLOW(L)中,$FOLLOW(L)=FOLLOW(L)\bigcup \{FIRST(M)-\{\varepsilon\}\}$。

剩下的非终结符的FOLLOW集也是相同的方法求,因为一次扫描可能不够,比方说上面求FOLLOW(L)需要FOLLOW(K),但是FOLLOW(K)暂时没求,所以要等第二次扫描L的时候才能加进来。

答案:

$$ FOLLOW(S)=\{\#,o\}\\ FOLLOW(M)=\{e,\#,o\}\\ FOLLOW(H)=\{\#,f,o\}\\ FOLLOW(L)=\{a,b,d,e,o,\#\}\\ FOLLOW(K)=\{e,\#,o\} $$

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment