编译原理中间代码生成7.ppt
《编译原理中间代码生成7.ppt》由会员分享,可在线阅读,更多相关《编译原理中间代码生成7.ppt(85页珍藏版)》请在三一文库上搜索。
1、第七章 中间代码生成,本章内容 介绍几种常用的中间表示:后缀表示、图形表示和三地址代码 用语法制导定义和翻译方案的方法来说明源语言的各种构造怎样被翻译成中间形式,7.1 中 间 语 言,7.1.1 后缀表示 表达式E的后缀表示可以如下归纳定义 如果E是变量或常数,那么E的后缀表示就是E本身,7.1 中 间 语 言,7.1.1 后缀表示 表达式E的后缀表示可以如下归纳定义 如果E是变量或常数,那么E的后缀表示就是E本身 如果E是形式为E1 opE2的表达式,那么E的后缀表示是E1 E2 op,其中E1和E2分别是E1和E2的后缀表示,7.1 中 间 语 言,7.1.1 后缀表示 表达式E的后缀表
2、示可以如下归纳定义 如果E是变量或常数,那么E的后缀表示就是E本身 如果E是形式为E1 opE2的表达式,那么E的后缀表示是E1 E2 op,其中E1和E2分别是E1和E2的后缀表示 如果E是形式为(E1)的表达式,那么E1的后缀表示也是E的后缀表示,7.1 中 间 语 言,后缀表示不需要括号 (8 4) + 2 的后缀表示是8 4 2 +,7.1 中 间 语 言,后缀表示不需要括号 (8 4) + 2 的后缀表示是8 4 2 + 后缀表示的最大优点是便于计算机处理表达式,7.1 中 间 语 言,后缀表示不需要括号 (8 4) + 2 的后缀表示是8 4 2 + 后缀表示的最大优点是便于计算机
3、处理表达式 后缀表示很容易拓广到含一元算符的表达式,7.1 中 间 语 言,后缀表示不需要括号 (8 4) + 2 的后缀表示是8 4 2 + 后缀表示的最大优点是便于计算机处理表达式 后缀表示很容易拓广到含一元算符的表达式 后缀表示也可以拓广到表示赋值语句和控制语句,但很难用栈来描述它的计算,7.1 中 间 语 言,7.1.2 图形表示 语法树是一种图形化的中间表示,7.1 中 间 语 言,7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示,7.1 中 间 语 言,构造赋值语句语法树的语法制导定义,7.1 中 间 语 言,7.1.3 三地址代码 一般形式:x =
4、y op z 表达式x + y z翻译成的三地址语句序列是 t1 = y z t2 = x + t1,7.1 中 间 语 言,三地址代码是语法树或dag的一种线性表示 a = (b + cd ) + cd 语法树的代码 t1 = b t2 = c d t3 = t1 + t2 t4 = c d t5 = t3 + t4 a = t5,7.1 中 间 语 言,三地址代码是语法树或dag的一种线性表示 a = (b + cd ) + cd 语法树的代码 dag的代码 t1 = b t1 = b t2 = c d t2 = c d t3 = t1 + t2 t3 = t1 + t2 t4 = c d
5、 t4 = t3 + t2 t5 = t3 + t4 a = t4 a = t5,7.1 中 间 语 言,本书常用的三地址语句 赋值语句x = y op z, x = op y, x = y 无条件转移goto L 条件转移if x relop y goto L 过程调用param x 和call p , n 过程返回 return y 索引赋值x = yi和 xi = y 地址和指针赋值x = &y,x = y和x = y,7.1 中 间 语 言,7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 三地址代码 静态单赋值
6、形式 p = a +b p1 = a +b q = p c q1 = p1 c p = q d p2 = q1 d p = e p p3 = e p2 q = p + q q2 = p3 + q1,7.1 中 间 语 言,7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 一个变量在不同路径上都定值的解决办法 if (flag) x = 1; else x = 1; y = x a; 的条件语句改成 if (flag) x1 = 1; else x2 = 1; x3 = (x1, x2); /由flag的值决定用x1还是x
7、2,7.2 声 明 语 句,为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息,7.2 声 明 语 句,7.2.1 过程中的声明,7.2 声 明 语 句,计算被声明名字的类型和相对地址 P offset = 0 D; S D D ; D D 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 nu
8、m of T1 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; S D D ; D | id : T | proc id ; D ; S 语义动作用到的函数 mkTable(previous) enter(table, name, type, offset) addWidth(table, width) enterProc(table, name,
9、 newtable),7.2 声 明 语 句,P M D; S addWidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) M t = mkTable (nil); push(t, tblprt); push (0, offset) D D1 ; D2 D proc id ; N D1; S t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) Did :T ent
10、er(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 record D end T record L D end T.type = record (top(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) L t =
11、 mkTable(nil); push(t, tblprt); push(0, offset) ,7.3 赋 值 语 句,7.3.1 符号表的中名字 S id := E p = lookup(id.lexeme); if p != nil then emit ( p, =, E.place) else error 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, =,
12、 uminus, E1.place) E (E1) E.place = E1.place E id p = lookup(id.lexeme); if p != nil then E.place = p else error ,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: array1
13、2, 13 of T 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3,7.3 赋 值 语 句,二维数组A: array12, 13 of T 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主 A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3,7.3 赋 值 语 句,二维数组A: array12, 13 of T 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主 A1, 1, A1, 2, A1, 3, A2, 1, A2, 2
14、, A2, 3 base + ( (i1 low1) n2 + (i2 low2 ) ) w (其中n2 = high2 low2 + 1),7.3 赋 值 语 句,二维数组A: array12, 13 of T 列为主 A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主 A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3 base + ( (i1 low1) n2 + (i2 low2 ) ) w (其中n2 = high2 low2 + 1) ( (i1 n2 ) + i2 ) w + (base ( (low1 n2 )
15、 + low2 ) w),7.3 赋 值 语 句,多维数组下标变量Ai1, 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 | id Elist Elist, E | E 改成 L Elist | id Elist Elist, E | id E,7.3 赋 值 语 句,所有产生式 S L := E E
16、E + E E (E ) E L L Elist L id Elist Elist, E Elist 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
17、 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.offs
18、et = 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 = newTe
19、mp(); emit (L.place, =, base(Elist.array), , invariant (Elist.array) ); L.offset = newTemp(); emit (L.offset, =, Elist.place,width(Elist.array),7.3 赋 值 语 句,E Lif L.offset = null then / L是简单变量 / E.place = L.place else begin E.place = newTemp(); emit (E.place, =, L.place, , L.offset, ) end ,7.3 赋 值 语
20、句,E Lif L.offset = null then / L是简单变量 / E.place = L.place else begin E.place = newTemp(); emit (E.place, =, L.place, , L.offset, ) end E E1 + E2E.place = newTemp(); emit (E.place, =, E1.place , +, E2.place) ,7.3 赋 值 语 句,E Lif L.offset = null then / L是简单变量 / E.place = L.place else begin E.place = new
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 中间 代码 生成
链接地址:https://www.31doc.com/p-4156955.html