编译原理中间代码生成7.ppt

第七章中间代码生成 本章内容介绍几种常用的中间表示 后缀表示 图形表示和三地址代码用语法制导定义和翻译方案的方法来说明源语言的各种构造怎样被翻译成中间形式 7 1中间语言 7 1 1后缀表示表达式e的后缀表示可以如下归纳定义如果e是变量或常数 那么e的后缀表示就是e本身 7 1中间语言 7 1 1后缀表示表达式e的后缀表示可以如下归纳定义如果e是变量或常数 那么e的后缀表示就是e本身如果e是形式为e1ope2的表达式 那么e的后缀表示是e1 e2 op 其中e1 和e2 分别是e1和e2的后缀表示 7 1中间语言 7 1 1后缀表示表达式e的后缀表示可以如下归纳定义如果e是变量或常数 那么e的后缀表示就是e本身如果e是形式为e1ope2的表达式 那么e的后缀表示是e1 e2 op 其中e1 和e2 分别是e1和e2的后缀表示如果e是形式为 e1 的表达式 那么e1的后缀表示也是e的后缀表示 7 1中间语言 后缀表示不需要括号 8 4 2的后缀表示是84 2 7 1中间语言 后缀表示不需要括号 8 4 2的后缀表示是84 2 后缀表示的最大优点是便于计算机处理表达式 7 1中间语言 后缀表示不需要括号 8 4 2的后缀表示是84 2 后缀表示的最大优点是便于计算机处理表达式后缀表示很容易拓广到含一元算符的表达式 7 1中间语言 后缀表示不需要括号 8 4 2的后缀表示是84 2 后缀表示的最大优点是便于计算机处理表达式后缀表示很容易拓广到含一元算符的表达式后缀表示也可以拓广到表示赋值语句和控制语句 但很难用栈来描述它的计算 7 1中间语言 7 1 2图形表示语法树是一种图形化的中间表示 7 1中间语言 7 1 2图形表示语法树是一种图形化的中间表示有向无环图也是一种中间表示 7 1中间语言 构造赋值语句语法树的语法制导定义 7 1中间语言 7 1 3三地址代码一般形式 x yopz表达式x y z翻译成的三地址语句序列是t1 y zt2 x t1 7 1中间语言 三地址代码是语法树或dag的一种线性表示a b c d c d语法树的代码t1 bt2 c dt3 t1 t2t4 c dt5 t3 t4a t5 7 1中间语言 三地址代码是语法树或dag的一种线性表示a b c d c d语法树的代码dag的代码t1 bt1 bt2 c dt2 c dt3 t1 t2t3 t1 t2t4 c dt4 t3 t2t5 t3 t4a t4a t5 7 1中间语言 本书常用的三地址语句赋值语句x yopz x opy x y无条件转移gotol条件转移ifxrelopygotol过程调用paramx和callp n过程返回returny索引赋值x y i 和x i y地址和指针赋值x y x y和 x y 7 1中间语言 7 1 4静态单赋值形式一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量的赋值三地址代码静态单赋值形式p a bp1 a bq p cq1 p1 cp q dp2 q1 dp e pp3 e p2q p qq2 p3 q1 7 1中间语言 7 1 4静态单赋值形式一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量的赋值一个变量在不同路径上都定值的解决办法if flag x 1 elsex 1 y x a 的条件语句改成if flag x1 1 elsex2 1 x3 x1 x2 由flag的值决定用x1还是x2 7 2声明语句 为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息 7 2声明语句 7 2 1过程中的声明 7 2声明语句 计算被声明名字的类型和相对地址p offset 0 d sd d dd id t enter id lexeme t type offset offset offset t width t integer t type integer t width 4 t real t type real t width 8 t array num oft1 t type array num val t1 type t width num val t1 width t t1 t type pointer t1 type t width 4 7 2声明语句 7 2 2作用域信息的保存所讨论语言的文法p d sd d d id t procid d s语义动作用到的函数mktable previous enter table name type offset addwidth table width enterproc table name newtable 7 2声明语句 p md s addwidth top tblptr top offset pop tblptr pop offset m t mktable nil push t tblprt push 0 offset d d1 d2d procid nd1 s t top tblptr addwidth t top offset pop tblptr pop offset enterproc top tblptr id lexeme t d id t enter top tblptr id lexeme t type top offset top offset top offset t width n t mktable top tblptr push t tblptr push 0 offset 7 2声明语句 7 2声明语句 7 2 3记录的域名t recorddendt recordldend t type record top tblptr t width top offset pop tblptr pop offset l t mktable nil push t tblprt push 0 offset 7 3赋值语句 7 3 1符号表的中名字s id e p lookup id lexeme ifp nilthenemit p e place elseerror e e1 e2 e place newtemp emit e place e1 place e2 place 7 3赋值语句 7 3 1符号表的中名字e e1 e place newtemp emit e place uminus e1 place e e1 e place e1 place e id p lookup id lexeme ifp nilthene place pelseerror 7 3赋值语句 7 3 2数组元素的地址计算一维数组a的第i个元素的地址计算base i low w 7 3赋值语句 7 3 2数组元素的地址计算一维数组a的第i个元素的地址计算base i low w重写成i w base low w 减少了运行时的计算 7 3赋值语句 二维数组a array 1 2 1 3 oft列为主a 1 1 a 2 1 a 1 2 a 2 2 a 1 3 a 2 3 7 3赋值语句 二维数组a array 1 2 1 3 oft列为主a 1 1 a 2 1 a 1 2 a 2 2 a 1 3 a 2 3 行为主a 1 1 a 1 2 a 1 3 a 2 1 a 2 2 a 2 3 7 3赋值语句 二维数组a array 1 2 1 3 oft列为主a 1 1 a 2 1 a 1 2 a 2 2 a 1 3 a 2 3 行为主a 1 1 a 1 2 a 1 3 a 2 1 a 2 2 a 2 3 base i1 low1 n2 i2 low2 w 其中n2 high2 low2 1 7 3赋值语句 二维数组a array 1 2 1 3 oft列为主a 1 1 a 2 1 a 1 2 a 2 2 a 1 3 a 2 3 行为主a 1 1 a 1 2 a 1 3 a 2 1 a 2 2 a 2 3 base i1 low1 n2 i2 low2 w 其中n2 high2 low2 1 i1 n2 i2 w base low1 n2 low2 w 7 3赋值语句 多维数组下标变量a i1 i2 ik 的地址表达式 i1 n2 i2 n3 i3 nk ik w base low1 n2 low2 n3 low3 nk lowk w 7 3赋值语句 7 3 3数组元素地址计算的翻译方案下标变量访问的产生式l id elist idelist elist e e改成l elist idelist elist e id e 7 3赋值语句 所有产生式s l ee e ee e e ll elist l idelist elist eelist id e 7 3赋值语句 l id l place id place l offset null 7 3赋值语句 l id l place id place l offset null elist id e elist place e place elist ndim 1 elist array id place 7 3赋值语句 l id l place id place l offset null elist id e elist place e place elist ndim 1 elist array id place elist elist1 e t newtemp m elist1 ndim 1 emit t elist1 place limit elist1 array m emit t t e place elist array elist1 array elist place t elist ndim m 7 3赋值语句 l id l place id place l offset null elist id e elist place e place elist ndim 1 elist array id place elist elist1 e t newtemp m elist1 ndim 1 emit t elist1 place limit elist1 array m emit t t e place elist array elist1 array elist place t elist ndim m l elist l place newtemp emit l place base elist array invariant elist array l offset newtemp emit l offset elist place width elist array 7 3赋值语句 e l ifl offset nullthen l是简单变量 e place l placeelsebegine place newtemp emit e place l place l offset end 7 3赋值语句 e l ifl offset nullthen l是简单变量 e place l placeelsebegine place newtemp emit e place l place l offset end e e1 e2 e place newtemp emit e place e1 place e2 place 7 3赋值语句 e l ifl offset nullthen l是简单变量 e place l placeelsebegine place newtemp emit e place l place l offset end e e1 e2 e place newtemp emit e place e1 place e2 place e e1 e place e1 place 7 3赋值语句 e l ifl offset nullthen l是简单变量 e place l placeelsebegine place newtemp emit e place l place l offset end e e1 e2 e place newtemp emit e place e1 place e2 place e e1 e place e1 place s l e ifl offset nullthen l是简单变量 emit l place e place elseemit l place l offset e place 7 3赋值语句 7 3赋值语句 t1 y 20t1 t1 z 7 3赋值语句 t1 y 20t1 t1 z t2 a 84t3 4 t1 7 3赋值语句 t1 y 20t1 t1 z t2 a 84t3 4 t1 t4 t2 t3 7 3赋值语句 t1 y 20t1 t1 z t2 a 84t3 4 t1 t4 t2 t3 x t4 7 3赋值语句 7 3 4类型转换x y i j x和y的类型是real i和j的类型是integer 中间代码t1 iint jt2 inttorealt1t3 yreal t2x t3 7 3赋值语句 e e1 e2e place newtemp ife1 type integere type realend 7 4布尔表达式和控制流语句 7 4 1布尔表达式布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式本节所用的布尔表达式文法b borb bandb notb b erelope true false 7 4布尔表达式和控制流语句 7 4 1布尔表达式布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算值的表示数值化 其计算类似于算术表达式的计算 7 4布尔表达式和控制流语句 7 4 1布尔表达式布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算值的表示数值化 其计算类似于算术表达式的计算布尔表达式的 短路 计算b1orb2定义成ifb1thentrueelseb2b1andb2定义成ifb1thenb2elsefalse用控制流来实现 即用程序中的位置来表示值 7 4布尔表达式和控制流语句 7 4 2控制流语句的翻译s ifbthens1 ifbthens1elses2 whilebdos1 s1 s2 7 4布尔表达式和控制流语句 7 4布尔表达式和控制流语句 s ifbthens1 b true newlabel b false s next s1 next s next s code b code gen b true s1 code 7 4布尔表达式和控制流语句 s ifbthens1elses2 b true newlabel b false newlabel s1 next s next s2 next s next s code b code gen b true s1 code gen goto s next gen b false s2 code 7 4布尔表达式和控制流语句 s whilebdos1 s begin newlabel b true newlabel b false s next s1 next s begin s code gen s begin b code gen b true s1 code gen goto s begin 7 4布尔表达式和控制流语句 s s1 s2 s1 next newlabel s2 next s next s code s1 code gen s1 next s2 code 7 4布尔表达式和控制流语句 7 4 3布尔表达式的控制流翻译如果b是a b的形式 那么代码是 ifa bgotob truegotob false 7 4布尔表达式和控制流语句 表达式a borc dande f的代码是 ifa bgotoltruegotol1l1 ifc dgotol2gotolfalsel2 ife fgotoltruegotolfalse 7 4布尔表达式和控制流语句 b b1orb2 b1 true b true b1 false newlabel b2 true b true b2 false b false b code b1 code gen b1 false b2 code 7 4布尔表达式和控制流语句 b b1orb2 b1 true b true b1 false newlabel b2 true b true b2 false b false b code b1 code gen b1 false b2 code b notb1 b1 true b false b1 false b true b code b1 code 7 4布尔表达式和控制流语句 b b1andb2 b1 true newlabel b1 false b false b2 true b true b2 false b false b code b1 code gen b1 true b2 code 7 4布尔表达式和控制流语句 b b1andb2 b1 true newlabel b1 false b false b2 true b true b2 false b false b code b1 code gen b1 true b2 code b b1 b1 true b true b1 false b false b code b1 code 7 4布尔表达式和控制流语句 b e1relope2 b code e1 code e2 code gen if e1 place relop op e2 place goto b true gen goto b false 7 4布尔表达式和控制流语句 b e1relope2 b code e1 code e2 code gen if e1 place relop op e2 place goto b true gen goto b false b true b code gen goto b true b false b code gen goto b false 7 4布尔表达式和控制流语句 7 4 4开关语句的翻译switchebegincasev1 s1casev2 s2 casevn 1 sn 1default snend 7 4布尔表达式和控制流语句 分支数较少时t e的代码 ln 2 ift vn 1gotoln 1ift v1gotol1 sn 1的代码s1的代码 gotonextgotonext ln 1 sn的代码l1 ift v2gotol2 next s2的代码gotonextl2 7 4布尔表达式和控制流语句 分支较多时 将分支测试的代码集中在一起 便于生成较好的分支测试代码 t e的代码 ln sn的代码gototest gotonextl1 s1的代码 test ift v1gotol1gotonext ift v2gotol2l2 s2的代码 gotonext ift vn 1gotoln 1 gotolnln 1 sn 1的代码 next gotonext 7 4布尔表达式和控制流语句 中间代码增加一种case语句 便于代码生成器对它进行特别处理test casev1l1casev2l2 casevn 1ln 1casetlnnext 7 4布尔表达式和控制流语句 7 4 5过程调用的翻译s callid elist elist elist eelist e 7 4布尔表达式和控制流语句 过程调用id e1 e2 en 的中间代码结构e1 place e1的代码e2 place e2的代码 en place en的代码parame1 placeparame2 place paramen placecallid place n 7 4布尔表达式和控制流语句 s callid elist 为长度为n的队列中的每个e place emit param e place emit call id plase n elist elist e 把e place放入队列末尾 elist e 将队列初始化 并让它仅含e place 本章要点 中间代码的几种形式 它们之间的相互转换符号表的组织和作用域信息的保存数组元素定址的翻译方案 布尔表达式的两种不同实现方式赋值语句和各种控制流语句的中间代码格式和生成中间代码的翻译方案过程调用的中间代码格式和生成中间代码的翻译方案 例题1 pascal语言的标准将for语句forv initialtofinaldostmt定义成和下面的代码序列有同样的含义 begint1 initial t2 final ift1t2dobeginv succ v stmtendendend 例题1 pascal语言的标准将for语句forv initialtofinaldostmt能否定义成和下面的代码序列有同样的含义 begint1 initial t2 final v t1 whilev t2dobeginstmt v succ