PPT《编译原理》

二、 LL(1)文法的判别 例:若文法G[S]为: S ? AB | bC A ?ε | b B ?ε | aD C ?AD | b D ?aS | c判别文法是否是LL(1)文法. 解:(1) 计算first集:方法一:计算first 集合的算法:对于每一个文法符号x?V,计算first(x)的方法如下: 若x?VT,则first(x)={x}若x?VN,且有x?a…,a?VT,则a?first(x)若x?VN,x ? ?,则??first(x)若x?VN,y1,y2,…,yi都?VN,产生式x?y1y2…yn,当y1,y2,…yi-1都? ?时(1≤i≤n), 则first(y1)-{?}, first(y2)-{?},…, first(yi-1)-{?},first(yi)都包含在first(x)中.e) 当上式中所有yi ? ? (1≤i≤n),则first(x)=first(y1) ∪first(y2) ∪…∪first(yn) ∪ {?} * * first(S)=first(A)=first(B)=first(C)=first(D)= S ? AB | bCA ?ε | bB ?ε | aDC ?AD | bD ?aS | c 按上面的规则可得上例文法中每个文法符号的first集合如下: first(S)={first(A)-{?}} ∪{first(B)-{?}?} ∪{b}={a,b, ?}first(A)={b} ∪{?}={b, ?}first(B)={?} ∪{a}={a, ?}first(C)={first(A)-{?}} ∪first(D) ∪first(b)={a,b, c}first(D)={a} ∪{c}={a,c} S ? AB | bCA ?ε | bB ?ε | aDC ?AD | bD ?aS | c 按上面的规则可得上例文法中每个文法符号的first集合如下: 一个文法符号串的first集合计算方法: 如果文法符号串??V*, ?=X1X2…Xn,

1、当X1?ε,则first(?)=first(X1)

2、当对任何j(1≤j≤i-1,2 ≤i ≤n),ε?first(Xj) 则first(?)=(first(X1)-{ε}) ∪(first(X2)-{ε}) ∪…∪(first(Xi-1)-{ε}) ∪first(Xi)

3、当first(Xj)都含有ε时(1 ≤ j ≤ n),则first(?)=first(X1) ∪first(X2) ∪…∪first(Xj) ∪{ε} * 根据上面规则,每个产生式的右部符号串开始符号集合为:first(AB)=first(bC)=first(ε)= first(aD)=first(AD)=first(b)=first(aS)=first(c)= 根据上面规则,每个产生式的右部符号串开始符号集合为:first(AB)=first(A) ∪first(B) ∪{ε}={a, b, ε}first(bC)={b}first(ε)={ ε} 根据规则2因为A ?εD?ε first(aD)={a}first(AD)=(first(A)-{ε}) ∪first(D)={a,b,c}first(b)={b}first(aS)={a}first(c)={c} 根据规则3因为A ?εB?ε 方法二:........