4.2LL(1)文法的判别p72 ■FIRST集合的计算 ■FOLLOW集合的计算 ■SELECT集合的计算 ■LL(1)文法的判别举例 ■LL(1)文法判别课堂练习 章节目录 16
16 4.2 LL(1)文法的判别 p72 ◼FIRST集合的计算 ◼FOLLOW集合的计算 ◼SELECT集合的计算 ◼LL(1)文法的判别举例 ◼LL(1)文法判别课堂练习 章节目录
FIRST(a)的计算法 定义和关系图p73 ■FIRST(a)={a|a==*>a.,a∈Vr} ◆若a=*>e,则e∈FIRST(a) ■计算文法符号X的FIRST(X) ■计算文法符号串a=X1X2.Xn的FIRST(a) 進 17
17 FIRST(α)的计算法 ——定义和关系图 p73 ◼FIRST(α)={ a｜α ==*> a . ，a∈ＶT } ◆若α ==*>ε，则ε∈ FIRST(α) ◼计算文法符号X的FIRST（X） ◼计算文法符号串α=X1X2.Xn的FIRST(α)
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') 18
18 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’）
-{e} 口3)若有X→Y.,且Y∈VN, 则FIRST(Y)-{e}加入FIRST(X); 例F→(E)|i FIRST()={(,i} T-FT'FIRST(T)=FIRST (F)-{e}={(i} -{e} 口若有X→Y1.Yi-1Yi.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)。 19
19 若有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.Y1-1Y.Yk FIRST(X)集举例 若有文法G为： FIRST:集 X→Y1Y2Y3Y4Y5 Y1 a, Y1 →a|e Y2 b, e Y2 → b e Ys C> e ==*>e Y4 d, e Y3 c e Y5 e,fe Y4 → dl e Y5 e |fe X a,b,c,d,e,fe → 因为Y5卡粉e, 所以e在FIRST(X) 因为Y5=)e, 所以e∈FIRST) I
20 计算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）