算法21示例 例G=({S,U,V,W},{a,b,c},PS),其中,P: s→>as|W|U;U→a;V→bv|ac;w→aW 现对G执行算法2.1: V=仍},P1=t 2由U→>a和V→>ac右部都是终结符,vw={U,v}; 3对于sU,由U∈VN有V={s,U,v} 此外再无可放入V的符号,W为无用符号。 G1=({S,U,V},{a,b,c},P1,S),其中,P1为: s→as|UU-av→>bv|ac
6 算法2.1示例 例 G=({S,U,V,W},{a,b,c},P,S)，其中，P: S→aS | W | U；U→a；V →bV |ac；W →aW 现对G执行算法2.1: 1. V’N={}, P1={}; 2.由U→a 和V→ac右部都是终结符,V’N={U,V}; 3.对于S→U,由U V’N 有V’N={S,U,V}; 此外再无可放入V’N的符号，W为无用符号。 G1=({S,U,V},{a,b,c},P1 ,S)，其中， P1为: S →aS | U U→a V →bV |ac
算法22的形式化描述 算法22任给文法G=(VVr,PS)构造 G’=(v"wvr,P',S),使∨X∈(VMV"r),3a,B∈ v∪V")*,有S→*axB (1)置v和P为空,y={s} (2)对于VA→>8∈P,其中A∈Vw则置δ中所有 非终结符入VN,所有终结符入Vr (3)重复(2,直到v和Vr不再增大; (4)令P={A→8|A→8∈P,δ∈(V∪V)*,∈V
7 算法2.2的形式化描述 算法2.2 任给文法G= (VN,VT,P,S),构造 G’=(V’N,V’T,P’,S), 使x (V’NV’T), , (V’N V’T)*, 有 S * x (1)置V’T和P’为空,V’N={S}; (2)对于 A→ P，其中 A V’N，则置中所有 非终结符入V’N ,所有终结符入V’T ; (3)重复(2),直到V’N和V’T 不再增大; (4)令P’={A→ | A→ P, (V’N V’T)*,A V’N}
算法22示例 现对G1=(S,U,V},{a,b,c},P1,S)(P1为:s→aS|U;U>a; V→bV|ac)执行算法22: 1置v={S},置Ⅴr和P为空; 2由SU及U一a将U及a分别放入VN和V"中,V=s,U} VT=fa 3此外,V’N和Vr不再增大; 4最后结果为G=({S,U},{a},P,S),P:S→aS|U;U->a
8 算法2.2示例 现对G1=({S,U,V},{a,b,c},P1 ,S)（ P1为: S →aS | U；U→a； V →bV |ac）执行算法2.2: 1.置V’N ={S}，置V’T和P’为空； 2.由S→U及U →a将U及a分别放入V’N 和V’T中，V ’N={S,U}， V’T={a} 3.此外, V ’N 和V ’T不再增大; 4.最后结果为G’=({S,U},{a},P’,S)，P’：S →aS | U；U→a
已化简文法 注意在删除无用符和无用产生式时,应先执行 算法2.1再执行算法2.2,就可得到“干净” (删除了全部无用符号和无用产生式)的文法 若先执行算法2.2,再执行算法2.1所得文法不 定“干净”。 已化简文法:不含无用符号、无用产生式以及形 如A→>A的产生式的文法
9 已化简文法 • 注意,在删除无用符和无用产生式时,应先执行 算法2.1再执行算法2.2,就可得到“干净” （删除了全部无用符号和无用产生式）的文法; 若先执行算法2.2,再执行算法2.1所得文法不 一定“干净” 。 • 已化简文法：不含无用符号、无用产生式以及形 如A→A的产生式的文法