编译原理第3讲(第三章)..ppt
1,第三章文法和语言,符号和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,2,文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+，(VNVT)*1型文法：对任一产生式，都有|，仅仅 S除外2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT*,3,1型文法,例：1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbB ADaDCa BDbDDb AabD,4,2型文法,例：2型（上下文无关）文法 文法GS：SABABS|0BSA|1,5,3型文法,GS：S0A|1B|0A0A|1B|0SB1B|1|0,GI：I lTI lT lTT dTT lT d,6,文法的类型关系,0型文法,3型文法,四类文法之间的逐级“包含”关系,7,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CF L）3型文法或正则（正规）文法（RG）产生的语言称为3型语言或正则（正规）语言（RL）,8,文法和语言,四种文法之间的关系：是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,9,根据形式语言理论,文法和识别系统间有这样的关系,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合,10,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述,图灵机,11,上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构语法树-句型推导的直观表示,12,句型推导的例子,GE：EE+T|T TT*F|F F(E)|a给出句型（句子）a+a*a的推导。EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,13,规范推导与规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。,14,语法树,设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树或派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行，谓之。,15,上下文无关文法的语法树,例:GS:SaAS ASbA ASS Sa Aba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,句型aabbaa的可能推导序列和语法树,16,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)定理：G为上下 文无关文法，对于，有S=*，当且仅当文法G有以为结果的一棵语法树(推导树),一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,17,例子,例：GE:E iE E+EE E*EE(E),E E+E E*E i i i,E E*E i E+E i i,句型 i*i+i 的两个不同的最左推导：推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导2：E E*E i*E i*E+E i*i+E i*i+i,18,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,19,文法的二义性和语言的二义性,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。二义文法改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E F（E）|i E(E)规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,
