本文学习文法的分类。


Chomsky文法分类体系

根据对文法中产生式的不同要求,Chomsky文法分类体系将文法分为了四种类型,分别是

0型文法 (Type-0 Grammar)
1型文法 (Type-1 Grammar)
2型文法 (Type-2 Grammar)
3型文法 (Type-3 Grammar)

0型文法 (Type-0 Grammar)

先来看0型文法,0型文法就是前面定义的文法,这种文法对于产生式几乎没有限制,它只是要求产生式的左部α中至少包含一个非终结符,因此0型文法也称为是无限制文法或短语结构文法,由0型文法生成的语言称为是0型语言。

α → β
无限制文法(Unrestricted Grammar) /短语结构文法(Phrase Structure Grammar, PSG )
∀α → β∈P, α中至少包含1个非终结符
由0型文法G生成的语言L(G)

1型文法 (Type-1 Grammar)

接下来来看1型文法,1型文法也称为是上下文有关文法,它在0型文法的基础上,进一步要求产生式的左部α中符号的个数不能多于右部β中符号的个数。

这类文法之所以称为是上下文有关文法是因为在这类文法中产生式的一般形式为α12 → α1βα2 ( β≠ε ) , 也就是说,非终结符A只有当它的上下文分别是α1和α2的时候,它才可以替换为β,因此它是上下文有关的。

由1型文法的定义,我们可以看出上下文有关文法中不包含空产生式。所谓空产生式就是产生式的右部β是空串的产生式。如果上下文有关文法中包含空产生式,那么β的长度就是零。而我们要求α中至少包含一个非终结符。所以α的长度至少是1,那么α的长度大于等于1,而β的长度等于零。这就与上下文有关文法的定义不符合。所以上下文有关文法中不包含空产生式。

由上下文有关文法生成的语言叫做上下文有关语言。

α → β
上下文有关文法(Context-Sensitive Grammar , CSG )
∀α → β∈P,|α|≤|β|
产生式的一般形式: α12 → α1βα2 ( β≠ε )
上下文有关语言(1型语言)
由上下文有关文法 (1型文法) G生成的语言L(G )
CSG中不包含ε-产生式

2型文法 (Type-2 Grammar)

接下来我们来看2型文法。2型文法也称为上下文无关文法,简称CFG。

上下文无关文法要求每一个产生式的左部α必须是一个非终结符,也就说产生式的一般形式是A→β。

α → β
上下文无关文法 (Context-Free Grammar, CFG )
∀α → β∈P,α ∈ VN
产生式的一般形式:A→β

前面已经约定过大写字母A表示的是非终结符,这也就是说将A替换成β,不需要考虑它的上下文,因此称为上下文无关文法。

例如我们刚才举的用来生成标识符的文法,它的每一个产生式的左部都是一个非终结符,因此这个文法是一个上下文无关文法。

S → L | LT
T → L | D | TL | TD
L → a | b | c | d |…| z
D → 0 | 1 | 2 | 3 |…| 9

由上下文无关文法生成的语言称为是上下文无关语言。

3型文法 (Type-3 Grammar)

再来看一下3型文法。3型文法也叫正则文法,简称为RG。

α → β
正则文法 (Regular Grammar, RG )
右线性(Right Linear)文法: A→wB 或 A→w
左线性(Left Linear) 文法: A→Bw 或 A→w
左线性文法和右线性文法都称为正则文法

三型文法分为两种:一种是右线性文法,一种是左线性文法。

先来看右线性文法,右线性文法在二型文法的基础上,进一步对产生式的右部进行限制,也就是说在右线性文法中,每一个产生式,它的右部要么是一个终结符号串w,要么是在终结符号串w右面添加一个非终结符B。

相应的左线性文法要求产生式的右部要么是一个终结符号串w,要么是在终结符号串w的左边增加一个非终结符。

将这两种情况概括起来,也就是说在正则文法中产生式的右部最多只有一个非终结符,而且它们要把着同一侧。

我们来看一个右线性文法的例子。

① S → a | b | c | d
② S → aT | bT | cT | dT
③ T → a | b | c | d | 0 | 1 | 2 | 3 | 4 | 5
④ T → aT | bT | cT | dT | 0T | 1T | 2T | 3T | 4T | 5T

在这个文法中,每一个产生式的左部都是一个非终结符,所以首先它满足了上下文无关文法,也就是二型文法的要求。

接下来我们再来看各个产生式的右部,前面已经约定了小写字母a、b、c、d代表的是终结符,数字也是终结符, 因此在这个文法中,所有的产生式的右部要么是一个终结符号串,要么是在终结符号串的右边增加一个非终结符, 因此它是一个右线性文法。

再来看一下这个右线性文法生成的是什么语言呢?

根据第三个产生式T定义为a或b或c或d这里abcd代表全部字母,因此T可以表示一个字母,T又定义为0或1或2或3或4或5,这里0到5代表的是全部数字。因此T又可以表示一个数字。

接下来根据第四的产生式T定义为一个字母或者一个数字,后面加上一个T,后面的T又可以进一步替换成一个字母或者一个数字加上一个T,这个替换的过程可以一直循环下去,因此T生成的实际上是一个字母数字串。

再来看文法的开始符号能生成什么,文法的开始符号定义为一个字母或者一个字母加上一个字母数字串,概括起来也就是字母开头的字母数字串,这实际上还是标识符的构造方法。因此这个文法生成的语言也是标识符,它与我们前面介绍的用来生成标识符的上下文无关文法是等价的,事实上我们还可以写出与这个右线性文法等价的左线性文法。

由正则文法生成的语言称为是正则语言,事实上不仅标识符可以用正则文法来描述,程序设计语言中的大多数单词都可以用正则文法来描述,我们将在第三章词法分析中详细介绍。

四种文法之间的关系

最后我们来看一下四种文法之间的关系,根据四种文法的定义,我们可以看出这四种文法是逐级限制的关系。

在0型文法中,只要求产生式的左部α中至少包含一个非终结符;1型文法也就是上下文有关文法在0型文法的基础上,进一步要求产生式左部α中符号的个数不能多于产生式右部β中的符号的个数;2型文法也就是上下文无关文法,它要求产生式的左部必须是一个非终结符;3型文法也是正则文法在2型文法的基础上,进一步对产生式的右部进行限制,也就是要求产生式的右部满足一些要求。

由此可见,如果不考虑空产生式的因素,那么各种类型的文法集合之间是一个逐级包含的关系,也就是说0型文法集合包含1型文法集合,1型文法集合包含2型文法集合,2型文法集合包含3型文法集合,如果一个文法是2型文法,那么它一定是1型文法,但是反过来却不成立;一个3型文法肯定是一个2型方法,进而也肯定是一个1型文法,但是反过来却不成立。

0型文法:α中至少包含1个非终结符
1型文法(CSG) :|α|≤|β|
2型文法(CFG) :α ∈ VN
3型文法(RG):A→wB 或 A→w (A→Bw 或A→w)

最后修改日期:2020年5月14日

留言

撰写回覆或留言