编译原理四种文法类型
1.基本知识
文法G定义的四元组(VN,VT,P,S)
VN---非终结符集合
VT---终结符集合
P---推导式集合
S---开始符（非终结符）
设G={VT,VN,S,P}，如果它的每个产生式α→β是这样一种结构：α∈(VT∪VN)* 且至少含有一个非终结符，
而β∈(VT∪VN)*，则G是一个0型文法。0型文法也称短语文法。
一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚
举的，反之，递归可枚举集必定是一个0型语言。
1.推导式左边要有大写字母
2.0型文法是这几类文法中限制最少的一个，所以一般见到的至少是0型文法。
1型文法也叫上下文有关文法，此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β，都有
|β|>=|α|。这里的|β|表示的是β的长度。
1. 0型文法的基础之上
2. 推导式右边的长度大于等于左边的长度
4.2型文法2型文法也叫上下文无关文法，它对应于下推自动机。2型文法是在1型文法的基础上，再满足：每一个α→β都
有α是非终结符。如A->Ba，符合2型文法要求。
4.2总结
1. 1型文法基础之上
2. 推导式左边全部都是非终结符号
5. 3型文法3型文法也叫正规文法，它对应于有限状态自动机。它是在2型文法的基础上满足：
A→α|αB（右线性）或A→α|Bα（左线性）。
1.2型文法基础上
2.
1.推导式左边
只有一位非终结符
2.推导式右边分为左线性和右线性
1.左线型
推导式右边（最多有两位最少有一位）必须有终结符
终结符在前
2.右线性
推导式右边（最多有两位最少有一位）必须有终结符
终结符在后
3.注意
推导中只能够全是左线型或者全是右线性
不能够有的推导式是左线型有的推导式是右线性
