《编译原理第八章—中间代码生成》由会员分享，可在线阅读，更多相关《编译原理第八章—中间代码生成（107页珍藏版）》请在金锄头文库上搜索。
1、第8章 语法制导翻译和 中间代码生成数计学院宋彩芳培训笔记l义务教育使我们睁开眼，高等教育使我们站起来；l精神自由和教学秩序l有考试无文法，靠记忆力被动接受知识永远不是自 己的；不会学习也是文盲；l教育是影响，是引发，是心灵之约；主要内容l属性文法l语法制导翻译概论l计算语义规则lS-属性文法和自下而上翻译lL-属性文法和自上而下翻译l中间代码的形式l简单赋值语句的翻译l布尔表达式的翻译l控制结构的翻译l说明语句的翻译l数组和结构的翻译主要内容l中间代码的形式l简单赋值语句的翻译l布尔表达式的翻译l控制结构的翻译l说明语句的翻译l数组和结构的翻译中间代码的形式l编译器各阶段的完整输出，均可以被
2、认为是源程序的某 种中间表示。l编译器前端l词法分析记号流l语法分析语法树l语义分析中间代码l本章讨论的是中间代码生成器输出的中间表示，称之为 中间代码。l中间代码实际上应起一个编译器前端与后端分水岭的作 用。l生成中间代码的好处：l再目标比较容易l独立于机器的优化可用于这种中间代码中间代码的形式l介绍几种常用的中间表示：l逆波兰记号（后缀表示）l三元式和树形表示l四元式语法 分析 器静态 检查 器中间 代码 生成 器中间 代码记号 流代码 生成 器中间代码的形式逆波兰记号（ 后缀表示）l表达式E的后缀表示可以如下归纳定义l如果E是变量或常数，那么E的后缀表示就是E本身。l如果E是形式为E1
3、opE2的表达式，那么E的后缀表示是E1 E2 op，其中E1和E2分别是E1和E2的后缀表示。l如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的 后缀表示。 中间代码的形式l后缀表示不需要括号l(8 4) + 2 的后缀表示是8 4 2 + l后缀表示很容易拓广到含一元算符的表达式 l后缀表示也可以拓广到表示赋值语句和控制语句， 但很难用栈来描述它的计算中间代码的形式l后缀式的特点：l操作符在前，操作数紧随其后，无需用括号限制运算的 优先级和结合性。l后缀表示的最大优点是便于计算机处理表达式l利用一个栈，自左向右地扫描表达式的后缀表示，遇到 运算对象，进栈；遇到运算符，出栈相应个数
4、的运算对 象计算，并将结果进栈。中间代码的形式l计算后缀式的虚拟机l输入 后缀式l输出 计算结果l方法 采用下述过程进行计算，最终结果留在栈中。 x = first_token; while(!end_of_exp )if (x in operators)push x; - 操作数进栈else pop(operators); - 算符，弹出操作数push(evaluate); - 计算，并将结果进栈next(x); 中间代码的形式l后缀式计算l算术表达式3+5+8的后缀式为35+8+。 （#35+8+#进栈） （#3 5+8+#进栈） （#35 +8+#弹出3和5，计算3+5，结果进栈） （#
5、8 8+#进栈） （#88 +#弹出8和8，计算8+8，结果进栈） （#16 # ）中间代码的形式l将后缀式推广到其他语句l后缀式并不局限于二元运算的表达式，可以推广到任何语句，只 要遵守操作数在前，操作符紧跟其后的原则即可。l语句：if e then x else y 它的后缀式可以写为： e x y if-then-else(1) 上述表示中，e、x和y均需计算。 而实际上，根据条件e的取值，x和y不能都计算： e p1 jez x p2 jump p1: y p2:(2) 其中：lp1和p2分别是标号；lp1 jez表示e的结果为0（假）则转向p1；lp2 jump表示无条件转向p2。l
6、与 (1)比较，(2)中的if-then-else被分解，首先计算e，根据e的 结果是否为真，决定计算x还是计算y。三元式和树形表示三元式主要由三部分组成： （OP，arg1, arg2 ） 其中OP是运算符 ， arg1,arg2分别是第一和第二两个运算对象 。 当OP是一目运算时，常常将运算对象定 义为arg1。 中间代码的形式例如 a+b*c 的 三元式序列：(1) ( * , b , c )(2) ( + , a , (1) )运算对象是指向符号表的某一项或指向 三元式表的某一项。 中间代码的形式1. 三元式出现的顺序和语法成份的 计值顺序相一致。 三元式的特点：2. 三元式之间的联系
7、是通过指示器实现的。 中间代码的形式树形表示 A * B + C*D +C*A*BD末端结点表示一个运算对象, 每一个 内结点表示一个一元或二元运算符。树形表示是三元式的翻版 (3)+(1)*(2)*CABD中间代码的形式四元式主要由四部分组成： （OP，arg1, arg2, result ） 其中OP是运算符， arg1,arg2分别是第一和第二两个运算对象。 当OP是一目运算时，常常将运算对象定义 为arg1。 中间代码的形式四元式的第四个分量result是编译程序 为存放中间运算结果而临时引进的变量 ，常称为临时变量，如Ti，也可以是用 户自定义变量，如X。 例如 X a*bc/d 的
8、 四元式序列 ：(1) ( *, a, b, T1 ) (2) ( /, c, d, T2 ) (3) ( +, T1, T2, T3 )(4) ( =, T3, -, X )中间代码的形式2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。 1. 四元式出现的顺序和语法成份的计值 顺序相一致。 四元式的特点：3. 便于优化处理。 中间代码的形式编译系统中，有时将四元式表示成另一 种更直观，更易理解的形式三地址代 码或三地址语句。result : arg1 OP arg2三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。 三地址代码形式定义为：中间代码的形式例如 X
9、 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 中间代码的形式例1. a + b * ( c + d )的逆波兰式 a bc d + * +中间代码的形式t1= at2= ct3= t2 + dt5= t1+ t4a + b * ( c + d )的四元式表示t4= b* t3 中间代码的形式i( i /( i i ) )的逆波兰式 i( i /( i i
10、 ) )的四元式t1= i it2= i / t1 t3= i t2i i i i /例2. 中间代码的形式中间代码的形式l介绍几种常用的中间表示：l逆波兰记号（后缀表示）l三元式和树形表示l四元式语法 分析 器静态 检查 器中间 代码 生成 器中间 代码记号 流代码 生成 器中间代码的形式l(jump,-,-,L)可简写为goto Ll(jrop,B,C,L)可简写为if B rop C goto Ll(case, V,L,-)各种语句的翻译l思考问题:l描述文法,适当地改写文法;l生成的中间代码形式l翻译规则,含一定的语法规则;主要内容l中间代码的形式l简单赋值语句的翻译l布尔表达式的翻译
11、l控制结构的翻译l说明语句的翻译l数组和结构的翻译预备知识：符号表的中名字l在三地址代码中直接用名字表示运算对象l实际应该把名字理解为它们在符号表中的名字l编译器在处理表达式、赋值语句等构造中的名字 时，需在符号表中查找它的定义，获得它的属性 ，然后生成四元式中使用它在符号表中的位置指 针。符号表的中名字lid的属性lname：组成该名字的字符序列llookup（id.name）：根据名字查找符号表中是否存在 该名字的条目，有则返回指针，否则返回nillE的属性lplace：符号表条目的地址lnewTemp：产生一个新的临时变量的名字，并返回一 整数码；lemit函数：输出四元式到输出文件；简
12、单赋值语句的翻译l赋值语句文法：lEid := E lEE+E|E*E|-E|(E)|idl翻译内容：l中间代码生成（四元式）:l其他语法检查：l如先定义后使用：l类型检查：l检查标识符的种类（kind），判断是否为变量名；emit(t := arg1 op arg2);E1.type=int AND E2.type=intp = lookup(id.name) ;产生式和语义描述： (1) S id := E P:=lookup (id.name) ;if P nil then emit( P“ :=” E.place)else error 简单赋值语句的翻译(2) EE1+E2 E.pla
13、ce:= newtemp;emit(E.place“:=” E1.place“+”E2.place) (3) EE1*E2 E.place:= newtemp;emit(E.place“:=” E1.place“*”E2.place) (4) E - E1 E.place:=newtemp;emit(E.place“:=”“uminus” E1.place) (5) E( E1) E.place:= E1.place (6) Eid E.place:=newtemp; P:=lookup(id.name);if Pnil then E.place:=Pelse error简单赋值语句的翻译简单
14、赋值语句的翻译l增加类型检查的赋值语句的翻译lEE1*E2 lE.place:= newtemp;lif E1.type=int AND E2.type=int then l begin emit(E.place“:=” E1.place“*”E2.place)l E.type := int l endllelse l begin t:= newtempl emit(t, “:=” ,“itr”,E2.place)l emit(E.place“:=” E1.place“*”t)l E.type := reall end主要内容l中间代码的形式l简单赋值语句的翻译l布尔表达式的翻译l控制结构的翻
15、译l说明语句的翻译l数组和结构的翻译布尔表达式l布尔表达式有两个基本目的l计算逻辑值 如：x=a or bl在控制流语句中用作条件表达式 如if C then .，while C do .等l本节所用的布尔表达式文法lE E or E | E and E | not E | ( E )| id rop id | true | falsel布尔运算的优先级与结合性（从高到低）：lnot and or 例如： a*by or not z 等价于： (a*b)y) or (not z)布尔表达式l布尔表达式的完全计算（数值表示的直接计算）(举例)l值的表示数值化，其计算类似于算术表达式的计算l1表示true， 0表示false。lor、and、not与
