编译原理之四：文法类型

　　本篇讲述文法的类型，某些类型的文法及其产生的语言得到了细致的研究并被伟大的乔姆斯基单独命名。乔姆斯基先生能众多规则中进行进一步归纳，对产生式施加不同的限制。而我们只能学习人家乔姆斯基先生研究好的东东，学习这种思考问题的方式。

 

　　四种文法之间的关系是将产生式作进一步的限制而定义的：

 

 

文法类型	规则	示例
0型文法	a->b 产生式左边a至少含有一个非终结符	nA->b
1型文法	在0型基础上，a->b 产生式右侧的长度越来越长。|b| >=|a| S->ε 除外。	nA->bSd
2型文法	在1型基础上，a->b左侧为一个非终结符。	A->bSd
3型文法	在2型基础上，a->b 右侧的形式为：A->cB 或A->c （仅此两种形式）AB为非终结符	A->bS A-n

 

　　从0型文法到3型文法，规则越来越严格了。

 

　　0型文法：可由图灵机识别（关于图灵机，百度百科描述很详细了。）

 

　　1型文法：上下文有关文法。（任何产生规则的左手端和右手端都可以被终结符和非终结符的上下文所围绕，乔姆斯基描述自然语言的一种方式介入的，在自然语言中一个单词是否可以出现在特定的位置要依赖于上下文。）

 

　　2型文法：上下文无关文法。之所以称为上下文无关文法，是因为在推导式中a->b ，字符a总可以被字符串b自由替换，而无需考虑字符a出现的上下文。

 

　　3型文法：正规语言，之所人称作正规语言（正则语言），可能是因为3型文法只有两种形式 A->aB A->a ，比较固定，规则明显，所以称为正规语言。（小菜这么想的）

作者：永远的晴天

出处：http://blog.csdn.net/lovesummerforever