编译原理 Compiler Principles 第六章中间代码生成 湖南大学信息科学与工程学院 软件工程系杨金民 2018

Transcription

1 编译原理 Compiler Principles 第六章中间代码生成 湖南大学信息科学与工程学院 软件工程系杨金民 2018

2 什么叫语法制导的翻译 求表达式的值 id 1 + id 2 *id * 5 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 id 2 id 3 四者的语义相同 对于计算机执行的指令流 : E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 对于计算器的计算结果 : 19

3 源程序 中间代码 求表达式的值 id 1 + id 2 *id * 5 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 id 2 id 3 对于计算机执行的指令流 : E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 对于计算器的计算结果 : 19 源程序是语句流, 中间代码是指令流, 都是线性结构

4 中间代码形式 源程序 高级中间表示形式 低级中间表现形式 目标代码 文法 :E E + E E * E id E 5 E 1 + E 4 id 1 E 2 * E 3 + * E 1 = id 1 E 2 = id 2 E 3 = id 3 E 4 = E 2 * E 3 E 5 = E 1 * + E 4 id 2 id 3 id 1 id 1 id 1 语法分析树 抽象语法树 三地址码

5 中间代码形式 有向无环图 DAG DAG(directed acyclic graph) 表达式 a + a * (b - c) + (b - c ) * d 的 DAG: + + * a * - d b c

6 中间代码形式 有向无环图 DAG 表达式 a + a * (b - c) + (b - c ) * d * * * a * - d - b c a b c c DAG 抽象语法树

7 生成抽象语法树的 SDD 产生式 1)E E 1 + T 2)E T 3)T T 1 * F 4)T F 5)F (E) 6)F id 语义规则 E.node = new Node('+', E 1.node, T.node) E.node =T.node E.node = new Node('*', T 1.node, F.node) T.node = F.node F.node = E.node F.node = new Leaf(id, id.entry)

8 生成 DAG 的 SDD 产生式 1)E E 1 + T 2)E T 3)T T 1 * F 4)T F 5)F (E) 6)F id 语义规则 E.node = gennode('+', E 1.node, T.node) E.node =T.node E.node = gennode('*', T 1.node, F.node) T.node = F.node F.node = E.node F.node = gen Leaf(id, id.entry) gennode((op, leftnode, right_node) { node = getnode(op, leftnode, right_node); if (node == null ) then return new Node(op, leftnode, right_node); else return node; } 差异何在?

9 6.2 三地址代码 一个运算符, 两个运算分量, 一个运算结果 ; x=y op z 运算分量 : 名字 : 用源程序中名字作为三地址代码的地址 常量 : 源程序中出现的 ; 编译器生成的临时变量 ;

10 三地址代码 (2) 指令 (1) 运算 / 赋值指令 :x=y op z, 或者 x=op y 复制指令 :x = y 无条件转移指令 :goto L 条件转移指令 :if x goto L if False x goto L 条件转移指令 :if x relop y goto L

11 三地址代码 (3) 过程调用 / 返回 : param x1 // 传递参数 param x2 param xn call p, n // 调用子过程 p,n 为参数个数 带下标的复制指令 :x=y[i] x[i] = y 注意 :i 表示离开数组位置第 i 个字节, 而不是数组的第 i 个元素 地址 / 指针赋值指令 : x=&y, x=*y, *x=y

12 三地址码例子 语句 : do i = i + 1; while (a[i]<v); 符号表 L: t 1 = i + 1 i = t 1 t 2 = i * 8 t 3 = a[t 2 ] IF t 3 < v GOTO L id name type size 0 i integer 4 1 a float(6, integer) 2 v integer 4 3 t1 integer 4 4 t2 integer 4 5 t3 integer : 组元素的大小 ( 字节数 )

13 其它中间代码表达形式 在实现时, 还有四元式 三元式 间接三元式 静态单 赋值 ; 四元式 :op, arg1, arg2, result; 三元式 : 就是 DAG;

14 6.3 类型和变量声明 类型检查 (Type Checking) 规则 : 保证运算分量的类型和运算符的预期类型要匹配 翻译 : 确定名字的类型, 需要的内存空间 计算数组元素的 地址 ( 即存储空间布局 ( 相对地址 ) 类型转换 选择正确 的运算符 ;

15 类型表达式 类型表达式 (type expression) 表示类型的结构, 其定义如下 : 基本类型是一个类型表达式 如 :boolean integer,float, void 等 类名是一个类型表达式 类型构造算子作用于类型仍是类型表达式 array[ 数字, 类型表达式 ] record { 字段, 类型对的列表 } list 类型 set 类型

16 类型表达式 从函数的角度来看待类型 : 类型构造算子 : 是用类型作为参数, 构造出新的类型 ; 从类型 s 到类型 t 的函数记作 s t; 按照函数的写法应该是 t (s) 例如 :list( ) 的结果是列表类型, 其元素的类型为 ; class Cell { int info; Cell next; } 类型名和递归类型 ; 可以给类型取名, 例如上面的 Cell 某种类型的变量,

17 变量的类型声明 文法 1 D T id ; D ε 2 T B C record { D } 3 B int float 4 C ε [num] C 语义 : D 生成一系列声明 ; T 生成不同的类型 ; B 生成基本类型 int/float; C 表示分量, 生成 [num] 序列 ; 注意 record 中包含了各个字段的声明 字段声明和变量声 明的文法一致

18 局部变量的存储布局 变量的类型, 确定了变量的内存大小 ( 以字节为单位 ), 称为类型的宽度 变量有值和地址两个值两个概念 变量值放在内存中, 在内存中的放置位置, 叫地址 可基于地址来访问变量的值 ; 变量的类型信息保存在符号表中 ; 一个函数的局部变量总是分配在连续的区间, 可基于相对地址来访问变量的值 相对地址, 是相对于这个区间的开始处

19 基本类型和数组类型的表达式和宽度求 解 SDT 例如,int [2][3] 的类型表达式为 array(2, array(3,integer) T t,w 1)T B {T.t = C.t = B.t; C.w =B.w } C { T.t=C.t ; T.w = C.w } t,w B t,w t C 2)B int { B.t = integer; B.w = 4 } 3)B float { B.t = float; B.w = 8 } t,w t,w int [ 2 ] C 1 4)C { C 1.t = C.t; C 1.w = C.w } t,w [num]c 1 { C.t = array(num, C 1.t) t,w [ 3 ] C 2 ; C.w = num * C 1.w } 5)C 在这里将 C 的 t 和 w 属性, 首先在展开时充当继承属性, 然后在 规约时让它们充当综合属性

20 程序的嵌套性层次结构 可伸展的树形结构 } include my_head.h int g_num; int main( int argc, char *argv ) { char szbuf [128]; char *psz = "Hello"; int p = 2; g_num = 189; MyFun( p ); if (p > 0) { int p; p = strcpy(szbuf, psz); } return 0; 函数块 1 main root 块 if 块 1 while 块 2... 函数 n if 块 1 if 块 2 while 块 3 每个 block 都有其符号表 类型符号表 ; 通常在 root 块中 变量符号表 ;

21 变量的作用域和内存布局 scheme 在一个函数里面, 其所有变量放在一个连续的存储空间中, 变 量在该空间的放置顺序与声明顺序一致 ; 相对地址从 0 开始, 变量 offset 记录了当前可用的相对地址 ; 每申明一个变量,SDT 所做处理 : offset 的值增加其宽度 : 在当前块的符号表中, 增加一行 ( 变量实例 ): top.put(id.lexeme, T.type, offset)

22 函数文法

23 声明序列的 SDT(2) 1) F {top = new Env(); D.offset= 0 } D 2) D T id; { top.put(id, T.type, offset, offset); D 1.offset = D.offset + T.width; } D 1 { D.offset = D 1.offset ; } 3) D

24 对记录类型 为每个记录创建单独的符号表 把原有的符号表对象, 以及 offset 暂存到环境中 在环境中新建一个符号表, 设 offset=0 T record id '{' { Env.push(top); top = new Env(); stack.push(offset); offset = 0; } D '}' {T.name = id.lexeme, T.type=record(top); T.width = offset; top env.pop(); offset = stack.po(); }

25 将表达式 三地址指令序列的 SDD 产生式 1)S id=e; 2)E E 1 + E 2 3)E -E 1 4)E (E 1 ) 5)E id 语义规则 S.code =E.code gen(top.get(id.lexeme) '=' E.addr) E.addr = new temp() E.code =E 1.code E 2.code gen(e.addr '= E 1.addr '+' E 2.addr) E.addr = new temp() E.code =E 1.code gen(e.addr '=' 'minus' E 1.addr ) E.addr = E 1.addr E.code =E 1.code E.addr = top.get(id.lexeme) E.code =''

26 增量式翻译方案 SDT 1)S id=e; 2)E E 1 + E 2 3)E -E 1 { AddCode(top.get(id.lexeme) '=' E.addr); } { E.addr = new temp(); AddCode(E.addr '= E 1.addr '+' E 2.addr); } { E.addr = new temp() AddCode(E.addr '=' 'minus' E 1.addr ); } 4)E (E 1 ) { E.addr = E 1.addr; } 5)E id { E.addr = top.get(id.lexeme); }

27 数组元素的寻址 数组元素被存放在连续的存储空间中 ; 元素从 0 到 n-1 编号, 第 i 个元素的地址为 :base+i*w K 维数组的寻址 : 数组按行存放时,A[i 1 ][i 2 ] [i k ] 的地址 base+i 1 *w 1 +i 2 *w 2 + +i k *w k 或者 base+(( ((i 1 *n 2 +i 2 )*n 3 +i 3 ) )*n k +i k )*w 在符号表中有 A 的条项,A 的条项中记录了 A 的类型,base 就是 A 的地址, 即 A 申明时填的 offset;

28 数组元素 L:L L[E] id[e] S L=E; E L. 计算偏移量, 存放于 L.addr 所指的临时变量中 1)L id[e]; 2)L L 1 [E] { L.array = top.get(id.lexeme); L.type =L.array.type.elem; L.addr = new Temp(); gen( L.addr '=' E.addr '*' L.type.width); } { L.array = L 1.array ; L.type =L 1.type.elem; t = new Temp(); L.addr = new Temp(); gen( t '= E.addr '*' L.type.width); gen( L.addr '=' L 1.addr '+' t); }

29 数组元素作为因子 L 的代码只计算了偏移量 ; 数组元素的值 : L 的数组基址加上偏移量 ; 使用三地址指令 x=a[i] 5)E L { E.addr = new temp(); AddCode(E.addr '=' L.array.base'[' L.addr ']'); }

30 给数组元素赋值 使用三地址指令 a[i]=x S L = E; { gen(l.array.base '[' L.addr ']' '=' E.addr); }

31 int a[2][3], c, i, j; 求表达式 c+a[i][j] 的三地址码序列 E addr= c c a [ E addr=i ] type=array(2, array(3, integer)) E + addr=t 5 L [ E ] type=array(3,integer) array = a addr=j addr=t 1 i 注释语法分析树 E L addr=t 4 array = a; type=integer addr=t 3 j t 1 = i * 12 t 2 = j * 4 t 3 = t 1 + t 2 t 4 = a[ t 3 ] t 5 = c + t 4

32 类型检查和转换 类型系统 : 编译时, 目标代码中的元素有值, 类型, 存储地址 的概念 ; 编译时就解决类型匹配问题 保证运行时, 不再存在 有关类型的问题要处理, 不会出错 : 强类型的语言 ; 编译时来发现错误, 以提高运行时效率 确定临时变量的大小 例如将一个 float 类型的变量的地址, 赋给一个 int 的指针变 量

33 类型检查的两种方式 类型综合 根据子表达式的类型构造出表达式的类型 例 :E 1 +E 2 的类型根据 E 1,E 2 的类型定义 要求名字先定义后使用 f,x 是表达式, s t 是从 s 映射到 t 的函数 if f 的类型为 s t, 且 x 的类型为 s, then f(x) 的类型为 t 可扩充到多变量函数 : 例 : E 1 +E 2 可看作函数 add(e 1, E 2 ) 类型推导

34 类型检查的两种方式 类型综合 类型推导 根据语言结构的使用方式来确定该结构的类型 if f(x) 是一个表达式 then 对于某类型 α,β;f 的类型为 α β 且 x 的类型为 α 例 :null(x) 是一个测试列表是否为空的函数, 则根据函数 null(x) 可推断出 x 必定是一个列表, 但 x 的元素类型未知 不要求名字先定义的语言需要类型推导, 如 :ML

35 类型转换 设表达式 x+i,x 为浮点数 i 为整数, 则结果应该是浮点数 x 和 i 使用不同的二进制表示方式 浮点 + 和整数加使用不同的指令 t1 = (float) i t2 = x + t1 类型转换比较简单时 E E1 + E2 { if(e1.type = integer and E2.type = integer) E.type = integer; else } ( 问题 : 请补充完整这条规则的语义动作 ) } 这个规则没有考虑产生类型转换代码

36 类型的 widening 和 narrowing Java 类型转换规则区分了拓宽转换和窄化转换 编译器自动完成的转换为隐式转换, 程序员用代码指定的转换为显式转换

37 处理类型转换的 SDT 图 6.27 在表达式计算中引入类型转换 图 6.26 widen 函数的伪代码

38 函数 / 运算符的重载 重载 (overload) 是面向对象程序设计语言的一个特征 例 :Java 语言中 + 算符可表示串连接或加法运算, 由操作数的类型来区分 用户自定义的函数也可以重载, 如 : Void err() { } Void err(string S) { }

39 函数 / 运算符的重载 通过查看参数就能解决的函数重载问题 E f(e1) { if f.typeset = {s i t i 1<= i<= k} and E 1.type=s k then E.type = t k }

40 6.6 控制流的翻译 布尔表达式可以用于改变控制流, 计算逻辑值 文法 B B B B && B!B (B) E relop E true false 语义 B 1 B 2 中 B 1 为真时, 不计算 B 2, 整个表达式为真 因此, 当 B 1 为真时应该跳过 B 2 的代码 B 1 && B 2 中 B 1 为假时, 不计算 B 2, 整个表达式为假 短路代码 通过跳转指令实现控制流的处理

41 短路代码的例子 语句 : if (x<100 x>200 && x!= y) x = 0; 代码 if x < 100 goto L2 if FALSE x > 200 goto L1 if FALSE x!= y goto L1 L2: x=0 L1: 接下来的代码

42 继承属性 : B.true B.false S.next 产生式 1)P S; 2)S if (B) S 1 B.true: B.false: 控制流语句的 SDD B.code S 1.code... S if (B) S 1 to B.true to B.false S.next 语义规则 S.next =newlable( ); P.code = S.code label(s.next) if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : B.true = newlable( ); B.false = S.next; S 1.next= S.next; S.code =B.code label(b.true) S 1.code

43 控制流语句的 SDD 继承属性 : B.true B.false S.next B.true: B.false: S.next: B.code S 1.code goto S.next S 2.code... S if (B) S 1 else S 2 to B.true to B.false 产生式 3)S if (B) S 1 else S 2 语义规则 B.true = newlable( ); B.false = newlable( ); S 1.next= S.next; S 2.next= S.next; S.code =B.code label(b.true) S 1.code gen('goto' S.next) label(b.false) S 2.code

44 控制流语句的 SDD begin: B.true: B.false: B.code S 1.code goto begin... to B.true to B.false S.next S while(b) S 1 产生式 4)S while (B) S 1 语义规则 begin = newlable( ); B.true = newlable( ); B.false =S.next; S1.next= S.next; S.code =label(begin) B.code label(b.true) S 1.code gen('goto' begin) label(b.false)

45 控制流语句的 SDD 产生式 语义规则 5)S S 1 S 2 S 1.next = newlable( ); B.true = newlable( ); B.false =S.next; S 2.next= S.next; S.code =S 1.code label( S 1.next) S 2.code

46 控制流语句 While 的 SDT begin: B.true: B.false: B.code S 1.code goto begin... to B.true to B.false S.next S while(b) S 1 S while ( {begin = newlabel( ); B.true = newlabel( ); B.false = S.next; AddCode(begin : ) } B) {AddCode(B.true : ); S1.next= S.next; } S 1 { AddCode ( goto begin); }

47 翻译布尔表达式的 SDD 产生式 1)B true; 2)B false 3)B E 1 rel E 2 语义规则 B.code = gen('goto' B.true) B.code = gen('goto' B.false) B.code =E1.code E1.code gen('if' E1.addr rel.op E2.addr 'goto' B.true)

48 翻译布尔表达式的 SDD 产生式 4)B!B 1 ; 语义规则 B1.true =B.false; B1.false = B.true; 5)B B 1 && B 2 B 1.true = newlabel( ); B 1.false = B.false; B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.true) B 2.code

49 翻译布尔表达式的 SDD 产生式 6)B B 1 B 2 语义规则 B 1.true = B.true; B 1.false = newlabel( ); B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.false) B 2.code

50 布尔表达式代码的例子 例 : 将 if (x<100 x > 200 && x!= y ) x = 0; 翻译成三地址 码 if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 :

51 减少 goto 指令 例 : 将 if (x<100 x > 200 && x!= y ) x = 0; 翻译成三地址 码 if x<100 goto L 2 goto L 3 L 3 : if x> 200 goto L 4 goto L 1 L 4 : if X!=y goto L 2 goto L 1 L 2 : x = 0 L 1 : 多余 iffalse x>200 goto L 1 iffalse x!=y goto L 1 if(b) S 1 B 的指令之后就是 S 1, B.true 不须要, 设为 fall

52 减少 goto 指令 产生式 3)B E 1 rel E 2 当时 B.code B.true: S 1.code B.false:... S if (B) S 1 语义规则 if B.true fall then B.code =E1.code E1.code gen('if' E1.addr rel.op E2.addr 'goto' B.true) else to B.true to B.false B.false: B.true= fall B.code S 1.code... to B.false B.code =E1.code E1.code gen('if False' E1.addr rel.op E2.addr 'goto' B.false)

53 减少 goto 指令 产生式 3)B E 1 rel E 2 语义规则 B.code =E1.code E1.code gen('if' E1.addr rel.op E2.addr 'goto' B.true) 产生式 3)B E 1 rel E 2 语义规则 if B.true fall then B.code =E1.code E1.code gen('if' E1.addr rel.op E2.addr 'goto' B.true) else B.code =E1.code E1.code gen('if False' E1.addr rel.op E2.addr 'goto' B.false)

54 减少 goto 指令 B B 1 B 2 当 B.true=fall 时 B 1.true S.next B1.code B 2.code S1.code... to B 1.true to B 2.false 因为 B 1.false 就是 B 2.code, 因此设 B 1.false=fall, 要省了一 条 goto B 2 起始处的指令 因为 B.true=fall, 又 B 1.code 中要跳转到 S 1.code 的开始 处, 只好创建 B 1.true

55 减少 goto 指令 B B 1 && B 2 当 B.true=fall 时 B 1.true S.next B1.code B 2.code S1.code... to B 1.false to B 2.false 因为 B 1.true 就是 B 2.code 起始处, 因此要设 B 1.true=fall, 省了一条 goto B 2 起始处的指令因为 B 2.true=fall, 又 B 2.code 后自然接 S 1, 省了一条 goto S 1 起始处的指令

56 翻译布尔表达式的 SDD 产生式 6)B B 1 B 2 语义规则 B 1.true = B.true; B 1.false = newlabel( ); B 2.true = B.true; B 2.false = B.false; B.code =B 1.code label(b 1.false) B 2.code 产生式 6)B B 1 B 2 语义规则 if B.true = fall then B 1.true = newlabel(); else B 1.true = B.true; B 1.false = fall; B 2.true = B.true; B 2.false = B.false; if B.true = fall then B.code =B 1.code B 2.code label(b 1.true) else B.code =B 1.code label(b 1.false) B 2.code

57 求布尔表达式的值, 比如 :x= a<b S id =B 等价于 if (B) id=true else id = false; S id = { B.true = newlabel( ); B.false = newlabel( ); } B {AddLabel(B.true : ); AddCode(id = true ); AddCode( goto' S.next) ; AddLabel(B.false : ); AddCode(id =false );}

58 生成 goto 指令时目标尚未已知问题 S if (B) S 1 按照短路代码的翻译方法,B 和 S 1 的代码中, 会包含有一些跳转指令 goto S.next 这些指令在前,S.next 标记的指令在后 ; 因此生成指令 goto S.next 时,S.next 的值是未知的 只有 S if (B) S 1 规约完了, 随后才会生成 S.next 标记的指令, 此时 S.next 才确定 ; B 中的 goto B.true 指令, 和 goto B.false 指令, 也有该问题 简单直接的方法是扫描一次代码, 填上 ;

59 回填技术的基本思想 在 B 和 S 1 中, 当生成 goto S.next 指令时, 记下该指令的 id, 添加到 B 的综合属性 B.nextList 中 规约时, 上传, 当规约 S if (B) S 1 时, 在完成中间代码生成之后, 此时 S.next 的值就确定下来了 使用 B.nextList, 定位这些前面的指令, 回填上 S.next 的值 ; 回填是在生成代码时, 调用 AddLabel(labelId ':') 时, 执行

60 布尔表达式的回填翻译 对布尔表达式 B, 引入两个综合属性 truelist: 包含跳转指令的列表, 为 true 时执行这些指令 Falselist: 包含跳转指令的列表, 为 false 时执行这些指令辅助函数 : Makelist(i) : 创建一个只含 i 的列表,i 是指令 id( 即数组的下标 ), 返回一个指向新创建列表的指针 ; Merge(p1,p2): 合并 p1 和 p2 指向的列表, 返回指向合并后新表的指针 Backpatch(p,i): 将 i 作为 goto 目标地址回填到 p 所含各指令中

61 布尔表达式的回填翻译 SDT 1)B true; { B.truelist = makelist(nextinstr); gen('goto _');} 2)B false; { B.falselist = makelist(nextinstr); gen('goto _');} 3)B E 1 rel E 2 { B.falselist = makelist(nextinstr); B.falselist = makelist(nextinstr + 1); gen('if' E 1.addr rel.op E 2.addr 'goto _'); gen('goto _'); }

62 布尔表达式的回填翻译 SDT 4)B (B 1 ); { B.truelist = B 1.truelist; B.falselist = B 1.falselist ;} 5)B!(B 1 ); { B.truelist = B 1.falselist; B.falselist = B 1.truelist; }

63 布尔表达式的回填翻译 SDT 6)B B 1 && { B 2.instr = nextinstr; } B 2 { Backpatch(B 1.truelist, B 2.instr); B.truelist = B 2.truelist; B.falselist = merge(b 1.falselist, B 2.falselist); } 7)B B 1 { B 2.instr = nextinstr; } B 2 { Backpatch(B 1.falselist, B 2.instr); B.falselist = B 2.falselist; B.truelist = merge(b 1.truelist, B 2.truelist); }

64 回填例子 :x<100 x>200 && x!=y 假设从 nextinstr = 100 开始 100: if x<100 goto _ 101: goto _ B t={100} f={100} x<100 i=102 B t={100,104} f={103,105} i=104 B B t={102} f={103} && t={104} f={103,105} B t={104} f={105} 102: if x>200 goto _ 103: goto _ 104: if x!=y goto _ 105: goto _ x>200 x!=y

65 控制转移语句的回填 S if ( B ) S if (B) S else S while (B) S { L } A L L S S 语句的综合属性 :nextlist 其中的跳转指令的目标, 是 S 执行完毕之后, 应该执行的下一条指令 考虑 S 是 while 语句 if 语句的子语句时, 分别应该跳转到哪里?

66 控制转移语句的回填 (2) 1) S if (B) { S 1.instr = nextinstr;} S 1 { backpatch(b.truelist, S 1.instr); S.nextlist = merge(b.falselist, S 1.nextlist); } 2) S if (B) { S 1.instr = nextinstr; } S 1 N else {S 2.instr = nextinstr;} S 2 { backpatch(b.truelist, S 1.instr); backpatch(b.falselist, S 2.instr); temp= merge(s 1.nextlist, N.nextlist); S.nextlist = merge(temp, S 2.nextlist); } 3) N { N.nextlist = makelist(nextinstr); gen('goto _'); } N 的作用是生成 goto 指令坯,N.nextlist 记录了这个指令的位置

67 控制转移语句的回填 (3) 4) S while ( { B.instr = nextinstr;} B) { S 1.instr = nextinstr;} S 1 { backpatch(s 1.nextlist, B.instr); backpatch(b.truelist, S 1.instr); S.nextlist = B.falselist; gen('goto' B.instr); }

68 控制转移语句的回填 (3) 5) S {L} { S.nextlist =L.nextlist ; } 6) S A; { S.nextlist =null; }S 1 L L 1 {S.instr = nextinstr;} S;N else S 2 { backpatch(l1.nextlist,s.instr); L.nextlist = S.nextlist; } 7) L S { L.nextlist =S.nextlist ; }

69 Break Continue 的处理 虽然 break continue 在语法上就是一个句子, 但是它的代码却和外围语句相关 方法 : 跟踪外围语句 S, 生成一个跳转指令坯 将这个指令坯的位置加入到 S 的 nextlist 中 跟踪的方法 在符号表中设置 break 条目, 令其指向外围语句 在符号表中设置指向 S 的 nextlist 的指针, 然后把这个指令坯的位置直接加入到 nextlist 中

70 6.8 switch 语句 许多语言都有 switch 或 case 语句 语句结构 switch (E) of { case V 1 : S 1 ; case V 2 : S 2 ; case V n-1 : S n-1 ; otherwise: S n }

71 switch 语句的翻译 1. 计算表达式 E 的值 2. 在 case 列表中寻找与表达式值相同的值 V j 当 case 表中明确列出的值都不与表达式匹配时, 就用默认值和表达式匹配 3. 执行和匹配值关联的语句 S j 其中步骤 2 是一个 n 路分支, 可采用多种方式实现

72 创建一个对照关系表 实现条件跳转的方式 编译器生成一个简单循环, 检查表达式 E 的值 当匹配某个 V i 时, 执行对应的 S i 均不匹配时, 肯定与末项匹配

73 翻译法 ( 一 ) T=E L 1 : if T V 1 goto L 2 S 1 的代码 goto next L 2 : if T V 2 goto L 3 S 2 的代码 goto next L 3 : L n-1 : if T V n-1 goto L n S n-1 的代码 goto next L n : next: S n 的代码

74 翻译法 ( 二 ) L 1 : L n-1 : L n : T=E goto test 关于 S 1 的中间码 goto next 关于 S n-1 的中间码 goto next 关于 S n 的中间码 goto next test: if T=V 1 goto L 1 if T=V 2 goto L 2 if T=V n-1 goto L n-1 goto L n next:

75 用来翻译 switch 语句的 case 三地址代 码指令 Case t V 1 L 1 Case t V 2 L 2 Case t V n-1 L n-1 Case t t L n next:

76 过程的中间代码 在三地址码中, 函数调用被拆分为准备进行调用时的参数求值, 然后是调用本身 设 a 为 int 类型的数组, n = f(a[i]); 的三地址码 : t 1 =i*4 t 2 =a[t 1 ] param t 2 t 3 = call f, 1 n = t 3

77 函数定义和调用的产生式 D T id(f) {S} F T id T id, F S return E; E id(a) A E E, A

78 过程调用的处理 过程调用主要对应两种事 : 传递参数 转子 传地址 : 把实在参数的地址传递给相应的形式参数 调用段预先把实在参数的地址传递到被调用段可以拿到的地方 ; 程序控制转入被调用段之后, 被调用段首先把实在参数的地址抄进自己相应的形式单元中 ; 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问

79 过程调用的翻译 翻译方法 : 把实参的地址逐一放在转子指令的前面. 例如, CALL S(A,X+Y) 翻译为 : 计算 X+Y 置于 T 中的代码 param A /* 第一个参数的地址 */ param T /* 第二个参数的地址 */ call S,2 /* 转子 */

80 过程调用的翻译 过程调用文法 : (1) S call id (Elist) (2) Elist Elist, E (3) Elist E 参数的地址存放在一个队列中 最后对队列中的每一项生成一条 param 语句

81 翻译模式 3. Elist E { 初始化 queue 仅包含 E.place;n=0 } 2. Elist Elist, E { 将 E.place 加入到 queue 的队尾 ;n=n+1 } 1. S call id (Elist) { for 队列 queue 中的每一项 p do gen( param p); gen( call id.addr, n) }

82 作业 6.1.1,6.2.1,6.4.3(2),6.6.4(1),6.7.1(1)

83 第六章中间代码生成 语义分析和中间代码生成 中间代码表示 类型检查和翻译 中间代码生成 DAG 图 三地址码 静态单赋值 表达式翻译 控制流翻译 回填 过程翻译

84 谢谢谢谢!