编译原理第07章中间代码生成

《编译原理第07章中间代码生成》由会员分享，可在线阅读，更多相关《编译原理第07章中间代码生成（92页珍藏版）》请在金锄头文库上搜索。

1、语义分析的任务：,静态语义审查,审查每个语法结构的静态语义,即验证语法结构合法的程序,是否真正有意义。,第7章 语法制导翻译技术和中间代码生成,例如:,表达式 A+B*C,对运算对象进行类型检查, 对变量进行先定义后使用检查,如果静态语义正确, 语义处理则要生成程序的某种中间代码的形式或直接生成目标代码。,执行真正的翻译,第7章 语法制导翻译技术和中间代码生成,目前多数编译程序进行语义分析的方法是采用语法制导翻译法。它不是一种形式系统, 但它比较接近形式化。,语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。,第7章 语法制导翻译技术和中间代码生成,(1) 属性,对文法的每一个符号,

2、引进一些属 性, 这些属性代表与文法符号相关的信息, 如类型、值、存储位置等。 与属性相关的信息, 即属性值,可以在语法分析过程中计算和传递。,1. 属性文法,第7章 语法制导翻译技术和中间代码生成,属性分为两类:,综合属性其计算规则按“自下而上”方式进行, 即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算得到。,属性加工的过程即是语义的处理过程。,综合属性和继承属性。,第7章 语法制导翻译技术和中间代码生成,继承属性其计算规则按“自上而下”方式进行, 即规则右部符号的某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算得到。,第7章 语法制导翻译技术和中间代码

3、生成,(2) 属性文法,为文法的每一个规则配备的计算属性的计算规则, 称为语义规则(描述语义处理的加工动作) 。,属性文法包含一个上下文无关文法和一系列语义规则。,语义规则:,第7章 语法制导翻译技术和中间代码生成,2. 语法制导翻译法,为文法的每个产生式都配备一个语义动作或语义子程序。,在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作, 从而实现语义处理。,第7章 语法制导翻译技术和中间代码生成,(1) 语法制导翻译法的基本思想,S, , ,Axy, , ,语义处理的加工动作,语法制导翻译法使用属性文法为工具来说明程序设计语言的语义。,第7章 语法制导翻译技

4、术和中间代码生成,(2) 语法制导翻译法,在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译的方法。,第7章 语法制导翻译技术和中间代码生成,为文法每一产生式设计相应的求值的语义描述(语义动作)：,例1:设有简单算术表达式的文法：,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,第7章

5、 语法制导翻译技术和中间代码生成,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,例2： SPS print”A” SPQ print”B” Pa print”C” QdQ print”D” QbR print”E” Rc print”F” 则采用自下而上分析法，分析输入序列aaadbc， 输出为？,第7章 语法制导翻译技术和中间代码生成,3. 编译中常用的中间代码:,逆波兰式,四元式,三元式,树形表示,第7章 语法制导翻译技术和中间代码生成,逆波兰式,逆波兰式除去了原表达式中的括

6、号，并将运算对象写在前面，运算符写在后面，因而又称为后缀式。,例如：,逆波兰式,a*b,ab*,(a+b)*(c+d),ab+cd+*,中缀表达式,第7章 语法制导翻译技术和中间代码生成,逆波兰式表示法同中缀表示法相比其优点是:,不再有括号,且运算符出现的顺序体 现了中缀表达式的运算顺序,2. 易于计算机处理,第7章 语法制导翻译技术和中间代码生成,一般表达式计值时，要处理两类符号，一类是运算对象，另一类是运算符，通常用两个工作栈分别处理。但处理用逆波兰式表示的表达式却只用一个工作栈。,第7章 语法制导翻译技术和中间代码生成,当计算机自左到右顺序扫描逆兰波式时，若当前符号是运算对象则进栈，若当

7、前符号是运算符，设为K元运算符，则将栈顶的K个元素依次取出，同时进行K元运算，并将运算结果置于栈顶，表达式处理完毕时，其计算结果自然呈现在栈顶。,第7章 语法制导翻译技术和中间代码生成,逆波兰式ab+c*的处理过程如下图：,第7章 语法制导翻译技术和中间代码生成,逆波兰形式可以推广到其他语法结构：,赋值语句,V=E,逆波兰式,VE=,条件语句,逆波兰式,if E S1 ; else S2,ES1S2￥,第7章 语法制导翻译技术和中间代码生成,三元式和树形表示,三元式主要由三部分组成：,（OP，arg1, arg2）,其中OP是运算符，,arg1,arg2分别是第一和第二个运算对象。,当OP是一

8、元运算时，常常将运算对象定义为arg1。,第7章 语法制导翻译技术和中间代码生成,例如 a+b*c 的 三元式序列：,(1) ( * , b , c ),(2) ( + , a , (1) ),运算对象是指向符号表的某一项或指向三元式表的某一项。,第7章 语法制导翻译技术和中间代码生成,1. 三元式出现的顺序和语法成分的 计值顺序相一致。,三元式的特点：,2. 三元式之间的联系是通过指示器 实现的。,第7章 语法制导翻译技术和中间代码生成,间接三元式,(1) 间接三元式表: 用来存放各三元式本身。,(2) 间接码表: 按执行各三元式的顺序,依次 列出各三元式在三元式表中的位置。,注意 : 间接

9、三元式表中不存放重复的 三元式。,第7章 语法制导翻译技术和中间代码生成,例如 语句,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)

10、 ( = , Y, (4) ),第7章 语法制导翻译技术和中间代码生成,树形表示,A * B + C*D,+,C,*,A,*,B,D,末端结点表示一个运算对象, 每一个内结点表示一个一元或二元运算符。,树形表示是三元式的翻版,(3)+,(1)*,(2)*,C,A,B,D,第7章 语法制导翻译技术和中间代码生成,四元式主要由四部分组成：,（OP，arg1, arg2, result）,其中OP是运算符，,arg1,arg2分别是第一和第二两个运算对象。,当OP是一目运算时，常常将运算对象定义为arg1。,第7章 语法制导翻译技术和中间代码生成,四元式的第四个分量result是编译程序为存放中间运

11、算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。,例如 X a*bc/d 的 四元式序列：,(1) ( *, a, b, T1 ),(2) ( /, c, d, T2 ),(3) ( +, T1, T2, T3 ),(4) ( =, T3, -, X ),第7章 语法制导翻译技术和中间代码生成,2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。,1. 四元式出现的顺序和语法成份的计值 顺序相一致。,四元式的特点：,3. 便于优化处理。,第7章 语法制导翻译技术和中间代码生成,编译系统中，有时将四元式表示成另一种更直观，更易理解的形式三地址代码

12、或三地址语句。,result : arg1 OP arg2,三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。,三地址代码形式定义为：,第7章 语法制导翻译技术和中间代码生成,例如 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,第7章 语法制导翻译技术和中间代码生成,例1. a + b * ( c + d )的逆波兰式,a bc d + *

13、 +,第7章 语法制导翻译技术和中间代码生成,t1= a,t2= c,t3= t2 + d,t5= t1+ t4,a + b * ( c + d )的四元式表示,t4= b* t3,第7章 语法制导翻译技术和中间代码生成,i( i /( i i ) )的逆波兰式,i( i /( i i ) )的四元式,t1= i i,t2= i / t1,t3= i t2,i i i i /,例2.,第7章 语法制导翻译技术和中间代码生成,4. 采用自下而上的语法制导翻译法语义动作的设计,（1）搞清楚源结构和目标结构,（2）自下而上的语法制导翻译特点： 栈顶形成句柄，归约时执行相应语义 动作,（3）给出从源结

14、构到目标结构的变换 方法,第7章 语法制导翻译技术和中间代码生成,例1. 设文法及其相应的语义动作如下:,SbTc print “1”,Sa print “2”,TR print “3”,RR/S print “4”,RS print “5”,采用自下而上语法制导翻译,给出输入串bR / bTc / bSc / ac的翻译结果,第7章 语法制导翻译技术和中间代码生成,分析: 首先对输入串 bR / bTc / bSc /ac画出规范规约的语法树:,S,再考虑归约时执行相应语义动作,第7章 语法制导翻译技术和中间代码生成,1,4,翻译结果为:,5,3,1,4,2,4,3,1,第7章 语法制导翻译

15、技术和中间代码生成,S,输出为:,输入是bR / bTc / bSc /ac,给出相应语义动作(翻译方案), print “1”, print “2”, print “3”, print “4”, print “5”,第7章 语法制导翻译技术和中间代码生成,S,例2 简单算术表达式求值的语义描述,例如，设有简单算术表达式的文法：,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,第7章 语法制导翻译技术和中间代码生成,例3 简单算术表达式翻译到四元式的 语义描述,例如，设有简单算术表达式的文法：,EEE | E*E | (E) | i,第7章 语法制导翻译技术和中间代码生成,E EEE*E(E) | i,源结构,目标结构,（1）T1a*b,（2）T2c*d,（3）T3T1T2,a*bc*d,第7章 语法制导翻译技术和中间代码生成,语义函数 emit（Tar