编译原理：文法的分类

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

0型文法

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

1型文法

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

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

$$\begin{gathered} {\alpha }_{1}A{\alpha }_2\Rightarrow {\alpha }_1\beta {\alpha }_2 \\ (\beta \ne ϵ) \end{gathered}$$

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

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

简单证明：

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

2型文法

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

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

$$A\Rightarrow \beta$$

3型文法

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

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

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

四种文法之间的关系

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

转载请注明来源：https://longjin666.cn/?p=1685

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