四、著名语言学家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(英文的)
七、小结:
上面描述的这些文法是对一些式子做一些运算,α属于某个集合,β属于某个集合,α→β,需要满足的一些具体的条件,根据不同的条件又可以分为不同的类型,可以采用递推的方式,将这些式子接着往下推,即可得到正规文法到正规式。
分享到:
相关推荐
此程序采用了加标记法 输入一个程序 得到的是压缩后的结果
编译原理LL1文法实现,使用D盘下TXT文档输入字符串例子
编译原理实验二:压缩文法的等价变换,,zip文件里包含实验报告和源代码两部分。
本程序解决了编译原理中文法的输入输出问题,识别符号是固定的,其他文法顺序自定。
编译原理2文法和形式语言 编译原理2文法和形式语言 编译原理2文法和形式语言 编译原理2文法和形式语言 编译原理2文法和形式语言
东北大学编译原理课设,C语言编译器,C语言文法流程图。 东北大学编译原理课设:C语言编译器,绘制的C语言文法流程图。供学弟学妹们参考,希望对你们有所帮助。
C语言文法,在网上找到的,对学编译原理很有帮助。
编译原理课程设计,LL1文法的实现。采用MFC。输入文法,分别求出每一个非终结符FIRST 集FOLLOW集和SELECT集,画出预测分析表,判定读入的文法是否是LL(1)文法,给定的任意符号串判定是否是文法中的句子,将分析过程...
大学编译原理实验用,LL1文法(C++编写)。不错的资源
编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告...
编译原理-文法和语言 很详细,复习编译原理-文法和语言的同学可以重点复习一下。
自己写的编译原理实验代码,有文法压缩,文法分析,预测分析和dfa等内容,欢迎指正。
文法和语言在编译原理中的详细介绍,更加深刻的了解文法和语言在编译原理学中的详细知识
LL1分析法,对于给定文法进行判断是否位LL1文法,并做相应变换使之满足LL1输出格式,对于给定的表达式和字符串输出预测分析过程 功能代码完善而全面,有图形化界面供大家参考。
里面就一个文件夹,是写出来的源程序,里面有源代码。可以运行的。
编译原理开发设计,采用LL1文法,界面MFC设计。
正规式转化为右线性文法输出正规式转化为右线性文法输出
AIIT 编译原理实验四LL(1)文法
C++实现编译原理自动机、LL1文法、及LR(0)文法的代码
编译原理LL1文法分析器C++详细源代码