Microsoft PowerPoint - L12-v3.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - L12-v3.pptx"

锤印
5 years ago
Views:

1 Lecture 12: 中间代码生成 -II Xiaoyuan Xie 谢晓园计算机学院 E301

2 控制流翻译

3 控制流语句的翻译文法 B表示布尔表达式 S代表语句 S if (B) S1 S if (B) S1 else S2 S while (B) S1 代码的布局见右图继承属性 B.true B为真的跳转目标 B.false B为假的跳转目标 S.next S执行完毕时的跳转目标

4 控制流语句的翻译控制流语句的翻译 S if B then S1 if B then S1 else S2 while B do S1 S1; S2

5 控制流语句的翻译 S if B then S1 {B.true = newlabel(); B.true: B.false = S.next; S1.next = S.next; B.code 指向B.true 指向B.false S1.code... (a) if-then S.code = B.code gen(b.true, : ) S1.code } label(b.true)

6 控制流语句的翻译 S if B then S1 else S2 {B.true = newlabel(); B.true: B.false = newlabel(); S1.next = S.next; S2.next = S.next; S.code = B.false: B.code S1.code goto S.next S2.code... (b) if-then-else B.code gen(b.true, : ) S1.code gen( goto, S.next) gen(b.false, : ) S2.code} 指向B.true 指向B.false

7 控制流语句的翻译 S while B do S1 {S.begin = newlabel(); S.begin: B.true = newlabel(); B.true: B.false = S.next; S1.next = S.begin; B.code S1.code goto S.begin... (c) while-do S.code = gen(s.begin, : ) B.code gen(b.true, : ) S1.code gen( goto, S.begin) } 指向B.true 指向B.false

8 控制流语句的翻译 S S1; S2 {S1.next = newlabel(); S2.next = S.next; S.code = S1.code gen(s1.next, : ) S2.code } S1.next: S1.code S2.code... (d) S1; S2

9 布尔表达式翻译

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

11 布尔表达式布尔表达式的完全计算布尔值计算和算数表达式计算非常类似可仿照算数表达式翻译方法为每个产生式写出语义子程序值的表示数值化效率低下

12 布尔表达式如何优化布尔表达式的短路计算用控制流来实现计算即用程序中的位置来表示值因为布尔表达式通常用来决定控制流走向 B1 or B2 定义成 if B1 then true else B2 B1 and B2 定义成 if B1 then B2 else false 两种不同计算方式会导致程序的结果不一样有时B中有副作用

13 布尔表达式的控制流语句的翻译布尔表达式可以用于改变控制流/计算逻辑值 B && B!B (B) E rel E true false 短路代码 B B B 通过跳转指令实现控制流的处理逻辑运算符本身不在代码中出现语义 B1 B2中B1为真时不计算B2 整个表达式为真因此当B1为真时可以跳过B2的代码定义成 if B1 then true else B2 B1&&B2中B1为假时可以不计算B2 整个表达式为假定义成 if B1 then B2 else false

14 布尔表达式的控制流翻译生成的代码执行时跳转到两个标号之一表达式的值为真时跳转到B.true 表达式的值为假时跳转到B.false B.true和B.false是两个继承属性根据B所在的上下文指向不同的位置如果B是if语句的条件表达式分别指向then分支和else分支如果没有else分支则指向if语句的下一条指令如果B是while语句的条件表达式分别指向循环体的开头和循环出口处

15 布尔表达式的控制流翻译

16 布尔表达式的控制流翻译如果B是a < b的形式那么代码是 if a < b goto B.true goto B.false

17 布尔表达式的控制流语句的翻译例表达式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 goto Lfalse

18 场景一布尔表达式用于决定控制流走向以 if (B) then S1 else S2 为例进行说明 if (T) then S1 else S2 if (E1 rop E2) then S1 else S2 if (B1 B2) then S1 else S2 if (B1 && B2) then S1 else S2 if (!B) then S1 else S2

19 场景一布尔表达式用于决定控制流走向短路代码例子 if (x<100 x>200 && x!= y) x = 0;

20 场景二布尔表达式用于赋值程序中出现布尔表达式的目的可能就是求出它的值 x=a<b && c<d

21 场景三 General cases 处理方法首先建立表达式的语法树然后根据表达式的不同角色来处理文法 S id = E; if (E) S while (E) S S S E E E E && E E rel E 根据E的语法树结点所在的位置 S while ( E ) S1中的E 生成跳转代码对于S id = E 生成计算右值的代码

22 Switch 语句的翻译

23 Switch语句翻译分支数较少时 switch E begin case V1: S1 case V2: S2... case Vn - 1: Sn 1 default: Sn end

24 Switch语句翻译分支较多时将分支测试代码集中在一起便于生成较好的分支测试代码

25 Switch语句翻译中间代码增加一种case语句便于代码生成器对它进行特别处理 test: next: case V1 case V2... case Vn-1 case t Ln L1 L2 简洁的办法构造一个关系对照表表中每个关系包含一个敞亮和对应的 label 运行时进行查找 Ln-1 N较小的时候效率可接受 N较大的时候二分查找 hash table 为每个可能值建立一个单元空间

26 过程调用的翻译

27 过程调用的翻译

28 语言中函数定义 D 定义了函数的 signature; F 定义了形参 ; S 定义了 ( 返回 ) 语句 ; E 定义了表达式, 包含函数调用 ; A 定义了实参

29 过程调用翻译需要考虑的点函数类型包含返回类型和形参类型 --- 在其列表上应用 fun构造算子构造符号表用栈来管理类型检查注意类型转换的规则函数调用为id(E, E,, E)生成三地址代码时只需对各个参数E生成三地址执行将所有E.addr放到一个队列中然后为每个参数生成一条param指令清除队列

30 回填

31 回填 1 为布尔表达式和控制流语句生成目标代码的关键问题某些跳转指令应该跳转到哪里例如 if (B) S 很重要按照短路代码的翻译方法 B的代码中有一些跳转指令在B为假时执行这些跳转指令的目标应该跳过S对应的代码,生成这些指令时 S的代码尚未生成因此目标不确定通过语句的继承属性next来传递需要第二趟处理如何一趟处理完毕呢

32 回填 2 基本思想记录B的代码中跳转指令goto S.next if goto S.next的位置但是不生成跳转目标这些位置被记录到B的综合属性B.falseList中当S.next的值已知时即S的代码生成完毕时把B.falseList中的所有指令的目标都填上这个值回填技术生成跳转指令时暂时不指定跳转目标标号而是使用列表记录这些不完整的指令等知道正确的目标时再填写目标标号每个列表中的指令都指向同一个目标

33 布尔表达式的回填翻译 1 布尔表达式用于语句的控制流时它总是在取值true时和取值false 时分别跳转到某个位置引入两个综合属性 truelist: 包含跳转指令位置的列表这些指令在取值true时执行 falselist 包含跳转指令位置的列表这些指令在取值false时执行辅助函数 Makelist(i) 创建一个只包含i的列表 Merge(p1,p2) 将p1和p2指向的列表合并 Backpatch(p,i) 将i作为目标标号插入到p所指列表中的各指令中

34 布尔表达式的回填翻译 (2)

35 回填和非回填方法的比较回填时生成指令坯然后加入相应的list 原来跳转到B.true的指令现在被加入到B.truelist中

36 回填和非回填方法的比较回填 ; 并将真假出口相对应 true/false 属性的赋值, 在回填方案中对应为相应的 list 的赋值或者 merge 原来生成 label 的地方, 在回填方案中使用 M 来记录相应的代码位置,M.inst 需要对应 label 的标号原方案生成的指令 goto B 1.false, 现在生成了 goto M.inst

37 布尔表达式的回填例子 x<100 x>200 && x!=y

38 控制转移语句的回填语句的综合属性 nextlist nextlist中的跳转指令的目标应该是s执行完毕之后紧接着执行的下一条指令的位置考虑S是while语句 if语句的子语句时分别应该跳转到哪里

39 控制转移语句的回填 M的作用就是用M.instr记录下一个指令的位置 N的作用是生成goto指令坯 N.nextlist只包含这个指令的位置

40 控制转移语句的回填

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

42 作业教材P263: 6.6.1, 教材P268: 6.7.1

43 类型检查

44 什么是类型一个程序变量在程序执行期间的值可以设想为有一个范围这个范围的一个界叫做该变量的类型变量都被给定类型的语言叫做类型化语言 typed language 语言若不限制变量值的范围则被称作未类型化的语言 untyped language

45 类型系统类型化语言的类型系统 type system 是该语言的一个组成部分它始终监视着程序中变量的类型通常还包括所有表达式的类型一个类型系统主要由一组定型规则 typing rules 构成这组规则用来给各种语言构造程序语句表达式等指派类型

46 类型系统程序运行时的执行错误分成两类会被捕获的错误 trapped error 例非法指令错误非法内存访问除数为零引起计算立即停止不会被捕获的错误 untrapped error 例下标变量的访问越过了数组的末端例跳到一个错误的地址该地址开始的内存正好代表一个指令序列错误可能会有一段时间未引起注意

47 类型系统禁止错误 forbidden error untrapped error集合 + trapped error的一个子集为语言设计类型系统的目标是在排除禁止错误良行为的程序(well-behaved) A program fragment that will not produce forbidden errors at run time (不同场合对良行为的定义略有区别) 安全语言任何合法程序都没有forbidden error

48 类型系统类型化的语言变量都被给定类型的语言表达式语句等程序构造的类型都可以静态确定例如类型boolean的变量x在程序每次运行时的值只能是布尔值 not (x)总有意义未类型化的语言不限制变量值范围的语言一个运算可以作用到任意的运算对象其结果可能是一个有意义的值一个错误一个异常或一个语言未加定义的结果,例如 LISP语言

49 类型系统显式类型化语言类型是语法的一部分隐式类型化的语言不存在隐式类型化的主流语言但可能存在忽略类型信息的程序片段例如不需要程序员声明函数的参数类型

50 类型系统 Strongly typed: 如果所有程序都是 well-behaved Dynamically typed: 运行时确定 forbidden error Statically typed: 编译时确定 forbidden error Weakly typed: 存在 illbehaved (i.e. forbidden error)

51 类型表达式类型本身也有结构我们使用类型表达式 (type expression)来表示这种结构基本类型 Boolean, integer, float, char, void 或类名或

52 类型表达式类型本身也有结构我们使用类型表达式 (type expression)来表示这种结构通过将类型构造算子作用于类型表达式而得例如 array[数字类型表达式] record[字段/类型对的列表] 可以用符号表表示函数类型构造算子参数类型结果类型笛卡尔积 s X t: struct { int a[10]; float f;} st 对应于 record((a array(0..9, int)) (f real)) 可以包含取值为类型表达式的变量

53 类型表达式的例子类型例子元素个数为3X4的二维数组数组的元素的记录类型该记录类型中包含两个字段: x和y,其类型分别是float和integer 类型表达式 array[3, array[4, record[(x,float),(y,integer)] ] ]

54 类型等价不同的语言有不同的类型等价的定义结构等价或者它们是相同的基本类型或者是相同的构造算子作用于结构等价的类型而得到的或者一个类型是另一个类型表达式的名字名等价类型名仅仅代表其自身

55 静态类型信息在编译中的作用应用一静态类型检查编译时确定forbidden error

56 类型检查和转换类型系统给每一个组成部分赋予一个类型表达式通过一组逻辑规则来表示这些类型表达式必须满足的条件可发现错误提高代码效率确定临时变量的大小

57 类型系统的分类类型综合根据子表达式的类型构造出表达式的类型 if f 的类型为s t且x的类型为s then f(x)的类型为t 类型推导根据语言结构的使用方式来确定该结构的类型 if f(x)是一个表达式 then 对于某些类型α,β f的类型为α β且x的类型为α

58 类型转换假设在表达式x*i中 x为浮点数 i为整数则结果应该是浮点数 x和i使用不同的二进制表示方式浮点*和整数*使用不同的指令 t1 = (float) i t2 = x fmul t1 类型转换比较简单时的SDD E E1 + E2 { if(e1.type = integer and E2.type = integer) E.type = integer; else if (E1.type = float and E2.type= integer) E.type = float; } 这个规则没有考虑生成类型转换代码

59 类型的widening和narrowing 编译器自动完成的转换为隐式转换程序员用代码指定的转换为显式转换

60 处理类型转换的SDT 函数Max求的是两个参数在拓宽层次结构中的最小公共祖先 Widen函数已经生成了必要的类型转换代码

61 函数/运算符的重载通过查看参数来解决函数重载问题 E f(e1) { if f.typeset = {si ti 1<= i<= k} and E1.type=sk then E.type = tk }

PowerPoint Presentation

PowerPoint Presentation 第六章中间代码生成许畅南京大学计算机系 2018 年春季本章内容中间代码表示表达式的有向无环图 DAG 三地址代码 :x = y op z 类型检查类型类型检查表达式的翻译中间代码生成控制流回填 2 编译器前端的逻辑结构前端是对源语言进行分析并产生中间表示处理与源语言相关的细节, 与目标机器无关前端后端分开的好处 : 不同的源语言不同的机器可以得到不同的编译器组合 3