北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）第二章 前后文无关文法和语言 2.4 文法的化简与改造 2.5 文法和语言的Chomsky分类

24文法的化筒与改滋 S4PMOAWMAMHZIAWIESMPMOHAWHMAMHZIAV 对文法进行化简和改造 希望定义语言的文法尽可能简单 某些语法分析技术对文法有要求和限制:LL分析 要求文法无左递归;算符优先分析要求文法不含 有8产生式;LR分析要求文法无二义性 本节主要内容 无用符号和无用产生式的删除 8-产生式的消除 单产生式的消除

1 2.4 文法的化简与改造 • 对文法进行化简和改造 – 希望定义语言的文法尽可能简单 – 某些语法分析技术对文法有要求和限制：LL分析 要求文法无左递归；算符优先分析要求文法不含 有-产生式；LR分析要求文法无二义性 • 本节主要内容 – 无用符号和无用产生式的删除 – -产生式的消除 – 单产生式的消除

无用符号和无用产生式的除 无用符号和无用产生式 设G=(V,Vr,P,S)是一文法,X∈V,X称为是有用的,若X至 少出现在一个句子的推导过程中,即X满足: (1)存在aB∈V*,有S→*axB (212) (2)存在w∈Vr,使αXβ→*w 213) 否则,称X是无用的。 若一产生式含有无用符号,则此产生式称为无用产生式。 无用产生式给语法分析带来了许多麻烦,应予以 删除

2 无用符号和无用产生式的删除 • 无用符号和无用产生式 设G=(VN,VT,P,S)是一文法, XV, X称为是有用的, 若X至 少出现在一个句子的推导过程中, 即X满足: (1) 存在, V* ,有 S* X (2.12) (2) 存在w VT*,使 X * w (2.13) 否则，称X是无用的。 若一产生式含有无用符号，则此产生式称为无用产生式。 • 无用产生式给语法分析带来了许多麻烦，应予以 删除

无用符号和无用产生式的识别 找出文法G中的全部无用符号,删除这些无用 符号以及包含它们的所有产生式。 识别文法G中的无用符号:对于任一符号Ⅹ, 如果X是有用的,则 Ⅹ至少出现在一个句型中(条件2.12),否则,用 算法22进行改造 符号X能推导出终结符号串(条件2.13),否则, 用算法2.进行改造

3 无用符号和无用产生式的识别 • 找出文法G中的全部无用符号，删除这些无用 符号以及包含它们的所有产生式。 • 识别文法G中的无用符号：对于任一符号X， 如果X是有用的，则 – X至少出现在一个句型中（条件2.12），否则，用 算法2.2进行改造 – 符号X能推导出终结符号串（条件2.13），否则， 用算法2.1进行改造

改造算法 算法21将文法G=(Vr,PS)改造为 G=(Vvr,P1S),使得对于每个X∈V”,存在w ∈V,满足X→*w 算法22任给文法G=(VVr,PS),构造 G=Vwvn,P’,S),使x∈(VwV,孔aB∈ ∪V")*,有S→*axB

4 改造算法 算法2.1 将文法G = (VN,VT,P,S),改造为 G1=(V’N,VT,P1 ,S),使得对于每个X  V’N,存在w VT*,满足 X* w. 算法2.2 任给文法G= (VN,VT,P,S),构造 G’=(V’N,V’T,P’,S), 使x (V’NV’T), ,  (V’N V’T)*, 有 S * x

算法2的形式化描述 算法21将文法G=(,vr,PS),改造为G=(v,v,P1,S),使 得对于每个X∈V,存在w∈Ⅵ,满足X→*w. 1)置vP1为空; (2)对于P中每个产生式A→>8若8∈(VV),则将A加入 v中 (3)重复(2),直到v不再增大; (4)对于每个A→>6∈P,若δ∈(Vw),则置A→>8于P中

5 算法2.1的形式化描述 算法2.1 将文法G = (VN,VT,P,S),改造为G1=(V’N,VT,P1 ,S),使 得对于每个X  V’N,存在w VT*,满足 X* w. (1)置V’N,P1为空; (2)对于P中每个产生式A→,若  (V’NVT)*,则将A加入 V’N中; (3)重复(2),直到V’N不再增大; (4)对于每个A→ P,若   (V’NVT)*,则置A→ 于P1中

算法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’NV’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的产生式的文法

24.2产生式的消除 -产生式是指右部为一空符号串的产生式。因 为某些语法分析算法要求不含8-产生式,因此 应消除。 若一语言不含E(即eELG,则可全部消除文法 中的8-产生式;否则文法中的8-产生式不能全 部消除。 可对E∈LG)的文法进行改造 开始符S可推导出E(即S→E∈P),此外再无其它-产 生式。 S不出现在任何产生式的右部

10 2.4.2 -产生式的消除 • -产生式是指右部为一空符号串的产生式。因 为某些语法分析算法要求不含-产生式，因此 应消除。 • 若一语言不含（即L(G)),则可全部消除文法 中的-产生式；否则文法中的-产生式不能全 部消除。 • 可对L(G)的文法进行改造 – 开始符S可推导出(即S→ P)，此外再无其它-产 生式。 – S不出现在任何产生式的右部