编译原理：文法的分类

在编译原理课程中，我们知道有4种文法：0型、1型、2型、3型。本文将对他们的区别进行描述。

0型文法

0型文法是“无限制文法”、“短语结构文法“，它对产生式几乎没有限制。对于任意的产生式\alpha \Rightarrow \beta , 0型文法要求，产生式左部的\alpha至少包含1个非终结符。

1型文法

1型文法称为“上下文有关文法”（CSG）。它要求在产生式中，左侧的符号个数不能多于右部的符号的个数。即对于任意的产生式\alpha \Rightarrow \beta , 1型文法要求， | \alpha | \le | \beta | .

1型文法的产生式的一般形式为：

也就是说，对于非终结符A，只有当其上下文分别为\alpha_1和\alpha_2时，它才能推出\beta，因此它是上下文有关的。

并且，由于1型文法的定义可知，1型文法中不包含空产生式，也就是说，产生式右部不为空串。

简单证明：

假设1型文法包含空产生式。那么右部的符号个数为0.而由于\alpha中至少包含1个非终结符，因此产生式左侧符号个数至少为1。与定义的 | \alpha | \le | \beta | 相矛盾，因此1型文法不包含空产生式。

2型文法

2型文法称为“上下文无关文法”（CFG）。2型文法要求其产生式左部必须为非终结符。只要满足这个条件，产生式的左部就能替换成右部的符号。

2型文法的产生式的一般形式为：

3型文法

3型文法又称为“正则文法”（RG）。它分为左线性文法和右线性文法两种。它在2型文法的基础上，进一步对产生式的右部进行限制。

右线性文法： A \Rightarrow wB 或 A \Rightarrow w . 产生式的右侧，以终结符打头，并且终结符的右边，是非终结符或空串。

左线性文法： A \Rightarrow Bw 或 A \Rightarrow w .产生式的右侧，要么是一个终结符，要么终结符号的左侧有一个非终结符号串。

四种文法之间的关系

四种文法是逐级限制的关系：