《编译原理第3讲(第三章)..ppt》由会员分享，可在线阅读，更多相关《编译原理第3讲(第三章)..ppt（19页珍藏版）》请在三一文库上搜索。
1、1,第三章 文法和语言,符号和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明,2,文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型： 0型文法：对任一产生式，都有(VNVT)+， (VNVT)* 1型文法：对任一产生式，都有|， 仅仅 S除外 2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT *,3,1型文法,例：1型（上下文有关）文法 文法GS：SCD AbbA CaCA BaaB CbCB BbbB ADaD Ca BDbD Db Aa
2、bD,4,2型文法,例：2型（上下文无关）文法 文法GS： SAB ABS|0 BSA|1,5,3型文法,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,GI： I lT I l T lT T dT T l T d,6,文法的类型关系,0型文法,3型文法,四类文法之间的逐级“包含”关系,7,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言或正则（
3、正规）语言（ RL ）,8,文法和语言,四种文法之间的关系：是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,9,根据形式语言理论,文法和识别系统间有这样的关系,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。 2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下
4、推自动机。 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*a EE+T E+T*F
5、 E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+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. 根的标记是S 3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定
6、AVN 4. 如果结点n有标记A，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标记而构成的行，谓之。,15,上下文无关文法的语法树,例: GS: SaAS ASbA ASS Sa Aba,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,句型aabbaa的可能推导序列和语法树,16,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的
7、语法树(推导树) 定理：G为上下 文无关文法，对于，有S =* ，当且仅当文法G有以为结果的一棵语法树(推导树),一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,17,例子,例：GE: E i E E+E E E*E E (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
8、+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) 规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,