编译原理之文法二
四、著名语言学家NoamChomsky(乔姆斯基)根据对产生式所施加的限制的不同，把文法分成四种类型，即0型、1型、2型和3型。
文法类型
产生式的限制
文法产生的语言
0型文法
α→β
其中α、β∈(VT∪VN)?*，∣α∣≠0
0型语言
1型文法
α→β
其中α、β∈(VT∪VN)?*，∣α∣≤∣β∣
1型语言，即上下文有关语言
2型文法
A→β
其中A∈VN，β∈(VT∪VN)?*
2型语言，即上下文无关语言
3型文法
A→α|αB(右线性)或A→α|Bα(左线性)
其中，A，B∈VN，α∈VT∪{ε}
3型语言，即正规语言，
又分为左线性语言和右线性语言
?
0型文法：α∈(VT∪VN)?*?且至少含有一个非终结符，而β∈(VT∪VN)?*
? ? ? ? ? ? ? ? ? ? ? ?例：A→a，Aa→a,aA→a(左边至少有一个大写字母)
1型文法：有一特例：α→ε也满足1型文法。
? ? ? ? ?例：A→a，A→ab，Aa→BAc（左边至少有一个大写字母，且左边的长度小于等于右边的长度）
2型文法：每一个A→β都有A是非终结符
? ? ? ??例：A→a，A→ab，AB→BAc（在1型文法的前提下，左边必须都是大写字母）
3型文法：如有：A→a,A→aB,B→a,B→cB，则符合3型文法的要求。
但如果推导为：A→ab,A→aB,B→a,B→cB或推导为：A→a,A→Ba,B→a,B→cB则不符合3型方法的要求了。
例子：A→ab,A→aB,B→a,B→cB中的A→ab不符合3型文法的定义,如果把后面的ab,改成aB(即“一个非终结符＋一个终结符”)就对了。
例子：A→a,A→Ba,B→a,B→cB中如果把B→cB改为B→Bc的形式就对了，因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中，只能完全满足其中的一个，才能算3型文法。
?
如果所有的终端结点都是与终结符关联的，每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型，则该字符串是文法G的一个句子，此时该推导树是完全推导树。
?
如：文法G=（{a,b}，{S,A},S,P）,其中：S→aAS|a,A→SbA|SS|ba,句型aabAa相对应的构造树。
?
解释：
文法G={VT，VN，S，P}，即VT={a,b}，VN={S,A}
S→aAS|a，即S→aAS，S→a
A→SbA|SS|ba，即A→SbA，A→SS，A→ba
? ? ? ? ? ? ?
? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ?
?
五、正规文法到正规式：
?
文法产生式
正规式
规则1
A→xB，B→y
A=xy
规则2
A→xA|y
A=x*y
规则3
A→x,A→y
A=x|y
?
规则1：由A→xB，B→y，可知：A→xB→xy
规则2：由A→xA|y，可知：A→xA，A→y，依次往下推A→xA→x2A→x3A……→x*A→x*y
规则3：A→x,A→y简写成A=x|y
六、关于对计算机的意义和作用：
? ? 对于形式语言的一个分层，正规语言是最小的集合，上下文无关语言、上下文相关语言、计算语言是那些语言的扩充集合，这些语言它们可以被不同类型的设备识别，有限状态自动机，下推自动机，线性有界自动机，图灵机等等。?
详细参加：http://zhidao.baidu.com/question/124218285.html（英文的）
?
七、小结：
? ? 上面描述的这些文法是对一些式子做一些运算，α属于某个集合，β属于某个集合，α→β，需要满足的一些具体的条件，根据不同的条件又可以分为不同的类型，可以采用递推的方式，将这些式子接着往下推，即可得到正规文法到正规式。
