FIRST(X)的计算法D73 重复以下计算，直到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’）
-{ε} n3)若有X→Y.,且Y∈VN, 则FIRST(Y)-{e}加入FIRST(X); 例F→(E)|i FIRST(F)={(,i} T-FT'FIRST(T)=FIRST (F)-{e}={(,i) u若有一，并对于装个， 有1≤j≤i-1,e∈FIRST(Y), 即Y1,Yi-1=*)e, 则将所有FIRST(Y;)-{e}UFIRST(Y;)-{e} 加入FIRST(X)中； u若所有Y1,Y=),则将e加入到FIRST(X)。 可时
17 u 若有X → Y1.Yi-1Yi.Yk ，并对于某个i， 有1≤j≤i-1，ε∈FIRST（Yj）， 即Y1 ，.，Yi-1==*>ε， 则将所有FIRST( Yj )-{ε}∪FIRST( Yi )-{ε} 加入FIRST( X )中； -{ε} n3)若有 X → Y.，且 Y ∈ＶN ， 则 FIRST(Y)-{ε}加入FIRST(X); 例 F→(E)|i FIRST(F)={（，i} T→FT' FIRST(T)=FIRST(F)-{ε}={（，i} u若所有Y1,.,Yk==*>ε，则将ε加入到 FIRST( X )。 -{ε}
计算X→Y1.Y-1Y.Yk FIRST(X)集举例 若有文法G为： FIRST:集 X→Y1Y2Y3Y4Y5 Y1 a, e Y1 →a Y2 b, e Y2 Y3 C, e Y3 c|e ==*> Y4 d, e → Y5 e,fe Y4 → d|e Y5 X a,b,c,d,e,fs → e l fe 因为Y5丰*>e, 所以e在FIRST (X) 因为Y6=〉e, 所以e∈FIRST(X)
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为： n先找以终结符开头的产生式 E→TE' FIRST(F)={(,i} E'→+TE’e FIRST(E')={+,e} FIRST(T)={米，e} n再找右部以非终结符开头的产生式 T’→*FT’|e FIRST(T)=FIRST(F F→(E)Ii 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 n先找以终结符开头的产生式 FIRST( F ) = { ( ,i } FIRST( E' ) = { + ，ε} FIRST( T' ) = { * , ε} n再找右部以非终结符开头的产生式 FIRST( T ) = FIRST( F ) FIRST( E ) = FIRST( T ) = { ( ,i }
计算FIRST(X)集合课堂练习 n先找以终结符开头的产生式 文法G为： FIRST(A)={a c S→Ap I Bq FIRST(B)={d,e} A→acA n再找右部以非终结符开头的产生式 FIRST(S)=FIRST(A)-{e} B→dB|e UFIRST(B)-{} BEGIN 因为B=〉e UFIRST(q) =fa,c,d,qh e年FIRST(S),因为S=+*>e 4 20
20 计算FIRST(X)集合课堂练习 ={a，c，d，q} 文法G为： S →Ap｜Bq A →a｜cA B →dB｜ε BEGIN n先找以终结符开头的产生式 FIRST(A)={ a ,c } FIRST(B)={ d ,ε} n再找右部以非终结符开头的产生式 FIRST(S)= FIRST(A)-{ε} ∪FIRST(B)-{ε} 因为B==>ε ε∈FIRST(S),因为S==*>ε ∪FIRST(q)