编译原理：文法分类-编译原理与实践

形式语言理论是乔姆斯基（Chomsky）于1956年首先建立起来的，它对计算机科学，尤其是程序语言的设计、编译方法和计算复杂性等方面，有着深远的影响。乔姆斯基文法一般分为四类，即0型、1型、2型和3型文法，其差别在于对产生式施加了不同的限制。

假设文法G=（VT，VN，S，P），α、β∈（VT∪VN）*，下面分别对各类文法进行简单介绍。

0型文法：也称为短语文法，指的是P中每个产生式α→β的左部α中至少含有一个非终结符的文法。0型文法描述的语言称为0型语言，它是一种递归可枚举语言；反之，递归可枚举集必定是0型语言，并且可由图灵机（Turing）进行识别。

1型文法：也称为上下文有关文法，是指在0型文法的基础上，若P中每个产生式α→β还满足|α|≤|β|（S→ε除外）的文法。该文法意味着，对非终结符进行替换时必须考虑上下文环境，而且一般不允许替换成空串ε。例如，假设α1 Aα2→α1γα2是该文法的一个产生式，其中α1、α2、γ∈（VT∪VN）*，γ≠ε，A∈VN，则只有A出现在α1和α2的上下文中时，才允许用γ替换A。1型文法描述的语言称为1型语言或上下文有关语言，这种语言可由线性界限自动机来识别。

2型文法：也称为上下文无关文法，是指P中每个产生式形如A→β的文法，其中A∈VN，β∈（VT∪VN）*。该文法意味着，对非终结符进行替换时不必考虑上下文。2型文法主要用来描述高级程序设计语言的语法结构，它所描述的语言称为2型语言或上下文无关语言，这种语言可由下推自动机来识别。(www.xing528.com)

3型文法：也称为正规文法，是指P中每个产生式形如A→αB或A→α的文法，其中A、B∈VN，α∈VT*。这种形式的3型文法也称为右线性文法。若P中每个产生式形如A→Bα或A→α，则称这种形式的3型文法为左线性文法。3型文法主要用来描述单词的构成，它所描述的语言称为3型语言或正规语言，这种语言可由有限自动机来识别。

上述四类文法是对产生式形式逐渐增加限制得到的，因此，它们之间形成了一种层层包含的关系，即：0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法。由此可以看出，3型文法的描述能力最弱，只能用来描述单词的构成；2型文法的描述能力比3型文法的描述能力要强，可以描述现今大多数程序设计语言的语法结构；1型文法的描述能力则比2型文法的描述能力更强；0型文法的描述能力最强。

总之，形式语言中还有许多非常有趣的内容，由于和编译技术没有直接关系，此处不再赘述。