第七章 中间代码生成 静态 中间 分析 检查 代码 记号流 器 生成 本章内容 介绍几种常用的中间表示:后缀表示、图形表示和三地址代码 第七章 中间代码生成 本章内容 介绍几种常用的中间表示:后缀表示、图形表示和三地址代码 用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 分析 器 静态 检查 中间 代码 生成 记号流
7.1 中 间 语 言 7.1.1 后缀表示 E E opE | uopE | (E) | id | num 7.1 中 间 语 言 7.1.1 后缀表示 E E opE | uopE | (E) | id | num 表达式E的后缀表示可以如下归纳定义: 表达式E 后缀式E id id num num E1 opE2 E1 E2 op uopE Euop (E) E
7.1 中 间 语 言 后缀表示不需要括号 (8 5) + 2 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 7.1 中 间 语 言 后缀表示不需要括号 (8 5) + 2 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 计算栈 输入串 8 5 2 + 8 5 2 + 8 5 2 + 3 2 + 3 2 + 5
7.1 中 间 语 言 后缀表示不需要括号 (8 5) + 2 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 7.1 中 间 语 言 后缀表示不需要括号 (8 5) + 2 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 后缀表示也可以拓广到表示赋值语句和控制语句,但很难用栈来描述控制语句的计算
7.1 中 间 语 言 7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示 assign a + b c d 7.1 中 间 语 言 7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示 assign a + b c d uminus (a) 语法树 a = (b + cd) + cd的图形表示 assign a + b c d uminus (b) DAG
7.1 中 间 语 言 构造赋值语句语法树的语法制导定义 修改构造结点的函数可生成有向无环图 产 生 式 语 义 规 则 S id =E 7.1 中 间 语 言 构造赋值语句语法树的语法制导定义 修改构造结点的函数可生成有向无环图 产 生 式 语 义 规 则 S id =E S.nptr = mkNode(‘assign’, mkLeaf (id, id.entry), E.nptr) E E1 +E2 E.nptr = mkNode( ‘+’, E1.nptr, E2.nptr) E E1 E2 E.nptr = mkNode( ‘’, E1.nptr, E2.nptr) E E1 E.nptr = mkUNode( ‘uminus’, E1.nptr) E (E1) E.nptr = E1.nptr F id E.nptr = mkLeaf (id, id.entry)
7.1 中 间 语 言 7.1.3 三地址代码 一般形式:x = y op z 例 表达式x + y z翻译成的三地址语句序列是 7.1 中 间 语 言 7.1.3 三地址代码 一般形式:x = y op z 例 表达式x + y z翻译成的三地址语句序列是 t1 = y z t2 = x + t1
7.1 中 间 语 言 三地址代码是语法树或DAG的一种线性表示 例 a = (b + cd ) + cd 语法树的代码 7.1 中 间 语 言 三地址代码是语法树或DAG的一种线性表示 例 a = (b + cd ) + cd 语法树的代码 t1 = b t2 = c d t3 = t1 + t2 t4 = c d t5 = t3 + t4 a = t5 assign a + b c d uminus
7.1 中 间 语 言 三地址代码是语法树或DAG的一种线性表示 例 a = (b + cd ) + cd 语法树的代码 DAG的代码 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 t4 = t3 + t2 t5 = t3 + t4 a = t4 a = t5 assign a + b c d uminus
7.1 中 间 语 言 本书常用的三地址语句 赋值语句x = y op z, x = op y, x = y 无条件转移goto L 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 = y[i]和 x[i] = y 地址和指针赋值x = &y,x = y和x = y
7.1 中 间 语 言 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 7.1 中 间 语 言 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 三地址代码 静态单赋值形式 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 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 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还是x2
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 [ num ] 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 声 明 语 句 计算被声明名字的类型和相对地址 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 [ num ] 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 sort var a:…; x:…; D D ; D | id : T | proc id ; D ; S sort var a:…; x:…; readarray var i:…; exchange quicksort var k, v:…; partition var i, j:…; 图6.14的程序 参数被略去
7.2 声 明 语 句 符号表实例 sort sort 空 表 头 readarray a exchange quicksort x partition v k i 指向exchange sort readarray exchange quicksort partition 符号表实例
7.2 声 明 语 句 符号表的特点 语义动作用到的函数 sort 各过程有各自的符号表 var a:…; x:…; readarray 符号表之间有双向链 构造符号表时需要符号表栈 构造符号表需要活动记录栈 语义动作用到的函数 mkTable(previous) enter(table, name, type, offset) addWidth(table, width) enterProc(table, name, newtable) sort var a:…; x:…; readarray var i:…; exchange quicksort var k, v:…; partition var i, j:…; 图6.14的程序 参数被略去
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 {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 声 明 语 句 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 {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 声 明 语 句 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 {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.3 记录的域名 T record D end 记录类型单独建符号表,作为类型表达式的 主要部分,域的相对地址从0开始 T record L D end {T.type = record (top(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) } L {t = mkTable(nil); push(t, tblprt); push(0, offset) } record a :…; r : record i :…; . . . end; k : …; end
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, ‘=’, ‘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 变换成 i w + (base low w) 减少了运行时的计算
7.3 赋 值 语 句 二维数组 A: array[1..2, 1..3] of T A[1,1] A[1,2] A[1,3] 列为主 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] of T i2 A[1,1] A[1,2] … … … … 二维数组 A: array[1..2, 1..3] of T 列为主 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 (A[i1, i2]的地址,其中n2 = high2 low2 + 1) 变换成 ( (i1 n2 ) + i2 ) w + (base ( (low1 n2 ) + low2 ) w) i1
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 ] | id Elist Elist, E | E 不便于在处理下标表达式时到符号表取信息 为便于写语义动作,改成等价的 L Elist ] | id Elist Elist, E | id [E
7.3 赋 值 语 句 所有产生式 S L := E E 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 } 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{if L.offset == null then / L是简单变量 / E.place = L.place else begin E.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 {if L.offset == null then / L是简单变量 / emit (L.place, ‘= ’, E.place) else emit (L.place , ‘[’, L.offset, ‘]’, ‘=’, E.place) }
7.3 赋 值 语 句 A[10, 20] S := L.place = x L.offset = null x E.place = t4 L.place = t2 L.offset = t3 Elist.place = t1 Elist.ndim = 2 Elist.array = A , Elist.place = y Elist.ndim = 1 E.place = z L.place = z E.place = y L.place = y A [ z ] y x := A[ y, z ]的注释分析树 x = t4 t4 = t2 [t3 ] t2 = c t3 = 4 t1 t1 = y 20 t1 = t1 + z 注:c =A 84 A[10, 20]
7.3 赋 值 语 句 7.3.4 类型转换 例 x = y + i j (x和y的类型是real,i和j的类型是integer) 中间代码 t1 = i int j t2 = inttoreal t1 t3 = y real+ t2 x = t3
7.3 赋 值 语 句 E E1 + E2 E.place = newTemp(); if E1.type == integer && E2.type == integer then begin emit (E.place, ‘=’, E1.place, ‘int+’, E2.place); E.type = integer end else if E1.type == integer && E2.type == real then begin u = newTemp(); emit (u, ‘=’, ‘inttoreal’, E1.place); emit (E.place, ‘=’, u, ‘real+’, E2.place); E.type = real . . .
7.4 布尔表达式和控制流语句 7.4.1 布尔表达式 布尔表达式有两个基本目的 本节所用的布尔表达式文法 计算逻辑值 在控制流语句中用作条件表达式 本节所用的布尔表达式文法 B B or B | B and B | not B | ( B ) | E relop E | true | false
7.4 布尔表达式和控制流语句 7.4.1 布尔表达式 布尔表达式的完全计算 布尔表达式的“短路”计算 值的表示数值化 其计算类似于算术表达式的计算 布尔表达式的“短路”计算 B1 or B2 定义成 if B1 then true else B2 B1 and B2 定义成 if B1 then B2 else false 用控制流来实现计算,即用程序中的位置来表示值,因为布尔表达式通常用来决定控制流走向 两种不同计算方式会导致程序的结果不一样
7.4 布尔表达式和控制流语句 7.4.2 控制流语句的翻译 S if B then S1 | if B then S1 else S2 | while B do S1 | S1; S2
7.4 布尔表达式和控制流语句 指向B.true B.code 指向B.false B.true: S1.code . . . (a) if-then B.false: goto S.next S2.code (b) if-then-else goto S.begin S.begin: (c) while-do S1.next: (d) S1; S2
7.4 布尔表达式和控制流语句 If-then若改成下面形式,会产生冗余跳转指令 指向B.true B.code 指向B.false S1.code B.true: . . . 指向B.true 指向B.false B.false: goto S.next S2.code (b) if-then-else (a) if-then goto S.begin S.begin: (c) while-do S1.next: (d) S1; S2
7.4 布尔表达式和控制流语句 S if B then S1 {B.true = newLabel(); B.false = S.next; S1.next = S.next; S.code = B.code || gen(B.true, ‘:’) || S1.code } B.code S1.code B.true: . . . 指向B.true 指向B.false (a) if-then
7.4 布尔表达式和控制流语句 S if B then S1 else S2 {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} B.code S1.code B.true: . . . 指向B.true 指向B.false B.false: goto S.next S2.code (b) if-then-else
7.4 布尔表达式和控制流语句 S while B do S1 {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) } B.code S1.code B.true: . . . 指向B.true 指向B.false goto S.begin S.begin: (c) while-do
7.4 布尔表达式和控制流语句 S S1; S2 {S1.next = newLabel(); S2.next = S.next; S.code = S1.code || gen(S1.next, ‘:’) || S2.code } S1.code S2.code S1.next: . . . (d) S1; S2
7.4 布尔表达式和控制流语句 7.4.3 布尔表达式的控制流翻译 如果B是a < b的形式, 那么代码是: if a < b goto B.true goto B.false
7.4 布尔表达式和控制流语句 例 表达式 a < b or c < d and e < f 的代码是: 例 表达式 a < b or c < d and e < f 的代码是: if a < b goto Ltrue goto L1 L1: if c < d goto L2 goto Lfalse L2: if e < f goto Ltrue
7.4 布尔表达式和控制流语句 B B1 or B2 {B1.true = B.true; B1.false = newLabel(); B2.false = B.false; B.code = B1.code || gen(B1.false, ‘:’) || B2.code } B not B1 {B1.true = B.false; B1.false = B.true; B.code = B1.code }
7.4 布尔表达式和控制流语句 B B1 and B2 {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; B.code = B1.code }
7.4 布尔表达式和控制流语句 B E1 relop E2 {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 开关语句的翻译 switch E begin case V1: S1 case V2: S2 . . . case Vn - 1: Sn – 1 default: Sn end
7.4 布尔表达式和控制流语句 分支数较少时 t = E的代码 | Ln-2: if t != Vn-1 goto Ln-1 if t != V1 goto L1 | Sn -1的代码 S1的代码 | goto next goto next | Ln-1: Sn的代码 L1: if t != V2 goto L2 | next: S2的代码 goto next L2: . . . . . .
7.4 布尔表达式和控制流语句 分支较多时,将分支测试代码集中在一起,便于生成较好的分支测试代码 t = E的代码 | Ln: Sn的代码 goto test | goto next L1: S1的代码 |test: if t == V1 goto L1 goto next | if t == V2 goto L2 L2: S2的代码 | . . . goto next | if t == Vn-1 goto Ln-1 . . . | goto Ln Ln-1: Sn -1的代码 | next: goto next
7.4 布尔表达式和控制流语句 中间代码增加一种case语句,便于代码生成器对它进行特别处理 test: case V1 L1 . . . case Vn-1 Ln-1 case t Ln next: 一个生成: 用二分查找确定该执行的分支 直接找到该执行的分支 的例子见第244页习题 8.8
7.4 布尔表达式和控制流语句 7.4.5 过程调用的翻译 S call id (Elist) Elist Elist, E
7.4 布尔表达式和控制流语句 过程调用id(E1, E2, …, En)的中间代码结构 E1.place = E1的代码 . . . En.place = En的代码 param E1.place param E2.place param En.place call id.place, n
7.4 布尔表达式和控制流语句 S call id (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语句 for v := initial to final do stmt 例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 定义成和下面的代码序列有同样的含义: begin t1 := initial; t2 := final; if t1<= t2 then begin v := t1; stmt; while v <> t2 do begin v := succ(v); stmt end
例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 能否定义成和下面的代码序列有同样的含义? begin t1 := initial; t2 := final; v := t1; while v <= t2 do begin stmt; v := succ(v) end
例 题 1 Pascal语言for语句 for v := initial to final do stmt 的中间代码结构如下: 例 题 1 Pascal语言for语句 for v := initial to final do stmt 的中间代码结构如下: t1 = initial t2 = final if t1 > t2 goto L1 v = t1 L2: stmt if v == t2 goto L1 v = v + 1 goto L2 L1:
例 题 2 C语言的for语句有下列形式 for (e1;e2;e3) stmt 它和 e1; while (e2)do begin 例 题 2 C语言的for语句有下列形式 for (e1;e2;e3) stmt 它和 e1; while (e2)do begin stmt; e3; end 有同样的语义
例 题 2 C语言的for语句for (e1;e2;e3) stmt的中间代码 结构如下 e1的代码 L1: e2的代码 L2: e3的代码 例 题 2 C语言的for语句for (e1;e2;e3) stmt的中间代码 结构如下 e1的代码 L1: e2的代码 L2: e3的代码 goto L1 stmt的代码 goto L2 真转 假转,由外层语句决定
例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 若a和b是同一类型记录,也允许 C语言 数组类型不行,结构体类型可以 为这种赋值选用或设计一种三地址语句,它要便于生成目标代码
例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 若a和b是同一类型记录,也允许 仍然用中间代码复写语句 x = y,在生成目标代码时,必须根据它们类型的size,产生一连串的值传送指令
例 题 4 下面的翻译方案使用了变量offset,请重写该翻译方案,它完成同样的事情,但只使用文法符号的属性,而不使用变量offset 例 题 4 下面的翻译方案使用了变量offset,请重写该翻译方案,它完成同样的事情,但只使用文法符号的属性,而不使用变量offset P {offset = 0} D 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 }
例 题 4 P {D.offset1 = 0} D { P.offset = D.offset2} 例 题 4 P {D.offset1 = 0} D { P.offset = D.offset2} D {D1.offset1 = D.offset1 } D1 ; {D2.offset1 = D1.offset2 }D2 {D.offset2 = D2.offset2 } D id :T{enter ( id.lexeme, T.type, D.offset1); D.offset2 = D.offset1 + T.width } T integer {T.type = integer; T.width = 4 } T real {T.type = real; T.width = 8 }
习 题 第一次:7.1 第二次:7.4, 7.8, 7.10 68