【编译原理】-- 第二章（三）（文法的化简改造、无用产生式、产生式的消除、文法的其他表示方法、例题）

目录

一、文法的化简与改造

1、文法的实用限制

（1）不含无用产生式

（2）不含有害规则

（3）无用符号和无用产生式的消除

 2、产生式的消除

算法3：     

算法4：ε不属于L(G)

算法5：ε属于L(G)

3、单产生式的消除

算法6：

 4、文法的其他表示方法

（1）{ }

 （2）[ ]

 （3）（ ）

 5、文法和语言的Chomsky分类

（1）0型文法

（2）1型文法

（3）2型文法

（4）3型文法

二、例题

1、G[Z]:Z→(+|-)AB

             A→0|1|2|......|9|AA             B→2|4|6|8         描述的语言特征

2、消除文法的ε产生式，G[S]：S→aBS|b B→cS|ε

3、将文法G[S]改写为等价的正则文法G[S]：S→dABA→aA|aB→Bb| ε

---

一、文法的化简与改造

1、文法的实用限制

不含无用产生式、不含有害规则。

（1）不含无用产生式

无用产生式:产生式的左部或右部含有无用符号。

设G=（Vn，Vt，P，S）是一文法，G中的符号x∈Vn∪Vt是有用的，则x 必满足
①存在α、β∈V*，有S=*>αxβ
②存在ω∈Vt* 使αxβ=*> ω
称符号x是有用的，否则x是无用的。

（2）不含有害规则

形如 U→ U 的规则 (原因①不必要②引起二义性)

（3）无用符号和无用产生式的消除

算法1：         满足②存在ω∈Vt* 使αxβ=*> ω

文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等价 文 法 G1=(Vn①,Vt,P①,S), 对 于 每 个 X∈Vn① , 都 有w1∈Vt*,满足X=*>w1。

算法2：         满足①存在α、β∈V*，有S=*> αxβ

文法G=(Vn,Vt,P,S)(假定L(G)≠Φ),得到等价文法G′=(Vn′,Vt′,P′,S),对于任一x∈V′,都存在α、β∈V′* ,有S=*> αxβ。

消除步骤：

1、对文法G,执行算法1得到文法G1；

2、对文法G1,执行算法2得到文法G′,为所求。

例：

G[S]:
Vn={S,W,U,V}
Vt={a,b,c }
P={

S→aS︱W︱U,
U→a,

V→bV︱ac,
W→aW

}

消除无用产生式：

G[S]:
Vn={S,U}
Vt={a}
P={S→aS︱U,U→a}

对G[S]执行算法2.1得到G1[S]:
Vn①={U,V,S}
Vt={a,b,c }
P①={S→aS︱U,
U→a, V→bV︱ac }

G1[S]执行算法2.2得到G2[S]
Vn′={S,U}
Vt′={a}
P′={S→aS︱U,U→a}

 2、产生式的消除

• 如某L(G)中不含ε,可消除G中的全部ε产生式;
• 如某L(G)中含ε,肯定不能消除G中的全部ε产生式;

算法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).

算法4：ε不属于L(G)

设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
(i)若Xi不属于W,即Xi属于（Vn－W）∪Vt,则取Yi=Xi ;
(ii)若Xi属于W,则Yi分别取为Xi和ε,即如果X1X2...Xm中有j个
符号属于W，则将有２j个形如Y→Y1Y2...Ym的产生式放入P′中，
但若所有的Xi均属于W,却不能把所有的Yi都取ε 。

例:

G[S]:

S→aA
A→BC
B→bB︱ε
C→cC︱ε
消除ε产生式

执行算法3
W={A,B,C}，S不属于W

执行算法4
G[S]:S→aA︱a
A→BC︱B︱C
B→bB︱b
C→cC︱c
为消除ε产生式后文法

算法5：ε属于L(G)

设G=(Vn,Vt, P, S), 且ε属于L(G)，则按下述算法构造G1=(Vn①,Vt,P①,S①), 使L(G1)=L(G),且除S ① → ε外, P ①不含另外ε产生式．此外, S ①不出现在任何产生式的右部。

情况一：S不出现在原文法任何产生式的右部

设G=(Vn,Vt,P, S), 且ε属于L(G)，S属于W,
执行算法2.4得 G′=(Vn,Vt,P′,S), 但ε属于L（G′）
设G=(Vn,Vt, P, S), 且ε属于L(G)，则按下述算法
构造G1=(Vn①,Vt,P①,S①), 使L(G1)=L(G),且除S ① → ε外, P ①
不含另外ε产生式．此外, S ①不出现在任何产生式的右部.
令P①=P′∪{S→ε}, Vn① = Vn, S① = S
则G1=(Vn①,Vt, P①, S①)为所求。

例:   S未出现在右部

G[S]:
S→cA︱AB
A→aAb︱ε
B→Bb︱ε

执行算法3得
W={B,A,S}

执行算法4得
消去ε产生式：
G′=(Vn, Vt, P′, S),
G＇[S]:
S→cA︱AB︱c︱A︱B
A→aAb︱ab
B→Bb︱b

执行算法5，情况1：
再加入S→ε，
得G1[S ]:
S →ε
S→cA︱AB︱c︱A︱B
A→aAb︱ab
B→Bb︱b 为所求

情况二：S出现在原文法产生式的右部

设G=(Vn,Vt,P,S), 且ε属于L(G)，S属于W,按下述算法先构造G′=(Vn①,Vt,P′，S①),再构造G1=(Vn①,Vt,P① ,S①), 使L(G1)=L(G)。

①引入新符号S①（S① 不属于V），作为G′的开始符号，并令Vn①＝Vn ∪｛ S① ｝；
②作产生式集P′=P∪{S①→α︱S→α∈P }得到G′（以下实际上是按算法2.5情况1处理）
③对文法G′=(Vn①,Vt,P′,S①),执行算法2.4消去P′中的全部ε产生式，并将S①→ε加入得到P① 得到文法G1=(Vn①,Vt,P① ,S①), L(G1)=L(G);

例：

G[S]:
S→cS︱AB
A→aAb︱ε
B→Bb︱ε

执行算法5，情况2：

引入S① ，做P’，得G＇
G＇[S①]:
S① →cS︱AB
S→cS︱AB
A→aAb︱ε
B→Bb︱ε

执行算法4得
W={B,A,S, S①},
再消除ε产生式，
再加入S① →ε 得G1

G1[S① ]:
S①→cS︱AB︱c︱A︱B︱ε
S→ cS︱AB︱c︱A︱B
A→aAb︱ab
B→Bb︱b
为所求

3、单产生式的消除

设G=(Vn,Vt , P, S)是一文法,假定G中不含ε-产生式,执行算法6得到不含单产生式的文法G′。

算法6：

(1)设Vn={A1,A2,..,An},对每个Ai(1≦i≦n),作集合序列 W1(Ai)={Ai}

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}

W(i)={B︱Ai*=>B,B∈Vn}

(2)构造产生式集合
P′=∪{ Ai →α︱ B →α∈P,B∈W(i), α不属于Vn}
此时, P′中已不含任何单产生式.

例：

G[S]:
Vn={S,A,B}
Vt={a,b}
P={

S→AB︱A︱B,
A→ab︱aAb
B→Bb︱b

}

对G[S]执行算法6得到G1[S]:
W(S)={S,A,B}
W(A)={A}
W(B)={B}

P′={S→AB︱aAb︱ab︱Bb︱b}
∪{A→aAb︱ab}
∪{B→Bb︱b}
为所求, G1[S]与G[S]等价.

 4、文法的其他表示方法

（1）{ }

 （2）[ ]

 （3）（ ）

规则中提取公因子

 5、文法和语言的Chomsky分类

文法是一个四元组G=（Vn，Vt，P，Z），乔姆斯基根据文法中P的不同，将文法分为四类,每一种文法对应一种语言。

（1）0型文法

文法G中规则呈α→β α∈V+，β∈V*，也称短语结构文法（PSG）,对应图灵机确定的语言为0型语言L0

（2）1型文法

文法G中规则呈α1Aα2→α1βα2 α1，α2∈V*，A∈Vn，β∈V+，也称上下文有关文法(CSG).对应线性界限自动机确定的语言为1型语言L1,也称上下文有关语言。

（3）2型文法

文法G中规则呈A→β A∈Vn，β∈V+ (或V*)，也称上下文无关文法(CFG).对应下推自动机识别,确定的语言为2型语言L2或上下文无关语言，2型文法在语法分析中用于描述语法类。

（4）3型文法

文法G中规则呈：

• A→aB或A→a A、Ｂ∈Vn,a∈Vt,称G为右线形正则文法.
• A→Ba或A→a A、Ｂ∈Vn,a∈Vt,称G为左线形正则文法

确定的语言为3型语言L3或正则语言，有限自动机识别，3型文法在词法分析中用于描述单词符号。

二、例题

1、G[Z]:Z→(+|-)AB

             A→0|1|2|......|9|AA
             B→2|4|6|8         描述的语言特征

句子是不能被5整除的偶整数（不以0结尾可以0开头）

2、消除文法的ε产生式，G[S]：S→aBS|b B→cS|ε

解：G[S]:
S→aBS|aS|b
B→cS

3、将文法G[S]改写为等价的正则文法
G[S]：S→dAB
A→aA|a
B→Bb| ε

解：设S′→AB
则 S→dS′

A带入S ′ 则
S′→aAB|aB
S′→aS′|aB

G[S]:
S→dS′
S′→aS′|aB
A→aA|a
B→bB| ε

消去无用产生式和ε产生式：

G[S]:
S→dS′
S′→aS′|aB|a
B→bB| b

---