在编译原理课程中,我们知道有4种文法:0型、1型、2型、3型。本文将对他们的区别进行描述。
0型文法
0型文法是“无限制文法”、“短语结构文法“,它对产生式几乎没有限制。对于任意的产生式$\alpha \Rightarrow \beta $, 0型文法要求,产生式左部的$\alpha$至少包含1个非终结符。
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型文法
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
欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~