一、文法的化简与改造
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
