1
2.4 文法的化简与改造
? 对文法进行化简和改造
– 希望定义语言的文法尽可能简单
– 某些语法分析技术对文法有要求和限制,LL分析
要求文法无左递归；算符优先分析要求文法不含
有 ?-产生式； LR分析要求文法无二义性
? 本节主要内容
– 无用符号和无用产生式的删除
– ?-产生式的消除
– 单产生式的消除
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是 无用的 。
若一产生式含有无用符号，则此产生式称为 无用产生式 。
? 无用产生式给语法分析带来了许多麻烦，应予以
删除 。
3
无用符号和无用产生式的识别
? 找出文法 G中的全部无用符号，删除这些无用
符号以及包含它们的所有产生式。
? 识别文法 G中的无用符号：对于任一符号 X，
如果 X是有用的，则
– X至少出现在一个句型中（条件 2.12），否则，用
算法 2.2进行改造
– 符号 X能推导出终结符号串（条件 2.13），否则，
用 算法 2.1进行改造
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?
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中,
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
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}
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
9
已化简文法
? 注意,在删除无用符和无用产生式时,应先执行
算法 2.1再执行算法 2.2,就可得到, 干净,
（删除了全部无用符号和无用产生式）的文法 ;
若先执行算法 2.2,再执行算法 2.1所得文法不
一定, 干净, 。
? 已化简文法, 不含 无用符号、无用产生式以及形
如 A?A的产生式的文法 。
10
2.4.2 ?-产生式的消除
? ?-产生式 是指右部为一空符号串 ?的产生式。因
为某些语法分析算法要求不含 ?-产生式,因此
应消除。
? 若一语言不含 ?（即 ??L(G)),则可全部消除文法
中的 ?-产生式 ；否则 文法中的 ?-产生式 不能全
部 消除。
? 可对 ??L(G)的文法进行改造
– 开始符 S可推导出 ?(即 S?? ?P)，此外再无其它 ?-产
生式 。
– S不出现在任何产生式的右部
11
判断语言中是否包含 ?
? 找出所有可推导出 ?的非终结符,
W={A| A?* ?,A?VN}
? 检验 S?W是否成立，可知 ??L(G)是否成立。
? 算法 2.3 设 G = (VN,VT,P,S)为任一 文法,
– 作集合 W1={A| A?? ? P}
– 作集合序列
– 当集合 序列 不再增大时，算法结束，令 W=Wk+1
– 显然对于 W中的每一个符号 A,有 A?* ?
1k}WβP,βB|B{WW kk1k ?????? ??
12
消除 ??L(G)情况时的 ?-产生式
? 算法 2.4,设 G = (VN,VT,P,S) 为一文法，且
??L(G),构造 其等价文法 G’=(VN,VT,P’,S),使得
L(G)=L(G’)，并且 G’中不含 ?-产生式 。
– 计算 W
– 对 P中的任一非 ? 产生式 A?X1X2…X m进行如下改写,
? 如果 Xi?W，则 Xi保持不变；
? 如果 Xi ?W，则该位置可以取 Xi和 ?两种取值情况；
? 将 Xi的每一种取值组合写成一条产生式；但若所有 Xi
都属于 W，则 X1X2…X m不能改写为 ?。
– 改写后的产生式放入到 P’中。
13
算法 2.4示例
? 设有文法 G=({S,A,B,C},{a,b,c},P,S),其中,P,
S?aA; A?BC; B?bB|?; C?cC|?
? 执行算法 2.3得到,W={A,B,C},继续执行算法
2.4得到产生式集合 P’,
S?aA,S?aA和 S?a
A?BC,A?BC,A?B和 A?C
B?bB,B?bB和 B?b
C?cC,C?cC和 C?c
14
消除 ??L(G)情况时的 ?-产生式
? 设 G = (VN,VT,P,S) 为一文法，且 ?? L(G),构造 文法
G’=(V’N,VT,P’,S’),使得 L(G)=L(G’)，并且除产生式
S’??外,P’中 再无其它 ?-产生式,S也不出现在任何产
生式的右部。
? 算法 2.5,如果 S不出现在任何产生式的右部，则直接
执行算法 2.4，消除所有的 ?-产生式，并补充产生式
S??，得到产生式集合 P’，并且 V’N =VN； S’= S；
15
消除 ??L(G)情况时的 ?-产生式（续）
? 否则 存在关于 S的递归
（ 1）引入新的符号 S’ ? VN ?VT 作为 G’的开始符号，令
V’N =VN?{S’}；
（ 2）作产生式集 P1=P ?{S’?? | S?? ? P} （ 3）
对文法 G’=(V’N,VT,P1,S’)执行算法 2.4，消除 P1中所有
的 ?-产生式。
（ 4）将 S’??添加到所得的产生式集合中，得到最后的
产生式集合 P’。
16
算法 2.5举例
? 设有文法 G=({S,A,B},{a,b,c},P,S),其中,P,
S?cS|AB; A?aAb|?; B?Bb|? W={S,A,B}
(1)引入新的符号 S’,V’N =VN?{S’}={S,A,B,S’}
(2) 作产生式集 P1=P ?{S’? cS,S’?AB}
(3) 再计算新的 W,W={S,A,B,S’}
(4) 改写非 ? 产生式,
– S?cS|AB,S?cS|c|AB|A|B
– A?aAb,A?aAb|ab
– B?Bb,B?Bb|b
– S’? cS|AB,S’?cS|c|AB|A|B
(5) 补充产生式 S’??
17
单产生式的消除
? 单产生式：右部仅有一个非终结符的产生式，如 A?B。
? 设 G = (VN,VT,P,S) 为一文法，且 G中不含 ?-产生式,构造
其等价 文法 G’,G’中不含任何单产生式。
? 算法 2.6
（ 1）对于 VN中的每一非终结符 Ai,构造集合
从 Ai推导出的单个非终结符的集合
（ 2）构造产生式集
左部为 Ai,右部为 Ai可以推导出的单个非终结符所对应
产生式的右部，但该右部不能是单个非终结符。
?
n
1i
N
( i )
i }Vα,WBP,αB|α{AP'
?
??????
}VBB,*A|{BW Ni( i ) ???
18
算法 2.6示例
? 设有文法 G=({S,A,B},{a,b},P,S),其中,P,
S?AB; S?A; S?B; A?aAb; A?ab;
B?Bb; B?b
(1) 构造集合 W(S)={S,A,B}; W(A)={A}; W(B)={B}
(2) 构造产生式集合
P’={S?AB,S?aAb,S?ab,S?Bb,S?b} ?
{A?aAb,A?ab} ?
{B?Bb; B?b}
可以验证，利用引理 2.1会得到相同的结果。
19
2.5 文法和语言的 Chomsky分类
? 文法的四元组表示是由 N.Chomsky于 1956年描述形
式语言时给出的。他还定义了 四类基本文法（ 0型文法、
1型文法,2型文法和 3型文法） 。
? 0型文法,
– 若 P中任一产生式都有一般形式 ???,其中 ??V+,
??V* 且对 ?,? 不加任何限制，则称 G为 0型文法
（ 短语结构文法,PSG)。
? 由 0型文法生成（或定义）的语言称为 0型语言 （ 递归
可枚举语言 ）。它可由 图灵 （ Turing） 机 识别。
20
0型语言举例
? 例如,S?ACaB Ca?aaC CB?DB CB?E
aD?Da AD?AC aE?Ea AE?? 就是一个 0型文
法,它所产生的语言为
},,,{}|{ 20 ?a a a a a a a aa a a aaaIiaL i ??? ?
对于程序设计语言来,0型文法 有很大的随意性,还须
加以限制。
21
1型文法和语言
? 若一 0型文法所有产生式具有形式 ?1A?2? ?1??2其中,
?1,?2 ?V*,??V+, A?VN,则称 G 为 1型 (前后文有关 )
文法,记为 CSG ( Context Sensitive Grammar) 。
? 命名的由来,只有当非终结符 A的前后分别为 ?1,?2时，
才能将 A替换为 ?。
? 1型文法 产生的语言称为 前后文有关语言 （ CSL）,它
可由 线性限界自动机 识别。
? 1 型文法还有另一种定义形式,G的每个产生式形为
???且满足, | ? |? | ? | ?,? ?V+
则 G是 1型文法
22
两种定义的等价性
? 任一种形式定义的文法所产生的语言都可由另一种形式定
义的文法产生。
? 根据定义，含有 ?产生式的文法不是 1型文法。由于实际需
要，也可以将 ?-产生式作为 1型文法的特例而接受之。
? 例 文法 G,S?? | A A?aABC A?abC CB?BC
bB?bb bC?bc cC?cc
? 因 G含有 ?-产生式,所以它不是一个严格意义下的 1型文法。
它所产生的语言为
? 删除 G中的 ?-产生式可以得到一个 1型文法，产生的语言为
}0|{)( ?? icbaGL iii
}1|{)'( ?? icbaGL iii
23
2型文法和语言
? 若一 1型文法 G中所有产生式具有形式,
A?? A?VN, ??V+
则称 G为 2型 (前后文无关 )文法,记为 CFG。
? 2型文法产生的语言称为 前后文无关语言 CFL，它可由
非确定下推自动机 识别。
? 若允许 ?-产生式存在，则 CFG产生式形式为
A?? A?VN, ??V*
? 例, G[S]=({S},{a,b},{S?aSb,S?ab},S)是一个前后文
无关文法，它产生的语言为
}1|{)( ?? ibaGL ii
24
3型文法和语言
? 若一 2型文法 G中仅含有形如 A?aB 或 A?a 的产生式，
其中 A,B ?VN,a ?VT 则称 G为 右线性文法； 若 G中仅
含有形如 A?Ba 或 A?a的产生式，则称 G为 左线性文
法 。
? 左线性文法 和 右线性文法 都称为 3型文法 （ 正规文法 ）
? 3型文法 产生的语言称为 3型（ 正规 ）语言,它可由 有
限自动机 识别。 正规语言 可用 正规表达式 表示。
? 3型文法 还可拓广定义为 A??B A?? （ ? ?VT +）,
可以证明，该定义与上面的定义是等价的。
25
四类语言之间的关系
由各类文法的定义可知,3型语言一定是 2型语言,2型语言一
定是 1型语言，也一定是 0型语言，反之不成立。
若把各类语言视为语言族 Lk,k=0,1,2,3，则它们之间有真
包含关系,
0123 LLLL ???
文法类型 文法名称 语言名称 自动机名称
0 短语结构 ~ 递归可枚举 图灵机
1 前后文有关 ~ 前后文有关 线性限界
2 前后文无关 ~ 前后文无关 下推自动机
3 正规 ~ 正规语言 有限自动机
2.4 文法的化简与改造
? 对文法进行化简和改造
– 希望定义语言的文法尽可能简单
– 某些语法分析技术对文法有要求和限制,LL分析
要求文法无左递归；算符优先分析要求文法不含
有 ?-产生式； LR分析要求文法无二义性
? 本节主要内容
– 无用符号和无用产生式的删除
– ?-产生式的消除
– 单产生式的消除
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是 无用的 。
若一产生式含有无用符号，则此产生式称为 无用产生式 。
? 无用产生式给语法分析带来了许多麻烦，应予以
删除 。
3
无用符号和无用产生式的识别
? 找出文法 G中的全部无用符号，删除这些无用
符号以及包含它们的所有产生式。
? 识别文法 G中的无用符号：对于任一符号 X，
如果 X是有用的，则
– X至少出现在一个句型中（条件 2.12），否则，用
算法 2.2进行改造
– 符号 X能推导出终结符号串（条件 2.13），否则，
用 算法 2.1进行改造
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?
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中,
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
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}
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
9
已化简文法
? 注意,在删除无用符和无用产生式时,应先执行
算法 2.1再执行算法 2.2,就可得到, 干净,
（删除了全部无用符号和无用产生式）的文法 ;
若先执行算法 2.2,再执行算法 2.1所得文法不
一定, 干净, 。
? 已化简文法, 不含 无用符号、无用产生式以及形
如 A?A的产生式的文法 。
10
2.4.2 ?-产生式的消除
? ?-产生式 是指右部为一空符号串 ?的产生式。因
为某些语法分析算法要求不含 ?-产生式,因此
应消除。
? 若一语言不含 ?（即 ??L(G)),则可全部消除文法
中的 ?-产生式 ；否则 文法中的 ?-产生式 不能全
部 消除。
? 可对 ??L(G)的文法进行改造
– 开始符 S可推导出 ?(即 S?? ?P)，此外再无其它 ?-产
生式 。
– S不出现在任何产生式的右部
11
判断语言中是否包含 ?
? 找出所有可推导出 ?的非终结符,
W={A| A?* ?,A?VN}
? 检验 S?W是否成立，可知 ??L(G)是否成立。
? 算法 2.3 设 G = (VN,VT,P,S)为任一 文法,
– 作集合 W1={A| A?? ? P}
– 作集合序列
– 当集合 序列 不再增大时，算法结束，令 W=Wk+1
– 显然对于 W中的每一个符号 A,有 A?* ?
1k}WβP,βB|B{WW kk1k ?????? ??
12
消除 ??L(G)情况时的 ?-产生式
? 算法 2.4,设 G = (VN,VT,P,S) 为一文法，且
??L(G),构造 其等价文法 G’=(VN,VT,P’,S),使得
L(G)=L(G’)，并且 G’中不含 ?-产生式 。
– 计算 W
– 对 P中的任一非 ? 产生式 A?X1X2…X m进行如下改写,
? 如果 Xi?W，则 Xi保持不变；
? 如果 Xi ?W，则该位置可以取 Xi和 ?两种取值情况；
? 将 Xi的每一种取值组合写成一条产生式；但若所有 Xi
都属于 W，则 X1X2…X m不能改写为 ?。
– 改写后的产生式放入到 P’中。
13
算法 2.4示例
? 设有文法 G=({S,A,B,C},{a,b,c},P,S),其中,P,
S?aA; A?BC; B?bB|?; C?cC|?
? 执行算法 2.3得到,W={A,B,C},继续执行算法
2.4得到产生式集合 P’,
S?aA,S?aA和 S?a
A?BC,A?BC,A?B和 A?C
B?bB,B?bB和 B?b
C?cC,C?cC和 C?c
14
消除 ??L(G)情况时的 ?-产生式
? 设 G = (VN,VT,P,S) 为一文法，且 ?? L(G),构造 文法
G’=(V’N,VT,P’,S’),使得 L(G)=L(G’)，并且除产生式
S’??外,P’中 再无其它 ?-产生式,S也不出现在任何产
生式的右部。
? 算法 2.5,如果 S不出现在任何产生式的右部，则直接
执行算法 2.4，消除所有的 ?-产生式，并补充产生式
S??，得到产生式集合 P’，并且 V’N =VN； S’= S；
15
消除 ??L(G)情况时的 ?-产生式（续）
? 否则 存在关于 S的递归
（ 1）引入新的符号 S’ ? VN ?VT 作为 G’的开始符号，令
V’N =VN?{S’}；
（ 2）作产生式集 P1=P ?{S’?? | S?? ? P} （ 3）
对文法 G’=(V’N,VT,P1,S’)执行算法 2.4，消除 P1中所有
的 ?-产生式。
（ 4）将 S’??添加到所得的产生式集合中，得到最后的
产生式集合 P’。
16
算法 2.5举例
? 设有文法 G=({S,A,B},{a,b,c},P,S),其中,P,
S?cS|AB; A?aAb|?; B?Bb|? W={S,A,B}
(1)引入新的符号 S’,V’N =VN?{S’}={S,A,B,S’}
(2) 作产生式集 P1=P ?{S’? cS,S’?AB}
(3) 再计算新的 W,W={S,A,B,S’}
(4) 改写非 ? 产生式,
– S?cS|AB,S?cS|c|AB|A|B
– A?aAb,A?aAb|ab
– B?Bb,B?Bb|b
– S’? cS|AB,S’?cS|c|AB|A|B
(5) 补充产生式 S’??
17
单产生式的消除
? 单产生式：右部仅有一个非终结符的产生式，如 A?B。
? 设 G = (VN,VT,P,S) 为一文法，且 G中不含 ?-产生式,构造
其等价 文法 G’,G’中不含任何单产生式。
? 算法 2.6
（ 1）对于 VN中的每一非终结符 Ai,构造集合
从 Ai推导出的单个非终结符的集合
（ 2）构造产生式集
左部为 Ai,右部为 Ai可以推导出的单个非终结符所对应
产生式的右部，但该右部不能是单个非终结符。
?
n
1i
N
( i )
i }Vα,WBP,αB|α{AP'
?
??????
}VBB,*A|{BW Ni( i ) ???
18
算法 2.6示例
? 设有文法 G=({S,A,B},{a,b},P,S),其中,P,
S?AB; S?A; S?B; A?aAb; A?ab;
B?Bb; B?b
(1) 构造集合 W(S)={S,A,B}; W(A)={A}; W(B)={B}
(2) 构造产生式集合
P’={S?AB,S?aAb,S?ab,S?Bb,S?b} ?
{A?aAb,A?ab} ?
{B?Bb; B?b}
可以验证，利用引理 2.1会得到相同的结果。
19
2.5 文法和语言的 Chomsky分类
? 文法的四元组表示是由 N.Chomsky于 1956年描述形
式语言时给出的。他还定义了 四类基本文法（ 0型文法、
1型文法,2型文法和 3型文法） 。
? 0型文法,
– 若 P中任一产生式都有一般形式 ???,其中 ??V+,
??V* 且对 ?,? 不加任何限制，则称 G为 0型文法
（ 短语结构文法,PSG)。
? 由 0型文法生成（或定义）的语言称为 0型语言 （ 递归
可枚举语言 ）。它可由 图灵 （ Turing） 机 识别。
20
0型语言举例
? 例如,S?ACaB Ca?aaC CB?DB CB?E
aD?Da AD?AC aE?Ea AE?? 就是一个 0型文
法,它所产生的语言为
},,,{}|{ 20 ?a a a a a a a aa a a aaaIiaL i ??? ?
对于程序设计语言来,0型文法 有很大的随意性,还须
加以限制。
21
1型文法和语言
? 若一 0型文法所有产生式具有形式 ?1A?2? ?1??2其中,
?1,?2 ?V*,??V+, A?VN,则称 G 为 1型 (前后文有关 )
文法,记为 CSG ( Context Sensitive Grammar) 。
? 命名的由来,只有当非终结符 A的前后分别为 ?1,?2时，
才能将 A替换为 ?。
? 1型文法 产生的语言称为 前后文有关语言 （ CSL）,它
可由 线性限界自动机 识别。
? 1 型文法还有另一种定义形式,G的每个产生式形为
???且满足, | ? |? | ? | ?,? ?V+
则 G是 1型文法
22
两种定义的等价性
? 任一种形式定义的文法所产生的语言都可由另一种形式定
义的文法产生。
? 根据定义，含有 ?产生式的文法不是 1型文法。由于实际需
要，也可以将 ?-产生式作为 1型文法的特例而接受之。
? 例 文法 G,S?? | A A?aABC A?abC CB?BC
bB?bb bC?bc cC?cc
? 因 G含有 ?-产生式,所以它不是一个严格意义下的 1型文法。
它所产生的语言为
? 删除 G中的 ?-产生式可以得到一个 1型文法，产生的语言为
}0|{)( ?? icbaGL iii
}1|{)'( ?? icbaGL iii
23
2型文法和语言
? 若一 1型文法 G中所有产生式具有形式,
A?? A?VN, ??V+
则称 G为 2型 (前后文无关 )文法,记为 CFG。
? 2型文法产生的语言称为 前后文无关语言 CFL，它可由
非确定下推自动机 识别。
? 若允许 ?-产生式存在，则 CFG产生式形式为
A?? A?VN, ??V*
? 例, G[S]=({S},{a,b},{S?aSb,S?ab},S)是一个前后文
无关文法，它产生的语言为
}1|{)( ?? ibaGL ii
24
3型文法和语言
? 若一 2型文法 G中仅含有形如 A?aB 或 A?a 的产生式，
其中 A,B ?VN,a ?VT 则称 G为 右线性文法； 若 G中仅
含有形如 A?Ba 或 A?a的产生式，则称 G为 左线性文
法 。
? 左线性文法 和 右线性文法 都称为 3型文法 （ 正规文法 ）
? 3型文法 产生的语言称为 3型（ 正规 ）语言,它可由 有
限自动机 识别。 正规语言 可用 正规表达式 表示。
? 3型文法 还可拓广定义为 A??B A?? （ ? ?VT +）,
可以证明，该定义与上面的定义是等价的。
25
四类语言之间的关系
由各类文法的定义可知,3型语言一定是 2型语言,2型语言一
定是 1型语言，也一定是 0型语言，反之不成立。
若把各类语言视为语言族 Lk,k=0,1,2,3，则它们之间有真
包含关系,
0123 LLLL ???
文法类型 文法名称 语言名称 自动机名称
0 短语结构 ~ 递归可枚举 图灵机
1 前后文有关 ~ 前后文有关 线性限界
2 前后文无关 ~ 前后文无关 下推自动机
3 正规 ~ 正规语言 有限自动机
