语法制导翻译技术.ppt

语义分析的任务：,静态语义审查,审查每个语法结构的静态语义,即验证语法结构合法的程序,是否真正有意义。,第5章 语法制导翻译技术和中间代码生成,5.1 概述,例如:,表达式 A+B*C,对运算对象进行类型检查, 对变量进行先定义后使用检查,如果静态语义正确, 语义处理则要执行真正的翻译, 即生成程序的某种中间代码的形式或直接生成目标代码。,执行真正的翻译,第5章 语法制导翻译技术和中间代码生成,目前多数编译程序进行语义分析的方法是采用语法制导翻译法 。它不是一种形式系统, 但它比较接近形式化。,语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。,第5章 语法制导翻译技术和中间代码生成,(1) 属性,对文法的每一个符号, 引进一些属 性, 这些属性代表与文法符号相关的信息, 如类型、值、存储位置等。与属性相关的信息, 即属性值,可以在语法分析过程中计算和传递。,5.2 属性文法,第5章 语法制导翻译技术和中间代码生成,属性分为两类:,综合属性其计算规则按“自下而上”方式进行, 即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。,属性加工的过程即是语义的处理过程。,综合属性和继承属性。,第5章 语法制导翻译技术和中间代码生成,继承属性其计算规则按“自上而下”方式进行, 即规则右部符号的某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算而得。,第5章 语法制导翻译技术和中间代码生成,(2) 属性文法,为文法的每一个规则配备的计算属性的计算规则, 称为语义规则(描述语义处理的加工动作) 。,属性文法包含一个上下文无关文法和一系列语义规则。,语义规则:,第5章 语法制导翻译技术和中间代码生成,这些语义规则附在文法的每个产生式上,在语法分析过程中, 执行语义规则描述的动作, 从而实现语义处理。也就是说, 附在文法的每个产生式上语义规则描述了语义处理的加工动作。,目前流行的语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。,第5章 语法制导翻译技术和中间代码生成,G： EE+T |T TT*F |F F(E)|i G： DTL Tinteger |real LL,id|id,5.3 语法制导翻译概述,为文法的每个产生式都配备一个语义动作或语义子程序。,在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作, 从而实现语义处理。,第5章 语法制导翻译技术和中间代码生成,(1) 语法制导翻译法 的基本思想,S, , ,Axy, , ,语义处理的加工动作,语法制导翻译法使用属性文法为工具来说明程序设计语言的语义。,第5章 语法制导翻译技术和中间代码生成,(2) 语法制导翻译法,在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译的方法。,第5章 语法制导翻译技术和中间代码生成,为文法每一产生式设计相应的求值的语义描述(语义动作)：,例如，设有简单算术表达式的文法：,EEE | E*E | (E) | digit,1.E E(1)E(2),E.val E(1).val E(2).val,2.E E(1)*E(2),E.val E(1).val*E(2).val,3.E (E(1),E.val E(1).val,4.E digit,E.val Lex.digit,第5章 语法制导翻译技术和中间代码生成,句子 7+8*5,5.4 编译中常用的中间代码:,逆波兰式,四元式,三元式,树形表示,第5章 语法制导翻译技术和中间代码生成,逆波兰式,逆波兰式除去了原表达式中的括号，并将运算对象写在前面，运算符写在后面，因而又称为后缀式。,例如：,逆波兰式,a*b,ab*,(a+b)*(c+d),ab+cd+*,中缀表达式,第5章 语法制导翻译技术和中间代码生成,逆波兰式表示法同中缀表示法相比其优点是:,不再有括号,且运算符出现的顺序体 现了中缀表达式 的运算顺序,2. 易于计算机处理,第5章 语法制导翻译技术和中间代码生成,一般表达式计值时，要处理两类符号，一类是运算对象，另一类是运算符，通常用两个工作栈分别处理。但处理用逆波兰式表示的表达式却只用一个工作栈。,第5章 语法制导翻译技术和中间代码生成,当计算机自左到右顺序扫描逆兰波式时，若当前符号是运算对象则进栈，若当前符号是运算符，设为K元运算符，则将栈顶的K个元素依次取出，同时进行K元运算，并将运算结果置于栈顶，表达式处理完毕时，其计算结果自然呈现在栈顶。,第5章 语法制导翻译技术和中间代码生成,逆波兰式ab+c*的处理过程如下图：,第5章 语法制导翻译技术和中间代码生成,逆波兰形式可以推广到其他语法结构：,赋值语句,V=E,逆波兰式,VE=,条件语句,逆波兰式,if E S1 ; else S2,ES1S2￥,第5章 语法制导翻译技术和中间代码生成,三元式和树形表示,三元式主要由三部分组成：,（OP，arg1, arg2）,其中OP是运算符，,arg1,arg2分别是第一和第二两个运算对象。,当OP是一目运算时，常常将运算对象定义为arg1。,第5章 语法制导翻译技术和中间代码生成,例如 a+b*c 的 三元式序列：,(1) ( * , b , c ),(2) ( + , a , (1) ),运算对象是指向符号表的某一项或指向三元式表的某一项。,第5章 语法制导翻译技术和中间代码生成,1. 三元式出现的顺序和语法成份的 计值顺序相一致。,三元式的特点：,2. 三元式之间的联系是通过指示器 实现的。,第5章 语法制导翻译技术和中间代码生成,间接三元式,(1) 间接三元式表: 用来存放各三元式本身。,(2) 间接码表: 按执行各三元式的顺序,依次 列出各三元式在三元式表中的位置。,注意 : 间接三元式表中不存放重复的 三元式。,第5章 语法制导翻译技术和中间代码生成,例如 语句,X= (A+B)*C,Y= D(A+B),三元式序列,(1) ( + , A , B ),(2) ( * , (1) , C ),(3) ( = , X , (2) ),(5) ( , D , (4) ),(4) ( + , A , B ),(6) ( = , Y, (5) ),间接三元式,间接码表,三元式表,(1)(2)(3) (1) (4) (5),(1) ( + , A , B ),(2) ( * , (1) , C ),(3) ( = , X , (2) ),(4) ( , D , (1) ),(5) ( = , Y, (4) ),第5章 语法制导翻译技术和中间代码生成,树形表示,A * B + C*D,+,C,*,A,*,B,D,末端结点表示一个运算对象, 每一个内结点表示一个一元或二元运算符。,树形表示是三元式的翻版,(3)+,(1)*,(2)*,C,A,B,D,第5章 语法制导翻译技术和中间代码生成,四元式主要由四部分组成：,（OP，arg1, arg2, result）,其中OP是运算符，,arg1,arg2分别是第一和第二两个运算对象。,当OP是一目运算时，常常将运算对象定义为arg1。,第5章 语法制导翻译技术和中间代码生成,四元式的第四个分量result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。,例如 X a*bc/d 的 四元式序列：,(1) ( *, a, b, T1 ),(2) ( /, c, d, T2 ),(3) ( +, T1, T2, T3 ),(4) ( =, T3, -, X ),第5章 语法制导翻译技术和中间代码生成,2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。,1. 四元式出现的顺序和语法成份的计值 顺序相一致。,四元式的特点：,3. 便于优化处理。,第5章 语法制导翻译技术和中间代码生成,四元式还可以表示条件的转移 (if ab goto 0) (goto 0),编译系统中，有时将四元式表示成另一种更直观，更易理解的形式三地址代码或三地址语句。,result : arg1 OP arg2,三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。,三地址代码形式定义为：,第5章 语法制导翻译技术和中间代码生成,例如 X a*bc/d 的 四元式序列：,(1) ( *, a, b, T1 ),(2) ( /, c, d, T2 ),(3) ( +, T1, T2, T3 ),(4) ( =, T3, -, X ),相应的三地址语句序列为：,（1）T1a*b,（2）T2c/d,（3）T3T1T2,（4）XT3,第5章 语法制导翻译技术和中间代码生成,例1. a + b * ( c + d )的逆波兰式,a bc d + * +,第5章 语法制导翻译技术和中间代码生成,t1= a,t2= c,t3= t2 + d,t5= t1+ t4,a + b * ( c + d )的四元式表示,t4= b* t3,第5章 语法制导翻译技术和中间代码生成,i( i /( i i ) )的逆波兰式,i( i /( i i ) )的四元式,t1= i i,t2= i / t1,t3= i t2,i i i i /,例2.,第5章 语法制导翻译技术和中间代码生成,语义函数 emit（Targ1 OP arg2）,功能是生成一个三地址语句，并送到输出文件中。,语义函数 newtemp( ),功能是产生一个新的临时变量名字，并回送新的临时变量名的整数码。如T1，T2等。,5.5.1 简单算术表达式和赋值语句的翻译,(2) 不进符号表，临时变量单词值部 分用整数码表示。,(1) 送到符号表。,对临时变量有两种不同的处理方法:,第5章 语法制导翻译技术和中间代码生成,语义过程 Lookup（）,功能是审查是否出现在符号表中，在则返回其指针，否则返回NULL。,语义变量 E.place,表示存放非终结符E值的变量名在符号表中的入口地址或临时变量名的整数码。,第5章 语法制导翻译技术和中间代码生成,1. E E(1) E(2),2. E E(1) * E(2), E.place newtemp( ); emit(E.placeE(1).placeE(2).place ) , E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) ,第5章 语法制导翻译技术和中间代码生成,3. E （E(1)）, E.place E(1).place；,4. E i, p Lookup (); if (p != NULL) E.place p; else error( ); ,第5章 语法制导翻译技术和中间代码生成,5. Ai=E, p Lookup (); if (p != NULL) emit(pE.place; ) else error( ); ,5.5.2布尔表达式到四元式的翻译,一.布尔表达式的文法, 计算逻辑值,程序设计语言中布尔表达式有两个作用:, 用作控制语句中的条件式,布尔表达式是由布尔算符(、和)施于布尔变量或关系表达式而成。,布尔表达式到四元式的翻译,E E (1) E (2),E E (1) E (2),E E (1),E ( E (1) ),E i (1) rop i (2),E i,布尔表达式到四元式的翻译,二. 布尔表达式的计值方法,1. 如同计算算术表达式一样,步步计算出各部分真、假值,最后计算出整个表达式的值。,2. 根据布尔运算的特殊性,采取某种优化措施,可避免计算整个表达式的值。,布尔表达式到四元式的翻译,AB 解释成,AB 解释成, A 解释成,if A then true else B,if A then B else false,if A then false else true,三. 布尔表达式的翻译方法,1. 同翻译算术表达式一样,翻译布尔表达式。,布尔表达式到四元式的翻译,1. E E (1) E (2), E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) ,2. E E (1) E (2), E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) ,3. E ( E (1) ), E.place E(1).place；,4. E i (1) rop i (2), E.place newtemp( )； emit (if i (1).place rop.op i (2).place goto nextq+3); emit ( E.place 0 ); emit ( goto nextq+2); emit ( E.place 1 ); , E.place i . place；,5. E i,布尔表达式到四元式的翻译,例如布尔表达式 a = bc d 对应如下四元式序列:,101 if a = b goto 104,102 t1= 0,103 goto 105,104 t1= 1,105 t2= c d,106 t3 = t1 t2,布尔表达式到四元式的翻译,2. 控制语句中布尔表达式的翻译,条件语句的语法为:,根据条件语句的语义,条件语句的代码结构为:,if E then S(1) else S(2),E的代码,S(1)的代码,S(2)的代码,Jump out,out:,真,假,布尔表达式到四元式的翻译,E是布尔表达式,根据布尔运算的特殊性,布尔表达式的目标结构为:,假,E(1)的代码,E(2)的代码,真,S(1),S(2),真,假,真,E(1)的代码,E(2)的代码,假,S(2),S(1),假,真,(1) 真出口和假出口:,真出口表示布尔表达式E为真时控制流向的转移目标,假出口表示布尔表达式E为假时控制流向的转移目标,布尔表达式到四元式的翻译,(2) 作为条件转移的E,把E翻译成的代码 是一串条件转或无条件转的四元式,对于E为 a rop b 的形式生成代码为:,if a rop b goto 真出口,goto 假出口,布尔表达式到四元式的翻译,布尔表达式到四元式的翻译,布尔表达式的真、假出口不能在产生其四元式的同时得知,E.true: 记录表达式 E 所对应的四元式需回填真出口的四元式的地址所构成的链,E.false: 记录表达式 E 所对应的四元式需回 填假出口的四元式的地址所构成的链,(3) 设置两个语义变量:,布尔表达式到四元式的翻译,把以 p1, p2为链首的两条链合并为一, 返回合并后的链首,(4) 链结函数和回填函数:, merge (p1, p2) :, backpatch ( int p, int t ) :,将 p 所链结的每个四元式的第四区分量都回填 t ;,布尔表达式到四元式的翻译,为及时回填转移地址, 使用语义变量 E. bcode 记录表达式E的第一个四元式语句序号。,(6) 定义语义变量 nextq 为四元式表指针。,布尔表达式到四元式的翻译,布尔表达式语义动作的设计,1. E E (1) E (2), backpatch( E(1).false, E(2). bcode) ； E. bcode= E(1).bcode ; E.true=merge ( E(1).true, E(2).true ) ; E.false= E(2).false ; ,布尔表达式到四元式的翻译,布尔表达式语义动作的设计,2. E E (1) E (2), backpatch( E(1).true, E(2).bcode) ； E.bcode= E(1).bcode ; E.true= E(2).true ; E.false=merge( E(1).false, E(2).false ) ; ,布尔表达式语义动作的设计,3. E E (1), E.bcode= E(1).bcode ; E.true=E(1). false ; E.false= E(1). true ; ,布尔表达式到四元式的翻译,4. E ( E (1) ), E.bcode= E(1).bcode ; E.true=E(1).true ; E.false= E(1).false ; ,布尔表达式语义动作的设计,5. E i (1) rop i (2), E.true= nextq ; E.bcode= nextq ; E.false= nextq+1; emit ( if i (1).place rop.op i (2).place goto 0 ) ; emit( goto 0 ) ; ,布尔表达式到四元式的翻译,布尔表达式到四元式的翻译,布尔表达式语义动作的设计,6. E i, E.true= nextq ; E.false= nextq +1; E.bcode= nextq ; emit(if i.place goto 0); emit( goto 0 ) ; ,布尔表达式到四元式的翻译,例如布尔表达式 a bc d 的翻译过程,5.5.3 控制语句的翻译,1. S if E then S(1) 2. | if E then S(1) else S(2) 3. | while E do S(1) 4. LL ；