FIRST集的定义 : 设G=(VT,VN,P,S)是上下文无关文法 FIRST(a)={a|a=>*ab,a∈VT, a,b∈V*} 若a=>*ε则规定ε∈FIRST (a) FIRST(α)就是从α可能推导出的所有开头终结符号和可能的ε所构成的集合。
FIRST集的分析方法 :
对于文法中的符号X∈VN∪VT,其FIRST(X)集合可反复应用下列规则计算,直到其FIRST(X)集合不再增大为止:
1)若 X∈VT,则FIRST(X)={X}。
2)若X∈VN,且具有形如X→aα的产生式(a∈VT),或具有形如X→ε的产生式,则把a或ε加进FIRST(X)。//把X能推出的第一个终结符加入FIRST(X)。
3) 设G中有形如X→Y1…Yk的产生式,其中X,Y1…Yk∈VN,且Y1…Yi-1均能=>*ε(1≤i≤k),则FIRST(Y1)-{ε},…, FIRST(Yi-1)-{ε},FIRST(Yi)都包含在FIRST(X)中。// Yi推导不出ε,所以Yi+1不在FIRST(X)中。
4) 若对一切1≤i≤k,均有ε∈FIRST(Yi),则将ε符号加进FIRST(X)。//若X=>*ε,则将ε加入FIRST(X)。
FIRST集的求法:
对于文法G的任一符号串α=X1X2…Xn可按下列步骤构造其FIRST(α)集合:
1) 置FIRST(α)=φ
2) 将FIRST(X1)中的一切非ε符号加进FIRST(α);
3) 若ε∈FIRST(X1),将FIRST(X2)中的一切非ε符号加进FIRST(α);若ε∈FIRST(X1)和FIRST(X2),将FIRST(X3)中的一切非ε符号加进FIRST(α);依次类推。//根据分析方法中的第3条,若该符号能推出ε则将下一个符号的FIRST集加入FIRST(α),以此类推。
4)若对于一切1≤i≤n,ε∈FIRST(Xi),则将ε符号加进FIRST(α)。 //根据分析方法的第4条,若右侧符号串的每个符号都能推出ε,则α肯定能推出ε,所以将ε加进FIRST(α)。
例:
E →TE’
E’→+TE’
E’→ε
T →FT’
T’→*FT’
T’→ε
F→(E)|i
FIRST(E)=FIRST(T)=FIRST(F)={ ( ,i } //FIRST(T)不包含ε,所以FIRST(E)不包含FIRST(E’),根据求法的第3条,T无法推出ε为向右类推的终止条件。同理:FIRST(T)不包含FIRST(T’)。
FIRST(E’)= { + ,ε}
FIRST(T’)={ * ,ε}
//遇到E →TE’这样的产生式,先把FISRT(T)放入FIRST(E),再看看T能否推导出ε,若能推出,则把FIRST(E’)放入FIRST(E),以此类推。
若T不能推出ε,则FIRST(E)求完了。若遇到终结符,请看分析方法第一条。
FOLLOW集定义 FOLLOW(A)={a| S=>*mAb 且a∈FIRST(b),m∈V*,b∈V+} 若 S=>*uAb, 且b =>*ε,则#∈FOLLOW( A)。
FOLLOW集的计算
1. 对于文法的开始符号S,置#于FOLLOW(S) 中;
2. 若A→αBβ是一个产生式,则把FIRST(β)-{e}加至FOLLOW(B)中;若β=>*e (即eÎFIRST(β)),则把FOLLOW(A)加至FOLLOW(B)中。//若B有可能是最后一个符号,则把
FOLLOW(A)加至FOLLOW(B)中,否则把FIRST(β)- {e}加至FOLLOW(B)中。
反复使用上述规则,直到所求FOLLOW集不再增大为止。
注意: 在FOLLOW集合中无ε。
//FIRST集从产生式左侧推导,而FOLLOW集从产生式右侧推导。例如求A的FIRST集,要先从产生式左侧找到A,然后根据产生式右侧的信息求出A的FIRST集;求A的FOLLOW集时,要先从产生式右侧找到A,然后根据A右侧的符号信息求出A的FOLLOW集。
例:
E→TE’,
E’→+TE’,
E’→ε,
T→FT’,
T’→*FT’,
T’→ε,
F→(E)|i
FOLLOW(E)= {),#},//E为开始符号,加入#,E的后面有终结符)
FOLLOW(E’)= FOLLOW(E)={ ) ,# } //第一个产生式中E’是最后一个符号,所以FOLLOW(E’)中加入FOLLOW(E)。
FOLLOW(T)={FIRST(E’)-{e}}∪FOLLOW(E)∪FOLLOW(E’) = { + , ) , # } //第一个产生是中T后面有非终结符E’,所以在FOLLOW(T)中加入{FIRST(E’)-{e}},而E’→ε,所以T有可能是最后一个符号,所以把FOLLOW(E)加入FOLLOW(T);同理第二个产生式中,要把FOLLOW(E’)加入FOLLOW(T)。
FOLLOW(T’)= FOLLOW(T)= { + , ) , # }
FOLLOW(F)={FIRST(T’)-{e}})∪FOLLOW(T)∪FOLLOW(T’) = {+,*,) ,# }