计算X→Y1.Y-1Y.Yk FIRST(X)集举例 若有文法G为： FIRST:集 X→Y1Y2Y3Y4Y5 Y1 a, e Y1 →a Y2 b, e Y2 → e e Y3 C, Y3 → c|e ==*>E Y4 d, e Y5 e,fe Y4 → e Y5 → e l fe X a,b,c,d,e,fs 因为Y5丰*>e, 所以e在FIRST (X) 因为Y6=>e， 所以e∈FIRST(X) ☒D
11 计算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)的计算法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') 12 ☒
12 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)-{}={(,i} -{ε} u若有X→Y1Y-Y.Yk,并对于某个i, 有1≤j≤i-1,e∈FIRST(Y), 即Y1,Yi-1=*>e, 则将所有FIRST(Y;)-{e}UFIRST(Y:)-{e} 加入FIRST(X)中； u若所有Y,Y)8,则将e加入到FIRST(X)。 13
13 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 )。 -{ε}
计算表达式文法FIRST(X)集举例 文法G为： n先找以终结符开头的产生式 E→TE' FIRST(F)={（,i} E'→+TE’e FIRST(E')={+, T-FT FIRST(T)={米，e} n再找右部以非终结符开头的产生式 T’→*FT’|e FIRST(T)=FIRST(F F→(E)|i FIRST(E )FIRST(T) ={（,i} 14
14 计算表达式文法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)集合课堂练习 先找以终结符开头的产生式 文法G为： FIRST(A)={a c S→Ap|Bq FIRST(B)={d,e} A→acA 再找右部以非终结符开头的产生式 FIRST(S)=FIRST (A)-8} B→dB|e UFIRST(B)-{} BEGIN 因为B=〉e UFIRST(q) =fa,c,d,qh e年FIRST(S),因为S=+*>e 4 15
15 计算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)