FIRST(X)的计算法p73 重复以下计算，直到FIRST(X)不再增大为止： 1)若X∈Vr,则FIRST(X)={X}。 例FIRST(+)={+} FIRST (i)={i) 2)若X∈VN, 若有X→a.,则将a加入FIRST(X); 例E'→+TE' +∈FIRST(E') F→(E)i(,i∈FIRST(F) 若有X→e,则将e加入FIRST(X)。 例E’→e e∈FIRST(E') 16
16 FIRST( X )的计算法 p73 重复以下计算，直到FIRST（X）不再增大为止: 1) 若 X∈ＶT，则 FIRST( X ) = { X }。 例 FIRST（+）={+} FIRST（i）={i} 2) 若 X∈ＶN， 若有X→a.，则将 a 加入FIRST(X)； 例 E'→+TE' +∈FIRST(E’) F→（E）|i （，i∈FIRST（F） 若有X →ε，则将ε加入FIRST( X )。 例 E’→ε ε∈FIRST（E’）
-{ε} 口3)若有X→Y.,且Y∈VN, 则FIRST(Y)-{e}加入FIRST(X); 例F→(E)|i FIRST(F)={(,i} T-FT'FIRST(T)=FIRST(F)-{e}={(,i] -{ε} 0 若有X→Y1.Yi-1Y.Yk,并对于某个i, 有1≤j≤i-1,e∈FIRST(Y), 即Y1,Yi-1=*)e, 则将所有FIRST(Y;)-{e}UFIRST(Yi)-{e} 加入FIRST(X)中； 口若所有Y1,Yk=)e,则将e加入到FIRST(X)。 17 ☑
17 若有X → Y1.Yi-1Yi.Yk ，并对于某个i， 有1≤j≤i-1，ε∈FIRST（Yj）， 即Y1 ，.，Yi-1==*>ε， 则将所有FIRST( Yj )-{ε}∪FIRST( Yi )-{ε} 加入FIRST( X )中； -{ε} 3)若有 X → Y.，且 Y ∈ＶN ， 则 FIRST(Y)-{ε}加入FIRST(X); 例 F→(E)|i FIRST(F)={（，i} T→FT' FIRST(T)=FIRST(F)-{ε}={（，i} 若所有Y1,.,Yk==*>ε，则将ε加入到 FIRST( X )。 -{ε}
计算X→Y1.Yi-1Yi.Yk FIRST(X)集举例 若有文法G为： FIRST:集 X→Y1Y2Y3Y4Y5 Yi a, Y1 →ae Y2 b, e Y2 → b|e Ys C, e Y4 d,s Y3 → Y5 e,fe Y4 → d| e X la,b,c,d,e,fe Y5 → 因为Y5卡>e,所以e在FIRST(X) 因为Y5==)e,所以e∈FIRST(&)
18 计算X→Y1.Yi-1Yi.Yk FIRST(X)集举例 若有文法G为： X → Y1 Y2 Y3 Y4 Y5 Y1 → a｜ε Y2 → b｜ε Y3 → c｜ε Y4 → d｜ε Y5 → e｜f FIRST集 Y1 Y2 Y3 Y4 Y5 X a，ε b，ε c，ε d，ε e，f a,b,c,d, e,f ε ε 因为Y5==*>ε， 所以ε∈FIRST（X） ε ==*>ε ==*>ε 因为Y5==*>ε， 所以ε∈FIRST（X）
计算表达式文法FIRST(X)集举例 文法G为： 口先找以终结符开头的产生式 B→T FIRST(F)={(,i} E’→+TE’|e FIRST(E')={+,8} T-FT FIRST(T')={*,8} 口再找右部以非终结符开头的产生式 T→米FT’|ε FIRST(T)=FIRST(F) F→(E)i FIRST(E)=FIRST(T) ={（,i} 19 ☒
19 计算表达式文法FIRST(X)集举例 文法G为： E →T E’ E'→+ T E'｜ε T →F T' T'→* F T'｜ε F →( E )｜i 先找以终结符开头的产生式 FIRST( F ) = { ( ,i } FIRST( E' ) = { + ，ε} FIRST( T' ) = { * , ε} 再找右部以非终结符开头的产生式 FIRST( T ) = FIRST( F ) FIRST( E ) = FIRST( T ) = { ( ,i }
计算FIRST(X)集合课堂练习 ▣先找以终结符开头的产生式 文法G为： FIRST(A)={a,c S→Ap|Bq FIRST(B)={d,e} A→a cA 口再找右部以非终结符开头的产生式 FIRST(S)=FIRST(A)-{8} B→dB|e UFIRST(B)-{8} BEGIN 因为B=〉e UFIRST(q) ={a,c,d,q} e年FIRST(S),因为S=十*>e 20
20 计算FIRST(X)集合课堂练习 ={a，c，d，q} 文法G为： S →Ap｜Bq A →a｜cA B →dB｜ε BEGIN 先找以终结符开头的产生式 FIRST(A)={ a ,c } FIRST(B)={ d ,ε} 再找右部以非终结符开头的产生式 FIRST(S)= FIRST(A)-{ε} ∪FIRST(B)-{ε} 因为B==>ε ε∈FIRST(S),因为S==*>ε ∪FIRST(q)