编译原理-文法类型.ppt

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:产生式的形式: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型文法的另一个定义,右线性文法: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是正规文法,补充例,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),存在一个语言是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型文法-有穷自动机,