编译原理与技术 第7章 中间代码生成 3学时.

Presentation on theme: "编译原理与技术 第7章 中间代码生成 3学时."— Presentation transcript:

1 编译原理与技术 第7章 中间代码生成 3学时

2 用语法制导定义和翻译方案来说明源语言的各种构造怎样被 翻译成中间形式 分析器 静态 检查器 中间 代码 生成器 记号流
7 中间代码生成 内容提要 介绍几种常用的中间表示： 后缀表示、图形表示和三地址代码 用语法制导定义和翻译方案来说明源语言的各种构造怎样被 翻译成中间形式 分析器 静态 检查器 中间 代码 生成器 记号流

3 第7章 中间代码生成 7.1 中间语言 0.5学时

4 E  E op E | uop E | (E) | id | num 表达式E的后缀表示可以如下归纳定义： 表达式E 后缀式E
7.1 中间语言 7.1.1 后缀表示 E  E op E | uop E | (E) | id | num 表达式E的后缀表示可以如下归纳定义： 表达式E 后缀式E id id num num E1 op E2 E1 E2 op uop E E uop (E) E

5 后缀表示的最大优点是便于计算机处理表达式 计算栈 输入串 8 5 - 2 + 8 5 - 2 + 8 5 - 2 + 3 2 + 3 2 +
7.1 中间语言 后缀表示不需要括号 (8 - 5) + 2 的后缀表示是 后缀表示的最大优点是便于计算机处理表达式 计算栈 输入串 3 2 + 3 2 + 5 后缀表示也可以拓广到表示赋值语句和控制语句，但很难用 栈来描述控制语句的计算

6 Directed Acyclical Graphs
7.1 中间语言 7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示 assign a +  b c d uminus (a) 语法树 assign a +  b c d uminus (b) DAG Directed Acyclical Graphs a = ( - b + c  d ) + c  d 的图形表示

7 S.nptr = mkNode( 'assign', mkLeaf (id, id.entry), E.nptr)
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)

8 例 表达式x + y  z翻译成的三地址语句序列是 t1 = y  z t2 = x + t1
7.1 中间语言 7.1.3 三地址代码 一般形式：x = y op z 例 表达式x + y  z翻译成的三地址语句序列是 t1 = y  z t2 = x + t1

9 三地址代码是语法树或DAG的一种线性表示 例 a = ( - b + c  d ) + c  d 语法树的代码 t1 = - b
7.1 中间语言 三地址代码是语法树或DAG的一种线性表示 例 a = ( - b + c  d ) + c  d 语法树的代码 t1 = - b t2 = c  d t3 = t1 + t2 t4 = c  d t5 = t3 + t4 a = t5 assign a +  b c d uminus DAG的代码 t1 = - b t2 = c  d t3 = t1 + t2 t4 = t3 + t2 a = t4 assign a +  b c d uminus

10 赋值语句 x = y op z， x = op y， x = y 无条件转移 goto L 条件转移 if x relop 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

11 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

12 x3 =  (x1, x2); //由flag的值决定用x1还是x2 y = x  x3;
7.1 中间语言 一个变量在不同路径上都定值的解决办法 if (flag) x = 1; else x = 1; y = x  a; 改成 if (flag) x1 = 1; else x2 = 1; x3 =  (x1, x2); //由flag的值决定用x1还是x2 y = x  x3;

13 第7章 中间代码生成 7.2 声明语句 0.5学时

14 符号表中包含名字的类型和分配给它的存储单元的相对地址 等信息
7.2 声明语句 本节介绍 为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址 等信息

15 7.2 声明语句 7.2.1 过程中的声明 计算被声明名字的类型和相对地址 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 }

16 7.2.2 作用域信息的保存 所讨论语言的文法 P  D; S D  D ; D | id : T | sort
7.2 声明语句 7.2.2 作用域信息的保存 所讨论语言的文法 P  D; S 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的程序参数被略去

17 exchange readarray x a 表 头 空 sort quicksort 指向readarray partition v k
7.2 声明语句 exchange readarray x a 表 头 空 sort quicksort 指向readarray partition v k i 指向exchange sort readarray exchange quicksort partition

18 mkTable(previous) //创立新表 enter(table, name, type, offset) //增加新的id条目
7.2 声明语句 符号表的特点 各过程有各自的符号表 符号表之间有双向链 构造符号表时需要符号表栈 构造符号表需要偏移记录栈 语义动作用到的函数 mkTable(previous) //创立新表 enter(table, name, type, offset) //增加新的id条目 addWidth(table, width) //将表大小写入表中 enterProc(table, name, newtable) //添加新的表条目

19 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) } 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) }

20 记录类型单独建符号表，作为类型表达式的主要部分，域的 相对地址从0开始
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

21 第7章 中间代码生成 7.3 赋值语句 0.5学时

22 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) } 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 }

23 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) 减少了运行时的计算

24 i2  i1 二维数组 A[1, 1] A[1, 2] A[1, 3] A: array[1..2, 1..3] of T
7.3 赋值语句 二维数组 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] A[i1, i2]的地址： base + ((i1-low1)n2 + (i2-low2 ))w (其中n2=high2-low2+1) 变换成 ((i1n2 )+i2)w + base-((low1n2)+low2)w A[1, 1] A[1, 2] A[1, 3] A[2, 1] A[2, 2] A[2, 3] i1 i2  A[1, 1] A[1, 2] … A[2, 1] A[2, 2] … … … …

25 多维数组下标变量A[i1, i2, ..., ik]的地址表达式 ( (… ( (i1n2+i2)n3+i3) … )nk+ik)w
7.3 赋值语句 多维数组下标变量A[i1, i2, ..., ik]的地址表达式 ( (… ( (i1n2+i2)n3+i3) … )nk+ik)w + base((…((low1n2+low2)n3+low3) … )nk+lowk)w

26 7.3.3 数组元素地址计算的翻译方案 下标变量访问的产生式 L  id [ Elist ] | id
7.3 赋值语句 7.3.3 数组元素地址计算的翻译方案 下标变量访问的产生式 L  id [ Elist ] | id Elist  Elist, E | E 不便于在处理下标表达式时到符号表取信息 为便于写语义动作，改成等价的 L  Elist ] | id Elist  Elist, E | id [E

27 所有产生式 S  L := E E  E + E E  (E ) E  L L  Elist ] L  id
7.3 赋值语句 所有产生式 S  L := E E  E + E E  (E ) E  L L  Elist ] L  id Elist  Elist, E Elist  id [ E

28 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)); }

29 7.3 赋值语句 E  L { if L.offset == null then / L是简单变量 / E.place = L.place; else { E.place = newTemp(); emit (E.place, '=', L.place, '[', L.offset, ']'); } } 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); }

30 S := L.place = x L.offset = null x E.place = t4 L.place = t2
7.3 赋值语句 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 ]的注释分析树 t4 = t2 [t3 ] x = t4 t2 = c t3 = t1  4 t1 = y  20 t1 = t1 + z 注：c =A  84 A[10, 20]

31 考虑C语言中数组double a[10][20]，写出计算a[i][j]、a[i]+1和a+i的三地址中间代码
7.3 赋值语句 例题 考虑C语言中数组double a[10][20]，写出计算a[i][j]、a[i]+1和a+i的三地址中间代码 a: pointer(array(20,double)) a[i]: pointer(double) a[i][j]: double a[i][j]: t1=i*20 t2=t1+j t3=t2*8 t4=a[t3] a[i]+1: t2=t1*8 t3=a+t2 t4=1*8 t5=t3+t4 a+i: t1=a t2=20*8 t3=t2*i t4=t1+t3

32 （x和y的类型是real，i和j的类型是integer）
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

33 7.3 赋值语句 E  E1 + E2 { E.place = newTemp(); if E1.type == integer && E2.type == integer then { emit (E.place, '=', E1.place, 'int+', E2.place); E.type = integer; } elseif E1.type == integer && E2.type == real then { u = newTemp(); emit (u, '=', 'inttoreal', E1.place); emit (E.place, '=', u, 'real+', E2.place); E.type = real; } . . .

34 第7章 中间代码生成 7.4 布尔表达式和控制流语句 1.5学时

35 B  B or B | B and B | not B | ( B ) | E relop E | true | false
7.4 布尔表达式和控制流语句 7.4.1 布尔表达式 布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 本节所用的布尔表达式文法 B  B or B | B and B | not B | ( B ) | E relop E | true | false

36 B1 or B2 定义成 if B1 then true else B2
7.4 布尔表达式和控制流语句 布尔表达式的完全计算 值的表示数值化 其计算类似于算术表达式的计算 布尔表达式的“短路”计算 B1 or B2 定义成 if B1 then true else B2 B1 and B2 定义成 if B1 then B2 else false 用控制流来实现计算，即用程序中的位置来表示值，因 为布尔表达式通常用来决定控制流走向 两种不同计算方式会导致程序的结果不一样

37 7.4.2 控制流语句的翻译 S  if B then S1 | if B then S1 else S2 | while B do S1
7.4 布尔表达式和控制流语句 7.4.2 控制流语句的翻译 S  if B then S1 | if B then S1 else S2 | while B do S1 | S1; S2

38 如果给If-then添加false标号，当它嵌入其它语句时，可能会产生冗余跳转指令
7.4 布尔表达式和控制流语句 如果给If-then添加false标号，当它嵌入其它语句时，可能会产生冗余跳转指令 B.code S1.code B.true: . . . 指向B.true 指向B.false (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 B.false:

39 S.code = B.code || gen(B.true, ':') || S1.code }
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

40 S.code = B.code || gen(B.true, ':') || S1.code ||
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

41 S.code = gen(S.begin, ':') || B.code || gen(B.true, ':') ||
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

42 { S1.next = newLabel(); S2.next = S.next;
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

43 如果B是 a < b 的形式，那么代码是： if a < b goto B.true goto B.false
7.4 布尔表达式和控制流语句 7.4.3 布尔表达式的控制流翻译 如果B是 a < b 的形式，那么代码是： if a < b goto B.true goto B.false 例 表达式 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

44 B.code = B1.code || gen(B1.false, ':') || B2.code }
7.4 布尔表达式和控制流语句 B  B1 or B2 { 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  not B1 { B1.true = B.false; B1.false = B.true; B.code = B1.code }

45 B.code = B1.code || gen(B1.true, ':') || B2.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 }

46 { B.code = E1.code || E2.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)}

47 7.4.4 开关语句的翻译 switch E begin case V1: S1 case V2: S2 . . .
7.4 布尔表达式和控制流语句 7.4.4 开关语句的翻译 switch E begin case V1: S1 case V2: S2 . . . case Vn-1: Sn-1 default: Sn end

48 t = E的代码 | Ln-2: if t != Vn-1 goto Ln-1 if t != V1 goto L1 | Sn -1的代码
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: | |

49 分支较多时，将分支测试代码集中在一起，便于生成较好的 分支测试代码 t = E的代码 | Ln: Sn的代码
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 |

50 中间代码增加一种case语句，便于代码生成器对它进行特别处理
7.4 布尔表达式和控制流语句 中间代码增加一种case语句，便于代码生成器对它进行特别处理 test: case V1 L1 case V2 L2 . . . case Vn-1 Ln-1 case t Ln next: 一个生成：  用二分查找确定该执行的分支  直接找到该执行的分支 的例子见第8章习题

51 过程调用id(E1, E2, …, En)的中间代码结构 E1.place = E1的代码 E2.place = E2的代码 . . .
7.4 布尔表达式和控制流语句 7.4.5 过程调用的翻译 S  call id (Elist) Elist  Elist, E Elist  E 过程调用id(E1, E2, …, En)的中间代码结构 E1.place = E1的代码 E2.place = E2的代码 . . . En.place = En的代码 param E1.place param E2.place param En.place call id.place, n

52 { 为长度为n的队列中的每个E.place， emit('param', E.place);
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 }

53 for v := initial to final do stmt 定义成和下面的代码序列有同样的含义： begin
7.4 布尔表达式和控制流语句 例题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

54 for v := initial to final do stmt 能否定义成和下面的代码序列有同样的含义？ begin
7.4 布尔表达式和控制流语句 例题1 for v := initial to final do stmt 能否定义成和下面的代码序列有同样的含义？ begin t1 := initial; t2 := final; v := t1; while v <= t2 do begin stmt; v := succ(v) end

55 for v := initial to final do stmt 的中间代码结构如下: t1 = initial t2 = final
7.4 布尔表达式和控制流语句 例题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:

56 例题2 C语言的for语句有下列形式 for ( e1 ; e2 ; e3 ) stmt 它和 e1;
7.4 布尔表达式和控制流语句 例题2 C语言的for语句有下列形式 for ( e1 ; e2 ; e3 ) stmt 它和 e1; while ( e2 ) do begin stmt; e3; end 有同样的语义

57 例题2 C语言的for语句有下列形式 for ( e1 ; e2 ; e3 ) stmt 的中间代码结构如下 e1的代码 L1: e2的代码
7.4 布尔表达式和控制流语句 例题2 C语言的for语句有下列形式 for ( e1 ; e2 ; e3 ) stmt 的中间代码结构如下 e1的代码 L1: e2的代码 L2: e3的代码 goto L1 stmt的代码 goto L2 真转 假转，由外层语句决定

58 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 若a和b是同一类型记录，也允许
7.4 布尔表达式和控制流语句 例题3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 若a和b是同一类型记录，也允许 C语言 数组类型不行，结构体类型可以 为这种赋值选用或设计一种三地址语句，它要便于生成目标 代码 仍然用中间代码复写语句 x = y，在生成目标代码时，必须 根据它们类型的size，产生一连串的值传送指令

59 下面的翻译方案使用了变量offset，请重写该翻译方案，它完 成同样的事情，但只使用文法符号的属性，而不使用变量 offset
7.4 布尔表达式和控制流语句 例题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; }

60 P  { D.offset1 = 0; } D { P.offset =D.offset2; }
7.4 布尔表达式和控制流语句 例题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; }

61 中间代码的后缀表示、图形表示、三地址代码，它们之间的 相互转换 符号表的组织和作用域信息的保存
7 中间代码生成 本章要点 中间代码的后缀表示、图形表示、三地址代码，它们之间的 相互转换 符号表的组织和作用域信息的保存 数组元素定址的翻译方案，布尔表达式的两种不同实现方式 赋值语句和各种控制流语句的中间代码格式和生成中间代码 的翻译方案 过程调用的中间代码格式和生成中间代码的翻译方案

62 7 中间代码生成 习题 中间代码的表示 7.1 7.2 符号表的建立 7.4 控制流语句的中间代码 7.8 7.10