编译原理：文法的分类

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

0型文法

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

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

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

$$ \alpha_1 A \alpha_2 \Rightarrow \alpha_1 \beta \alpha_2 \\ (\beta \ne \epsilon )$$

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

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

简单证明：

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

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

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

$$ A \Rightarrow \beta $$

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

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

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

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

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~