编译原理FIRST、FOLLOW、SELECT集の通俗解释

1.为什么要引入FIRST集的概念？

• 因为有公共左因子的问题，公共左公因子是指在文法的产生式集合中，某个非终结符的多个候选式具有相同的前缀。
• 一般来说，公共左公因子的产生式为 
  
  A→αβ1│αβ2A→αβ1│αβ2
• 如果有公共左因子的问题，那么只能采取试探的方法来分析每一个候选式，分析的过程很可能产生回溯，回溯分析法是一种不确定的方法。
• 若所有候选式都没有公共左因子就可以选择惟一匹配的候选式，不会产生(公共左公因子引起的)回溯。
• 为了消除回溯，对任何一个非终结符和当前的待匹配符号，期望 
  
  • 要么只有一个候选式可用
  • 要么没有候选式可用

因此引入以下FIRST集合的概念:

• 对α∈(VT⋃VN)∗α∈(VT⋃VN)∗,有 
  
  FIRST(α)＝{a|α⟹∗a⋅⋅⋅,a∈VT}FIRST(α)＝{a|α⟹∗a⋅⋅⋅,a∈VT}
  
  特别地，若α⟹∗εα⟹∗ε,则ε∈FIRST(α)ε∈FIRST(α)

因此对于每一文法符号 X∈VT⋃VNX∈VT⋃VN，构造FIRST(X)FIRST(X)的方法为: 
使用下列规则，直至每个FIRST集不再增大为止：

• 若X∈VTX∈VT，则FIRST(X)={X}FIRST(X)={X}(意思是如果XX是终结符，则其FIRSTFIRST集合为其自身)；

• 若 X∈VNX∈VN，那么XX的产生式分以下三种情况:

  • X→εX→ε
  • 则ε∈FIRST(X)ε∈FIRST(X)
  • X→a⋅⋅⋅X→a⋅⋅⋅
  • 则a∈FIRST(X)a∈FIRST(X)
  • X→Y⋅⋅⋅X→Y⋅⋅⋅，且Y∈VNY∈VN

  • 则FIRST(Y)–{ε}⊆FIRST(X)FIRST(Y)–{ε}⊆FIRST(X)

  • 特例: X→Y1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅YkX→Y1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk 
    且 Y1,Y2,⋅⋅⋅Yi−1∈VNY1,Y2,⋅⋅⋅Yi−1∈VN 
    Y1,Y2,⋅⋅⋅Yi−1⟹∗εY1,Y2,⋅⋅⋅Yi−1⟹∗ε

    • 则FIRST(Yj)–{ε}⊆FIRST(X)(1≤j≤i−1)，FIRST(Yi)⊆FIRST(X)FIRST(Yj)–{ε}⊆FIRST(X)(1≤j≤i−1)，FIRST(Yi)⊆FIRST(X)

  • 特别地，当Y1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk⟹∗εY1Y2⋅⋅⋅Yi−1Yi⋅⋅⋅Yk⟹∗ε

    • 则 ε∈FIRST(X)ε∈FIRST(X)

结论:针对无空产生式的文法G，同一非终结符的任两个产生式的右部符号串的FIRST集无交集，即可进行确定的自顶向下分析。

2.为什么要引入FOLLOW集的概念？

考虑文法G[S]: 
S→aAS→aA 
S→dS→d 
A→bASA→bAS 
A→εA→ε 
求得各终结符和符号串的FIRST集合如下: 
FIRST(S)={a,d}FIRST(S)={a,d} 
FIRST(A)={b,ε}FIRST(A)={b,ε} 
FIRST(aA)={a}FIRST(aA)={a} 
FIRST(d)={d}FIRST(d)={d} 
FIRST(bAS)={b}FIRST(bAS)={b} 
FIRST(ε)={ε}FIRST(ε)={ε} 
若输入串W=abdW=abd，则试图推导出abd串的推导过程为S⇒aA⇒abAS⇒abS⇒abdS⇒aA⇒abAS⇒abS⇒abd 
从以上推导过程中可以看到，在第2步到第3步的推导中，即abAS⇒abSabAS⇒abS时，因为当前面临的输入符号为dd，但是最左非终结符AA的产生式右部的开始符号集都不包含dd，但有εε，因此对于dd的匹配自然认为只能依赖于在可能的推导过程中AA的后面的符号，所以这时候选用产生式A→εA→ε向下推导。而当前AA后面的符号为SS，SS产生式右部的开始符号集包含了dd，所以例子中可用S→dS→d推导得到匹配。 
语法树如下所示: 
 
很显然，我们从以上叙述中可以得出: 
当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的开始符号集两两不相交，并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。因此，引入了一个文法符号的后跟符号集合。 
引入以下FOLLOW集的概念:

• 对A∈VNA∈VN，有 
  FOLLOW(A)={a|S⟹∗⋅⋅⋅Aa⋅⋅⋅，a∈VT}FOLLOW(A)={a|S⟹∗⋅⋅⋅Aa⋅⋅⋅，a∈VT} 
  若S⟹∗⋅⋅⋅AS⟹∗⋅⋅⋅A，则规定#∈FOLLOW(A)#∈FOLLOW(A) 
  这里用#作为输入串的结束符，也称为输入串括号。

因此对于每一文法符号 A∈VNA∈VN，实际上求FOLLOW(A)FOLLOW(A) 
就是考察A在产生式右端的出现情况，哪些终结符号可以跟随在A后面？

使用下列规则，直至每个FOLLOW集不再增大为止：

• 首先，设S为文法的开始符号，把{#}{#}加入FOLLOW(S)FOLLOW(S)中(这里#为句子括号)
• 若B→αAβB→αAβ是一个产生式，则 FIRST(β)−{ε}⊆FOLLOW(A)FIRST(β)−{ε}⊆FOLLOW(A)
• 如果B→αAB→αA或者B→αAβB→αAβ且β⟹∗εβ⟹∗ε，则 FOLLOW(B)⊆FOLLOW(A)FOLLOW(B)⊆FOLLOW(A) 
  
  • 解释: 因为在推导过程中可能出现如下的句型序列:
  • S⇒∗⋅⋅⋅α1Bβ1⋅⋅⋅⇒⋅⋅⋅α1αAββ1⋅⋅⋅⇒⋅⋅⋅α1αAβ1⋅⋅⋅S⇒∗⋅⋅⋅α1Bβ1⋅⋅⋅⇒⋅⋅⋅α1αAββ1⋅⋅⋅⇒⋅⋅⋅α1αAβ1⋅⋅⋅

例题: 
A→BCc | gDBA→BCc | gDB 
B→bCDE | εB→bCDE | ε 
C→DaB | caC→DaB | ca 
D→dD | εD→dD | ε 
E→gAf | cE→gAf | c

对于FIRST集合，解释其中的FIRST(A)的求解。

• A→BCcA→BCc属于上述产生式的特例情况，很显然B⇒∗ε，C⇏∗εB⇒∗ε，C⇏∗ε，因此 
  (FIRST(B)−{ε})⋃FIRST(C)⊆FIRST(A)(FIRST(B)−{ε})⋃FIRST(C)⊆FIRST(A)
• A→gDBA→gDB属于上述产生式的第二种情况，因此g∈FIRST(A)g∈FIRST(A)
• 最后得出: 
  FIRST(A)=(FIRST(B)−{ε})⋃FIRST(C)⋃{g}FIRST(A)=(FIRST(B)−{ε})⋃FIRST(C)⋃{g}
• 而FIRST(B)={b,ε}，FIRST(C)={a,c,d}FIRST(B)={b,ε}，FIRST(C)={a,c,d}
• 故FIRST(A)={a,b,c,d,g}FIRST(A)={a,b,c,d,g}

对于FOLLOW集合，有如下的计算情况:

3.为什么要引入SELECT集的概念？

由于从2中我们得出结论: 
当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的开始符号集两两不相交，并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。 
因此当文法中含有形如： 

• 一个产生式的选择符号集SELECT。给定上下文无关文法的产生式A→α,A∈VN,α∈V∗A→α,A∈VN,α∈V∗，若α⇏∗εα⇏∗ε，则SELECT(A→α)=FIRST(α)SELECT(A→α)=FIRST(α)。

• 如果α⇒∗εα⇒∗ε，则SELECT(A→α)=(FIRST(α)−{ε})⋃FOLLOW(A)SELECT(A→α)=(FIRST(α)−{ε})⋃FOLLOW(A)。

因此一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式，A→α，A→βA→α，A→β，满足 

再次回到上述例题

A→BCc | gDBA→BCc | gDB 
B→bCDE | εB→bCDE | ε 
C→DaB | caC→DaB | ca 
D→dD | εD→dD | ε 
E→gAf | cE→gAf | c

  因此根据以上所求得的FIRST集和FOLLOW集，可求得各产生式的SELECT集合如下：