编译原理2.3.3文法类型.ppt

上传人:sccc 文档编号:5665735 上传时间:2023-08-07 格式:PPT 页数:24 大小:188.01KB
返回 下载 相关 举报
编译原理2.3.3文法类型.ppt_第1页
第1页 / 共24页
编译原理2.3.3文法类型.ppt_第2页
第2页 / 共24页
编译原理2.3.3文法类型.ppt_第3页
第3页 / 共24页
编译原理2.3.3文法类型.ppt_第4页
第4页 / 共24页
编译原理2.3.3文法类型.ppt_第5页
第5页 / 共24页
点击查看更多>>
资源描述

《编译原理2.3.3文法类型.ppt》由会员分享,可在线阅读,更多相关《编译原理2.3.3文法类型.ppt(24页珍藏版)》请在三一办公上搜索。

1、2.3.3 形式语言鸟瞰,一、文法的四种类型二、文法四种类型的包含关系三、文法四种类型的描述能力,一、文法的四种类型,乔姆斯基(Chomsky)产生式,V=VNVT V+,V*对产生式施加不同的限制 文法的四种类型:0型、1型、2型和3型,0型文法(短语文法)PSG Phrase Structure Grammar,V+,V*至少含有一个非终结符0型文法的能力相当于图灵机任何0型语言都是递归可枚举的;递归可枚举集必定是一个0型语言,1型文法(上下文有关文法)CSG Context-Sensitive Grammar,定义1:每个产生式均满足|,(仅仅S例外,但S不出现在其他产生式的右边)定义2

2、:产生式的形式:A,即左部的一个非终结符在推导时,它左右的字符串必须保持原样.,2型文法(上下文无关文法)Context-Free Grammar CFG,产生式的形 式:A AVN,V*2型文法一定满足1型文法的定义|A|关于 A,补充定理:有关上下文无关文法中的规则,若L是由文法G产生的语言,G每个产生式的形式均为A,AVN,V*,(可为)则L能由这样的一种文法产生,即:每个产生式或者为A形式,V或者为S的形式,且S不在任何产生式的右边,3型文法(正规文法,正则文法)A regular grammar,右线性文法:AB 或 A,VT*左线性文法:AB 或 A,VT*,3型文法的另一个定义,

3、右线性文法:AaB 或 Aa,aVT左线性文法:ABa 或 Aa,aVT,补充,小结,产生式:,V+,V*0型:,V+,V*至少含有一个非终结符1型:,V+,V*|(仅S例外,但S不出现在其他产生式的右边)2型:A,AVN,V*3型:AB 或 A,VT*,二、文法四种类型的包含关系,G1:SCDAbbACaCABaaBCbCB BbbBADaD CaBDbD DbAabDG1是上下文有关文法,请判断以下文法的类型,补充例,G2:SaB,AbAASbA,BbAa,BbSAaS,BaBBG2是上下文无关文法,补充例,G3:S0A A1BS1B B1BS0 B1A0A B0A0SG3是正规文法,补充

4、例,G4:I lT|lT lT|dT|l|d其中l 表示az中的任何一英文字母,d 表示09中的任一数字。G4是正规文法,补充例,三、文法四种类型的描述能力,L(T3)L(T2)L(T1)L(T0),上下文有关语言上下文无关语言正规语言,3型语言举例 L(T3),L=an bam|n,m1 G:SaS,SaB,BbC,CaC,Ca,_型文法,补充例,3,L(T3)L(T2),存在一个语言是2型语言 而非3型语言 L(G)=an bn|n1 无法用正则文法描述 G:SaSb|ab,p34,以下语言是_型语言,L=an ban|n1 G:SaAa,AaAa,Ab,2,补充例,L(T2)L(T1),

5、存在一个语言是1型语言 而非2型语言L=anbmanbmccc|n,m1 无法用上下文无关文法描述,补充例,L=anbnci|n1,i1 是上下文无关 语言L=anbncn|n1 无法用上下文无关文法产生,P35,L(T1)L(T0),存在一个语言是0型语言 而非1型语言L=c|(a|b)*只能用0型文法产生.,P35,补充:Decision problem,Decision problem 判断一个符号串是否是一个语言的句子Fully Decidable 存在一个算法在有限时间内给出答案Semi-decidable(Recursively Enumerable)存在一个算法,如果符号串是该语言的句子,将在有限时间内回答“是”如果符号串不是该语言的句子,可能无法在有限的时间内给出答案,补充:文法和识别系统,0型文法-图灵机 1型文法-线性界限自动机 2型文法-不确定的下推自动机3型文法-有穷自动机,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 建筑/施工/环境 > 农业报告


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号