文法分类

首先先简单的介绍下两个概念

语言是由文法描述的,文法使用有限的规则将无限的语言描述出来

语言的形式化定义：由文法 G 的开始符号 S 推导出的所有句子构成的集合称为文法 G 生成的语言，记作 L(G)

接下来讲下文法的分类

文法分为0型文法、1型文法、2型文法、3型文法

0型文法只需要对α有要求 至少包含1个非终结符

1型文法在0型文法的基础上进一步的要求产生式的左部α中符号的个数不能多于β中符号的个数

非终结符A，当它的上下文分别是α1和α2的时候才可以替换为β，因此是上下文有关的

上下文有关文法中不包含空产生式，空产生式就是产生式的右部β是空串的产生式

如果上下文有关文法中包含空产生式，那么β的长度就为0，而我们要求α中至少包含一个非终结符，所以α 的长度至少为1，那么α的长度大于等于1，而β的长度等于0这就与上下文有关文法的定义不符合，所以上下文有关文法中就不包含空产生式

2型文法就是上下文无关文法，左部α必须是一个非终结符，大写字母A定义的是非终结符，然后将A转换为β不需要考虑上下文，所以称为上下文无关文法

下面用来生成标识符的文法的左部被称为非终结符，称为上下文无关文法，由上下文无关文法生成的语言叫做上下文无关语言

3型文法，右线性文法在2型文法的基础上继续对产生式的右部进行限制，也就是说右线性文法的右部要么是终结符号串w，要么就是在终结符右边添加一个非终结符B

左线性文法的话要么是一个终结符，要么是在终结符左边加一个非终结符

在正则文法的表达式的右部最多只有一个非终结符

对于下面的右线性文法，首先满足了2型文法的要求，左边是一个非终结符，所以满足了上下文无关文法的要求，接下来看各个产生式的右部小写字母a、b、c、d代表的是终结符，数字也是终结符，因此下面的产生式要么是都是终结符号串，要么终结符号串右边都是非终结符号串，因此下面是一个右线性文法

其实不仅标识符可以用正则文法来描述，程序设计语言中的大多数单词都可以用正则文法来描述

每种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法