《编译原理课件05语法制导翻译技术和中间代码生成》由会员分享，可在线阅读，更多相关《编译原理课件05语法制导翻译技术和中间代码生成（96页珍藏版）》请在金锄头文库上搜索。
1、第5章 语法制导翻译技术和中间代码生成,5.1 概述 5.2 属性文法 5.3 语法制导翻译概述 5.4 中间语言 5.5 自下而上语法制导翻译 5.6 递归下降语法制导的翻译 本章小结,语义分析的任务：,静态语义审查,审查每个语法结构的静态语义,即验证语法结构合法的程序,是否真正有意义。,5.1 概述,例如:,表达式 A+B*C,对运算对象进行类型检查, 对变量进行先定义后使用检查,如果静态语义正确, 语义处理则要执行真正的翻译, 即生成程序的某种中间代码的形式或直接生成目标代码。,执行真正的翻译,5.1 概述,目前多数编译程序进行语义分析的方法是采用语法制导翻译法 。它不是一种形式系统,
2、但它比较接近形式化。,语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。,5.1 概述,(1) 属性,对文法的每一个符号, 引进一些属 性, 这些属性代表与文法符号相关的信息, 如类型、值、存储位置等。与属性相关的信息, 即属性值,可以在语法分析过程中计算和传递。,1. 属性文法,5.2 属性文法,属性分为两类:,综合属性其计算规则按“自下而上”方式进行, 即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。,属性加工的过程即是语义的处理过程。,综合属性和继承属性。,5.2 属性文法,继承属性其计算规则按“自上而下”方式进行, 即规则右部符号的某些属性根据其左部
3、符号的属性和(或)右部其他符号的某些属性计算而得。,5.2 属性文法,(2) 属性文法,为文法的每一个规则配备的计算属性的计算规则, 称为语义规则(描述语义处理的加工动作) 。,属性文法包含一个上下文无关文法和一系列语义规则。,语义规则:,5.2 属性文法,这些语义规则附在文法的每个产生式上,在语法分析过程中, 执行语义规则描述的动作, 从而实现语义处理。也就是说, 附在文法的每个产生式上语义规则描述了语义处理的加工动作。,目前流行的语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。,5.2 属性文法,2. 语法制导翻译法,为文法的每个产生式都配备一个语义动作或语义子程序。,在语法分析
4、的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作, 从而实现语义处理。,5.3 语法制导翻译概述,(1) 语法制导翻译法 的基本思想,S, , ,Axy, , ,语义处理的加工动作,语法制导翻译法使用属性文法为工具来说明程序设计语言的语义。,5.3 语法制导翻译概述,(2) 语法制导翻译法,在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译的方法。,5.3 语法制导翻译概述,为文法每一产生式设计相应的求值的语义描述(语义动作)：,例如，设有简单算术表达式的文法：,EEE | E*E | (E) | digit
5、,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.3 语法制导翻译概述,E.val = 47,E.val = 8,E.val = 40,E.val = 7,E.val = 5,+,5,*,8,7,句子 7+8*5,E,E,E,E,E,3. 编译中常用的中间代码:,逆波兰式,四元式,三元式,树形表示,5.4 中间代码,逆波兰式,逆波兰式除去了原表达式中的括号，并将运算对象写在前面，运算符写在
6、后面，因而又称为后缀式。,例如：,逆波兰式,a*b,ab*,(a+b)*(c+d),ab+cd+*,中缀表达式,5.4 中间代码,逆波兰式表示法同中缀表示法相比其优点是:,不再有括号,且运算符出现的顺序体现了中缀表达式 的运算顺序,2. 易于计算机处理,5.4 中间代码,一般表达式计值时，要处理两类符号，一类是运算对象，另一类是运算符，通常用两个工作栈分别处理。但处理用逆波兰式表示的表达式却只用一个工作栈。,5.4 中间代码,当计算机自左到右顺序扫描逆兰波式时，若当前符号是运算对象则进栈，若当前符号是运算符，设为K元运算符，则将栈顶的K个元素依次取出，同时进行K元运算，并将运算结果置于栈顶，表
7、达式处理完毕时，其计算结果自然呈现在栈顶。,5.4 中间代码,逆波兰式ab+c*的处理过程如下图：,5.4 中间代码,逆波兰形式可以推广到其他语法结构：,赋值语句,V=E,逆波兰式,VE=,条件语句,逆波兰式,if E S1 ; else S2,ES1S2￥,5.4 中间代码,三元式和树形表示,三元式主要由三部分组成：,（OP，arg1, arg2）,其中OP是运算符，,arg1,arg2分别是第一和第二两个运算对象。,当OP是一目运算时，常常将运算对象定义为arg1。,第5章 语法制导翻译技术和中间代码生成,例如 a+b*c 的 三元式序列：,(1) ( * , b , c ),(2) (
8、+ , a , (1) ),运算对象是指向符号表的某一项或指向三元式表的某一项。,5.4 中间代码,1. 三元式出现的顺序和语法成份的 计值顺序相一致。,三元式的特点：,2. 三元式之间的联系是通过指示器实现的。,5.4 中间代码,间接三元式,(1) 间接三元式表: 用来存放各三元式本身。,(2) 间接码表: 按执行各三元式的顺序,依次 列出各三元式在三元式表中的位置。,注意 : 间接三元式表中不存放重复的三元式。,5.4 中间代码,例如 语句,X= (A+B)*C,Y= D(A+B),三元式序列,(1) ( + , A , B ),(2) ( * , (1) , C ),(3) ( = ,
9、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.4 中间代码,树形表示,A * B + C*D,+,C,*,A,*,B,D,末端结点表示一个运算对象, 每一个内结点表示一个一元或二元运算符。,树形表示是三元式的翻版,(3)+,(1)*,(2)*,C
10、,A,B,D,5.4 中间代码,四元式主要由四部分组成：,（OP，arg1, arg2, result）,其中OP是运算符，,arg1,arg2分别是第一和第二两个运算对象。,当OP是一目运算时，常常将运算对象定义为arg1。,5.4 中间代码,四元式的第四个分量result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。,例如 X a*bc/d 的 四元式序列：,(1) ( *, a, b, T1 ),(2) ( /, c, d, T2 ),(3) ( +, T1, T2, T3 ),(4) ( =, T3, -, X ),5.4 中间代码
11、,2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。,1. 四元式出现的顺序和语法成份的计值 顺序相一致。,四元式的特点：,3. 便于优化处理。,5.4 中间代码,编译系统中，有时将四元式表示成另一种更直观，更易理解的形式三地址代码或三地址语句。,result : arg1 OP arg2,三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。,三地址代码形式定义为：,5.4 中间代码,例如 X a*bc/d 的 四元式序列：,(1) ( *, a, b, T1 ),(2) ( /, c, d, T2 ),(3) ( +, T1, T2, T3 ),(4) ( =,
12、T3, -, X ),相应的三地址语句序列为：,（1）T1a*b,（2）T2c/d,（3）T3T1T2,（4）XT3,5.4 中间代码,例1. a + b * ( c + d )的逆波兰式,a bc d + * +,5.4 中间代码,t1= a,t2= c,t3= t2 + d,t5= t1+ t4,a + b * ( c + d )的四元式表示,t4= b* t3,5.4 中间代码,i( i /( i i ) )的逆波兰式,i( i /( i i ) )的四元式,t1= i i,t2= i / t1,t3= i t2,i i i i /,例2.,5.4 中间代码,4. 采用自下而上的语法制导
13、翻译法语义 动作的设计,（1）搞清楚源结构和目标结构,（2）自下而上的语法制导翻译特点：栈顶形成句柄，归约时执行相应语义动作,（3）给出从源结构到目标结构的变换方法,5.5 自下而上的语法制导翻译,例1. 设文法及其相应的语义动作如下:,SbTc print “1”,Sa print “2”,TR print “3”,RR/S print “4”,RS print “5”,采用自下而上语法制导翻译,给出输入串bR / bTc / bSc / ac的翻译结果,5.5 自下而上的语法制导翻译,分析: 首先对输入串 bR / bTc / bSc /ac画出语法树:,S,c,T,b,R,S,/,R,/
14、,R,S,/,R,c,T,b,a,S,c,T,b,R,S,再考虑归约时执行相应语义动作,5.5 自下而上的语法制导翻译,1,4,翻译结果为:,5,3,1,4,2,4,3,1,5.5 自下而上的语法制导翻译,输出为:,输入是bR / bTc / bSc /ac,给出相应语义动作(翻译方案), print “1”, print “2”, print “3”, print “4”, print “5”,5.5 自下而上的语法制导翻译,例2 简单算术表达式求值的语义描述,例如，设有简单算术表达式的文法：,EEE | E*E | (E) | digit,1.E E(1)E(2),E.val E(1).v
15、al 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.5 自下而上的语法制导翻译,例3 简单算术表达式翻译到四元式的语义描述,例如，设有简单算术表达式的文法：,EEE | E*E | (E) | i,5.5 自下而上的语法制导翻译,E EEE*E(E) | i,源结构,目标结构,（1）T1a*b,（2）T2c*d,（3）T3T1T2,a*bc*d,5.5 自下而上的语法制导翻译,语义函数 emit（Targ1 OP arg2）,功能是生成一个三地址语句，并送到输出文件中。,
