Yn;当Y1 Y2 … Yi-1都ε时,(其中1≤i≤n),则FIRST(Y1){ε}、FIRST(Y2) -{ε} 、…、FIRST(Yi-1)- {ε},FIRST(Yi) 都包含在FIRST(X)中
(e) 当(d)中所有Yi * ε,(i=1,2,…n),则 FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}
一 . 自上而下语法分析方法
给定文法G和源程序串$。从G的开始符 号S出发,通过反复使用产生式对句型中的 非终结符进行替换(推导),逐步推导出$ 。
是一种产生的方法,面向目标的方法。 分析的主旨是选择产生式的合适的侯选 式进行推导,逐步使推导结果与$匹配。
Ch4 语法分析 4.1 语法分析程序综述 4.1.2 语法分析的方法
计算Select集:
B ε | aD C AD | b
每个产生式的Select集合计算为:D aS | c
Select(SAB)= (first (AB) -{ε}) ∪Follow(S)={b,a,#}
Select(S bC)= first (bC)={b}
因为A B
Select(Aε)=(first (ε) -{}) ∪Follow (A)={c,a,#}
A ε | b B ε | aD C AD | b D aS | c
first(C)={first(A)-{}} ∪first(D) ∪first(b)={a,b, c}
first(D)={a} ∪{c}={a,c}
➢求出每个文法符号的FIRST集合后也就不难求出一个符号 串的FIRST集合
✓若符号串α∈V*,α=X1 X2 … Xn,当X1不能
∪{ε}
ε*,则置 ∈