北京交通大学 于双元 4
算法2.1,文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等 价文法G1=(Vn①,Vt,P ①,S),对于每个X∈Vn① ,都有 w1∈Vt*,满足X=*>w1; 步骤: (1)分别置Vn①和P①为Φ; (2)对P中的每一个产生式A→δ,若δ∈Vt*,则将A置 于 V n①中 ;
B→Bb︱b }
∪{A→aAb︱ab} ∪{B→Bb︱b}
为所求,G[S]与 G1[S]等价.
北京交通大学 于双元
17
§2.4.4 文法的其它表示方法
一、扩充的BNF表示 BNF:元符号 < , > , ::=(→), ∣ 扩充的BNF(EBNF): < , > , ::=(→), ∣, ( , ) ,{,},[,] 1、{ }
北京交通大学 于双元 21
Vt (2) B ∈Vn
a
B
(3)形如U →x1 |x2 |…… |xn x1 x2 …… xn
北京交通大学 于双元 22
X=y1y2……yn
X={y}
y1
y2
… …
yn
y
例：G[Z]: Z →x |(B) x ( Z Z 例C语言中的 <复合语句> { 语句 ;
Wk+1(Ai)=Wk(Ai)∪{D︱C →D ∈P,C∈Wk(Ai),D ∈Vn} k≧1
则必存在一个j,使Wj(Ai)=Wj+1(Ai)=… 令 W(i)=Wj(Ai) (i=1,2,…,n) 即W(i)={B︱Ai*=>B,B ∈Vn} Ai本身在集合中
北京交通大学 于双元 15
算法2.6 (2)构造产生式集合
G＇执行算法2.4 得G1 G1[S① ]: S① →cS︱AB︱c︱A︱B︱ε S→ cS︱AB︱c︱A︱B A→aAb︱ab B→Bb︱b 为所求
北京交通大学 于双元
14
§2.4.3 单产生式的消除
设G=(Vn,Vt ,P,S)是一文法,假定G中不含ε-产生式, 执行算法2.6得到不含单产生式的文法G′. 算法2.6 (1)设Vn={A1,A2,..,An},对每个Ai(1≦i≦n), 作集合序列 W1(Ai)={Ai}
北京交通大学 于双元
10
算法2.５
设G=(Vn,Vt,P,S), 且ε属于L(G)，则按下述算法构造 G1=(Vn①,Vt,P①,S①), 使L(G1)=L(G),且除S ① → ε外, P ①不 含另外ε产生式．此外, S ①不出现在任何产生式的右部.
情况1:S不出现在原文法任何产生式的右部 设G=(Vn,Vt,P,S), 且ε属于L(G)，S属于W, 执行算法2.4得 G′=(Vn,Vt,P′,S), 但S→ε属于G′ 令P①=P′∪{S→ε}, Vn① = Vn, S① = S 则G1=(Vn①,Vt,P①,S①)为所求.
北京交通大学 于双元
9
算法2.4
设G=(Vn,Vt,P,S), 且ε不属于L(G)，则按下述算法构造 G′=(Vn,Vt,P′,S), 使L(G′)=L(G),且不含ε产生式．
①按算法2.3将Vn分为两个不相交的子集，W及Vn－W ②设X →X1X2…Xm是P中的任一产生式，按下述规则将所有形 X→Y1Y2…Ym的产生式放入P′中，对于一切1<=i<=m (ⅰ)若Xi不属于W,即Xi属于（Vn－W）∪Vt,则取Yi=Xi ; (ⅱ)若Xi属于W,则Yi分别取为Xi和ε,即如果Y1Y2…Ym中有j 个符号属于W，则将有２j个形如Y→Y1Y2…Ym的产生式放入P′ 中，但若所有的Xi均属于W,却不能把所有的Yi都取ε 。
北京交通大学 于双元 23
B →ZC C →{+Z}
) + }
§2.5 文法和语言的Chomsky分类 文法是一个四元组G=（Vn，Vt，P，Z） 乔姆斯基根据文法中P的不同，将文法分为 四类,每一种文法对应一种语言. 0型文法：文法G中规则呈 α→β α∈V+，β∈V* 也称短语结构文法（PSG） 确定的语言为0型语言L0
(不含左递归)
<无符号整数>→<数字> { <数字>} <数字> →0 ∣1 ∣2 ∣3 ∣… … ∣ 9
北京交通大学 于双元
19
例: BNF: G[<标识符>] <标识符>→<字母>|<标识符><字母> |<标识符><数字> < >|<标 字>|< 数>) <标>→<字 字母>→a|b| …>(< |z|A| …|Z <字>→a|b|…|z|A|…|Z <数字>→0|1|2|…|9 <数>→0|1|2|…|9 ENBF:G[<标识符>] 标>=><标>(<字>|< 数 >) > |<数字>} << 标识符>→<字母 >{< 字母 =+><标>(<字>|<数>)…… (<字>|<数>) <字母>→a|b| … |z|A| … |Z (<字>|<数>) =><字>(<字 >|< 数>) …… < > =><字>{(<字 <标 数字>→0|1|2| …>|< |9 数>)}
§2.4 文法的化简与改造
§2.4.1 文法的实用限制 （无用符号和无用产生式的消除） §2.4.2 ε -产生式的消除 §2.4.3 单产生式的消除 §2.4.4 文法的其它表示方法
北京交通大学 于双元
1
§2.4 文法的化简与改造
§2.4.1文法的实用限制 1、不含无用产生式 G[S]: 设G=（Vn，Vt，P，S）是一文法，G中的符号 S →aA A →aA |d x∈Vn∪Vt是有用的，则x 必满足 ①存在α、β∈V*，有S=*> αxβ ②存在ω∈Vt* 使αxβ=*> ω 称符号x是有用的，否则是无用的。
0
0
S
1
1
0 S 1
0 1
3
北京交通大学 于双元
3. 无用符号和无用产生式的消除
算法2.1 算法2.2
满足②存在ω∈Vt* 使αxβ=*> ω 满足①存在α、β∈V*，有S=*> αxβ
x∈Vt∪Vn
算法2.1,文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等 价文法G1=(Vn①,Vt,P ①,S),对于每个X∈Vn① ,都有 w1∈Vt*,满足X=*>w1; 算法2.2,文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等 价文法G′=(Vn′,Vt′,P′,S),对于任一X∈V′,都存在α、 β∈(V′)* ,有S=*> αxβ; x∈Vt′∪Vn′ 消除步骤: 1.对文法G,执行算法2.1得到文法G1; 2.对文法G1,执行算法2.2得到文法G2,为所求.
(3)对P中的每一个产生式A→X1X2…Xm,若每个Xi都属 于Vt 或Vn①,则将A置于Vn①中; (4)重复步骤(3),直到Vn①不再增大为止; (5)对P中的每一个产生式B→Y1Y2…Yn,若B及每个Yi都 属于Vn①∪Vt,则将此产生式B→Y1Y2…Yn置于P①中.
北京交通大学 于双元 5
算法2.2,文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等 价文法G′=(Vn′,Vt′,P′,S),对于任一x∈V′,都存在α、 β∈(V′)* ,有S=*> αxβ; 步骤: (1)分别置Vn′、 Vt′和P′为Φ; (2)将文法的开始符号S置于Vn ′中;
无用产生式:产生式的左部或右部含有无用符号。
北京交通大学 于双元 2
G[S]: S →aA |Bb A →aA |d B →bB C →cC |d
2、不含有害规则
形如 U→ U 的规则 (原因①不必要②引起二义性) 例：G1[S]：S→0S1|01 G 1无二义性文法 G2[S]：S→0S1|01|S G2二义性文法 L（G1）=L(G2)={0n 1n|n>=1} G2文法句子0011 的两棵不同语法树. S S S
例G[S]:
Vn={S,W,U,V} Vt={a,b,c } P={S→aS︱W︱U, U→a,V→bV︱ac,
对G[S]执行算法2.1得到G1[S]:
Vn①={U,V,S} P①={S→aS︱U, U→a, Vt={a,b,c } G1[S]执行算法2.2得到G2[S] Vn′={S,U} V→bV︱ac }
北京交通大学 于双元 8
算法2.3
找出G中满足A=＊>ε的所有A,构成集合W
设G=(Vn,Vt ,P,S) ①作集合W1={A︱A→ε∈P} ②作集合序列Wk+1= Wk∪{B︱B→β∈P且β∈ Wk＋｝ 显然Wk≦ Wk+1（K>=1), 由于Vn有限， 故必存在某i,使得Wi=Wi+1=…., 令W=Wi,对每个A∈W, A=＊>ε 特别：当S∈W,则ε∈L(G);否则，ε不属于L(G).
{t}n {t}
m
t∈V*,
t∈V*,
符号串t自重复n到m次.
符号串t自重复0到无穷次.
北京交通大学 于双元 18
例:BNF: G[<无符号整数>]
(含左递归) <无符号整数>→<数字> ∣ <无符号整数> <数字> <数字> →0 ∣1 ∣2 ∣3 ∣… … ∣ 9
扩充的BNF: G[<无符号整数>]