FIRST(a)的计算法 设a=X1X2.Xi-1X1.Xn,按以下方法构造集合 n若e庄FIRST(X1)即X1=〉e 则FIRST(a)=FIRST(X); n若任何1≤j≤i-1,2≤≤n,e∈FIRST（Xj) 则X:前所有FIRST(X;)-{e}和FIRST(X:) 加入到FIRST(a)中； n若所有的1≤j≤n,e∈FIRST(X;） 则把e也加入FIRST(a)中； n若a=e,则FIRST(a)={e} 16 ☒
16 FIRST(α) 的计算法 设α=X1 X2 . Xi-1 Xi . Xn，按以下方法构造集合 则FIRST(α) = FIRST（ X1 )； n若任何1≤j≤i-1,2≤i≤n,ε∈FIRST ( Xj ) 则Xi前所有FIRST( Xj )-{ε}和FIRST( Xi ) 加入到 FIRST(α) 中； n若所有的1≤j≤n，ε∈FIRST( Xj ) 则把ε也加入FIRST(α)中； n若α=ε，则 FIRST(α)={ε} n若ε∈ FIRST( X1 ) 即X1==>ε
计算表达式文法候选式FIRST(a)集举例 文法G为： E→TE?E'→+TE?eT→FT?T'→*FT'e 罪婺绪符的FIRST集 候选式的FIRST2集 FIRST(E)={(,i} FIRST(TE')=FIRST(T)={(,i} FIRST(E')={+,e} FIRST(+TE”)={+ FIRST(T)=((,i} FIRST(FT')=FIRST(F)={(,i} FIRST(T')={*,e} FIRST (*FT')={*} FIRST((E))={} FIRST(F)={(,i} FIRST(i)=(i} FIRST(e)={e}
17 计算表达式文法候选式FIRST(α)集举例 候选式的FIRST集 FIRST(TE’)=FIRST(T)={(,i} FIRST(+TE’)={+} FIRST(FT’)=FIRST(F)={(,i} FIRST(*FT’)={*} FIRST((E))={(} FIRST(i)={i} FIRST(ε)={ε} 文法G为： E→TE’ E'→+TE’|ε T→FT’ T'→*FT’|ε 非终结符的 F→(E)|i FIRST集 FIRST(E)={(,i} FIRST(E')={+,ε} FIRST(T)={(,i} FIRST(T')={*,ε} FIRST(F)={(,i}
计算FIRST(a)集合课堂练习 文法G为： S→Ap|Bq A→acA B→dB|e 非终结符的FIRST集 候选式的FIRST集 FIRST(S)={a,c,d,q} FIRST(Ap)=FIRST(A)=(a,c} FIRST(A)=a,c} FIRST(Bq)=FIRST(B)-{e} UFIRST(q) FIRST(B)={d,e} ={d,q} BEGIN FIRST (a)={a} FIRST(cA)={c} FIRST(dB)={d} FIRST(e)={8} 小节目录 18 ☑
18 计算FIRST(α)集合课堂练习 文法G为： S →Ap｜Bq A →a｜cA B → dB｜ε 非终结符的FIRST集 FIRST(S)={a,c,d,q} FIRST(A)={a,c} FIRST(B)={d,ε} BEGIN 候选式的FIRST集 FIRST(Ap)=FIRST(A)={a,c} FIRST(Bq)=FIRST(B)-{ε} ∪FIRST(q) ={d,q} FIRST(a)={a} FIRST(cA)={c} FIRST(dB)={d} FIRST(ε)={ε} 小节目录
F0LL0W(A)的计算法p75 nF0LL0W(A)={a|S==*>.Aa.,a∈Vr} u若S=*>.A,则#∈FOLL0W(A) 重复以下计算，直到每个FOLLOW(A)不再增大为止： n1)将#加入到F0LL0W(S)中 例#∈FOLLOW(E) n2)若A→aBB, 则将FIRST(B)-{e}加入FOLLOW(B) 例E→TE? FIRST(E)-{e}加入 FOLLOW(T) T→FT' FIRST(T)-{e}加入 19 FOLLOW (F)
19 FOLLOW(A)的计算法 p75 n FOLLOW(A)= {a｜S==*>.Aa. ，a∈ＶT } u 若S==*>.A，则#∈FOLLOW（A） 重复以下计算，直到每个FOLLOW(A)不再增大为止： n 1)将 # 加入到 FOLLOW( S )中 例 # ∈ FOLLOW( E ) n 2)若A→αBβ, 则将FIRST(β)-{ε}加入FOLLOW(B) 例 E→TE’ FIRST(E’)-{ε}加入 FOLLOW(T) T→FT’ FIRST(T’)-{ε}加入 FOLLOW(F)
F0LLOW(A)的计算法（续) n3) 若+aB,或{→aBB,一 且B=*>e,即e∈FIRST(B),A≠B 则将FOLLOW(A)所有元素加入FOLLOW(B) 例E→TE' FOLLOW(E)加入 E→T E→e F0LL0wEy拊FOLL0W(T) T路 FO0LL0W(T)加入 T→FTT→ε FOLLOWFOLLOW (F) 20 ☑
20 FOLLOW( A ) 的计算法（续） n 3) 若 A → αB ，或 A → αBβ， 且 β==*>ε，即ε∈ FIRST(β)，A≠B 则将FOLLOW(A)所有元素加入FOLLOW(B) ε 例 E →T E’ FOLLOW(E)加入 FOLLOW(E’) E →T E’ E'→ε FOLLOW(E)加入FOLLOW(T) T →F T’ FOLLOW(T)加入 FOLLOW(T’) T →F T’ T'→ε FOLLOW(T)加入FOLLOW(F)