大侠素材铺

Size: px

Start display at page:

Download "大侠素材铺"

麒握解
4 years ago
Views:

1 编译原理与技术中间代码生成 Ⅰ 计算机科学与技术学院李诚 12/11/2018

关于课程实验目标 : 为 PL0 语言实现一个简单的编译器 Project 1: 词法分析 Project 2: 语法分析 Project 3: 语法错误处理 + 对前两个 project 的扩展, 11.15 release,11.

2 关于课程实验目标 : 为 PL0 语言实现一个简单的编译器 Project 1: 词法分析 Project 2: 语法分析 Project 3: 语法错误处理 + 对前两个 project 的扩展, release,11.30 提交 Project 4: 代码生成,12.1 release,12.15 提交项目结束后, 需要进行答辩, 每一组准备 ppt, 每一名同学都要汇报自己做了什么学到了什么对课程和实验的意见与建议 2018/11/12 Compiler, USTC,

3 通知期中考试的成绩在本周之内公布由于老师出差, 周四的课取消, 后面补回来周四的上机课正常进行, 助教会发布新的项目内容, 并对之前项目的完成情况进行说明, 请大家尽量都去 2018/11/12 Compiler, USTC,

4 主要内容记号流分析器语法树静态检查器语法树中间代码生成器中间代码代码生成器符号表中间语言 (Intermediate Representation) 后缀表达式图表示三地址码静态单赋值中间代码生成声明语句 ( 更新符号表 ) 表达式赋值语句 ( 产生临时变量查询符号表 ) 布尔表达式控制流语句 ( 标号 / 回填短路计算 ) 2018/11/12 Compiler, USTC,

5 主要内容记号流分析器语法树静态检查器语法树中间代码生成器中间代码代码生成器符号表中间语言 (Intermediate Representation) 后缀表达式图表示三地址码静态单赋值中间代码生成声明语句 ( 更新符号表 ) 表达式赋值语句 ( 产生临时变量查询符号表 ) 布尔表达式控制流语句 ( 标号 / 回填短路计算 ) 2018/11/12 Compiler, USTC,

6 为什么需要中间语言? 实践过程中, 推陈出新的语言不断涌现的指令集开发成本之间的权衡 2018/11/12 Compiler, USTC,

7 后缀表示 uop 是一元运算符 E E ope uope (E) id num 表达式 E id num E 1 op E 2 uope (E) 后缀式 E id num E 1 E 2 op E uop E 2018/11/12 Compiler, USTC,

8 后缀表示后缀表示不需要括号 (8 5) + 2 的后缀表示是后缀表示的最大优点是便于计算机处理表达式计算栈输入串 /11/12 Compiler, USTC,

后缀表示后缀表示不需要括号 (8 5) + 2 的后缀表示是 8 5 2 + 后缀表示的最大优点是便于计算机处理表达式后缀表示的表达能力

9 后缀表示后缀表示不需要括号 (8 5) + 2 的后缀表示是后缀表示的最大优点是便于计算机处理表达式后缀表示的表达能力可以拓广到表示赋值语句和控制语句但很难用栈来描述控制语句的计算 2018/11/12 Compiler, USTC,

10 图形表示语法树是一种图形化的中间表示 assign a + + uminus c d c d b (a) 语法树 a = ( b + c d) + c d 的图形表示 2018/11/12 Compiler, USTC,

11 图形表示语法树是一种图形化的中间表示 assign a + + uminus c d c d b (a) 语法树 c*d 是公共子表达式 a = ( b + c d) + c d 的图形表示 2018/11/12 Compiler, USTC,

12 图形表示语法树是一种图形化的中间表示有向无环图 (Directed Acyclic Graph, DAG) 也是一种中间表示 assign a + + uminus c d c d b (a) 语法树 DAG 中的一个结点 N 可能有多个父结点 assign a + + uminus c d b (b) DAG a = ( b + c d) + c d 的图形表示 2018/11/12 Compiler, USTC,

13 图形表示构造赋值语句语法树的语法制导定义 ( 第四章内容 ) 修改构造结点的函数可生成有向无环图产生式 S id =E E E 1 +E 2 E E 1 E 2 E E 1 E (E 1 ) F id 语义规则 S.nptr = mknode( assign, mkleaf (id, id.entry), E.nptr) E.nptr = mknode( +, E 1.nptr, E 2.nptr) E.nptr = mknode(, E 1.nptr, E 2.nptr) E.nptr = mkunode( uminus, E 1.nptr) E.nptr = E 1.nptr E.nptr = mkleaf (id, id.entry) 2018/11/12 Compiler, USTC,

14 三地址代码三地址代码 (three-address code) 一般形式 :x = y op z 最多一个算符最多三个计算分量每一个分量代表一个地址, 因此三地址例表达式 x + y z 翻译成的三地址语句序列 t 1 = y z t 2 = x + t /11/12 Compiler, USTC,

15 三地址代码三地址代码是语法树或 DAG 的一种线性表示例 a = ( b + c d ) + c d 语法树的代码 t 1 = b t 2 = c d t 3 = t 1 + t 2 t 4 = c d t 5 = t 3 + t 4 a = t 5 uminus 2018/11/12 Compiler, USTC,

16 三地址代码三地址代码是语法树或 DAG 的一种线性表示例 a = ( b + c d ) + c d 语法树的代码 DAG 的代码 t 1 = b t 1 = b t 2 = c d t 2 = c d t 3 = t 1 + t 2 t 3 = t 1 + t 2 t 4 = c d t 4 = t 3 + t 2 t 5 = t 3 + t 4 a = t 4 a = t 5 + uminus c b assign a + d 2018/11/12 Compiler, USTC,

17 三地址代码常用的三地址语句赋值语句 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 2018/11/12 Compiler, USTC,

18 三地址代码的实现方式三地址代码只说明了指令的组成部分, 为描述其在编译器中的具体数据结构实现常见的实现方式有三种 : 四元式 : (op, arg1, arg2, result) 三元式 : (op, arg1, arg2) 间接三元式 : ( 三元式的指针表 ) 2018/11/12 Compiler, USTC,

19 三地址代码的实现方式四元式 (Quadruple) 例 :a = b * c + b * c 缺点 : 临时变量太多, 增加时间和空间成本 2018/11/12 Compiler, USTC,

20 三地址代码的实现方式三元式 (Triple) 例 :a = b * c + b * c 缺点 : 隐式的临时变量, 代码位置调整会造成引用该位置的代码也要修改 2018/11/12 Compiler, USTC,

21 三地址代码的实现方式间接三元式 (Indirect triple) 例 :a = b * c + b * c 指令序列可以任意调整顺序优势 : 比四元式空间开销小, 比三元式更灵活 2018/11/12 Compiler, USTC,

22 三地址代码的实现方式总结四元式按编号次序计算计算结果存于 result 方便移动, 计算次序容易调整大量引入临时变量三元式按编号次序计算由编号代表不方便移动在代码生成时进行临时变量的分配间接三元式按编号次序计算方便移动, 计算次序容易调整在代码生成时进行临时变量的分配 2018/11/12 Compiler, USTC,

23 静态单赋值形式一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量的赋值三地址代码静态单赋值形式 p = a +b p 1 = a +b q = p c q 1 = p 1 c p = q d p 2 = q 1 d p = e p p 3 = e p 2 q = p + q q 2 = p 3 + q /11/12 Compiler, USTC,

24 静态单赋值形式一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量的赋值一个变量在不同路径上都定值的解决办法 if (flag) x = 1; else x = 1; y = x a; 改成 if (flag) x 1 = 1; else x 2 = 1; x 3 = (x 1, x 2 ); // 由 flag 的值决定用 x 1 还是 x /11/12 Compiler, USTC,

25 主要内容记号流分析器语法树静态检查器语法树中间代码生成器中间代码代码生成器符号表中间语言 (Intermediate Representation) 后缀表达式图表示三地址码静态单赋值中间代码生成声明语句 ( 更新符号表 ) 表达式赋值语句 ( 产生临时变量查询符号表 ) 布尔表达式控制流语句 ( 标号 / 回填短路计算 ) 2018/11/12 Compiler, USTC,

26 中间代码生成的关键问题类型与符号表的变化多样化类型 => 整型 ( 字节字 ) 浮点型类型符号表 1 个某类型的数据 => m 个字节 (m 为类型对应的字宽 ) 语句的翻译声明语句 : 不生成指令, 但会更新符号表 ( 作用域, 字宽及存放的相对地址 ) 赋值语句 : 引入临时变量数组 / 记录元素的地址计算类型转换控制流语句 : 跳转目标的确定 ( 引入标号或使用回填技术 ) 短路计算 2018/11/12 Compiler, USTC,

27 符号表的设计类型检查后的符号表符号表条目 :( 标识符存储类别类型信息 ) 存储类别 :extern, static, register, 类型信息 :( 类别标识, 该类别关联的其他信息 ) 如数组 (Array,(len, elemtype)) 本章符号表的变化作用域 => 多个符号表变量 : 字宽存储的相对地址 ( 以字节为单位 ) 记录类型 : 用符号表管理各个成员的字宽相对地址 2018/11/12 Compiler, USTC,

28 声明语句的翻译一般不产生代码 ; 仅将有关变量的属性填入符号表 ( 如类型存储偏移位置 -offset) 例 : 文法 G 1 如下 : P D D D ; D D id : T T int real array [ number ] of T 1 T /11/13 编译原理与技术讲义 28

29 声明语句的翻译 - 有关符号的属性 T.type - 变量所具有的类型, 如整型 INT 实型 REAL 数组类型 array( 元素个数, 元素类型 ) 指针类型 pointer( 所指对象类型 ) T.width - 该类型数据所占的字节数 offset - 变量的存储偏移地址 2018/11/13 编译原理与技术讲义 29

30 声明语句的翻译 T.type T.width 整型 INT 4 实型 REAL 4 数组 array(number, T 1 ) number.val * T 1.width 指针 pointer(t 1 ) 4 enter(name,type,offset)- 将类型 type 和偏移 offset 填入符号表中 name 所在的表项 2018/11/13 编译原理与技术讲义 30

31 声明语句的翻译 (1)P M D (2)D D 1 ; D 2 (3)D id : T { // 填入变量的相关属性 enter( id.name, T.type, offset) // 计算下一可用偏移位置 offset = offset + T.width } (4)M { offset := 0 // 偏移初始为 0} 2018/11/13 编译原理与技术讲义 31

32 声明语句的翻译 (5)T int { T.type := INT; T.width := 4 } (6)T real { T.type := REAL; T.width := 4 } (7)T array [ number ] of T 1 { T.type := array( number.val, T 1.type); T.width := number.val * T 1.width } (8)T pointer( T 1 ) { T.type := pointer( T 1.type) ; T.width := 4 } 2018/11/13 编译原理与技术讲义 32

33 编译原理与技术中间代码生成 Ⅰ TBA

Microsoft PowerPoint - ch7.ppt [兼容模式]

Microsoft PowerPoint - ch7.ppt [兼容模式] 第七章中间代码生成静态中间代码记号分析检查代码中间生成流器器生成代码器器本章内容介绍几种常用的中间表示 (intermediate representation): 后缀表示图形表示和三地址代码用语法制导定义和翻译方案来说明源语言的各种用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 7.1.1 后缀表示 7.1 中间语言 E E ope uope (E) id num