Microsoft PowerPoint - 1-Introduction12.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 1-Introduction12.ppt [兼容模式]"

称施
5 years ago
Views:

1 课程简介 Principles of Compiler Yinliang Zhao Xi an Jiaotong University 2012 本课程内容介绍把高级语言程序转换为低级语言程序的原理和实现技术本课程目的是为计算机科学与技术专业的本科生系统地介绍程序分析变换运行管理及优化等技术旨在培养学生解决程序构造和处理的能力, 所学知识在编译器设计实现程序分析与验证程序转换和优化等应用中均能发挥作用 2 任课教师情况教学安排 Instructor: 赵银亮教授联系方式 :yinliang_zhao@163.com 办公室 : 西一楼 411 室, 电话 T:3 人与编译有关的研究背景 : Lisp 机 Lisp_M1 系统 ( ) Common Lisp Object System 实现 ( ) 并行程序性能分析 ( ) C 语言交叉编译器 ( ) DSP C 编译系统 ( ) 推测多线程编译技术 ( ) 总学时课内学时 44 56, 主要讲授大纲中的知识点上机实验 8, 将安排具体题目, 提交结果辅导答疑, 每周四下午 4-6 点西一楼 411 室综合成绩 : 平时成绩 20%, 包括上机作业和课堂笔记上机 : 由班长去计算机系实验中心登记作业 : 指定时间提交, 过后不补课堂笔记 : 期末统一收缴后检查并评分期末考试 80% 3 4 线程级推测模型及编译优化方法 ( ) 1

2 教材及参考书陈火旺等. 程序设计语言编译原理 ( 第 3 版 ). 国防工业出版社. Kenneth C. Louden. Compiler Construction: Principles and Practice ( 英文版 1997). 机械工业出版社, 2002 lfred V. ho, Ravi Sethi, Jeffrey D. Ullman. Compilers :principles, techniques, and tools(2001) 有翻译本 : 南大赵建华等译. 编译原理. 机械工业, 下载区与讨论区邮件联系方式联系方式 :xjtucompiler2012@163.com 课件及资料下载问题讨论等 : 用密码 xjtucompiler 打开上述邮箱可以下载资料有问题发邮件到上述邮箱回答问题或讨论也可以使用这个邮箱进行 5 6 第一章, 第二章, 第三章, , 第四章, 第五章, 5.1, 5.2*, 5.3,5.4 1 第六章, , -* 第七章, 第八章, 第九章, , 9.6* 第十章, , 11.4* 主要教学内容引论形式语言简介词法分析自顶向下语法分析自底向上语法分析属性文法中间代码生成符号表运行时存储空间组织代码优化寄存器分配注意 : 讲课内容与教材内容不是严格一致, 对于一些内容, 课件中讲得更深入细致, 另一些内容则相比教材更简略, 总体服从大纲要求 7 几点说明先修课程 : 离散数学数据结构程序设计语言形式语言与自动机学习本课程的目标 : 理解编译过程 ; 能够编写简单的编译程序 ; 有进行程序分析变换评价的基础学习的途径 : 原理入手 ( 掌握知识点 ); 掌握相关理论方法和技术方法 ; 多做练习本课程的编程实验推荐采用 C 或 Java 编程进行 8 2

3 第一章引论基本概念什么叫编译程序编译过程概述编译程序的结构及生成编译程序是一个程序, 该程序将用某个语言写的程序 ( 称为源程序 ) 作为输入, 并翻译成为功能上等价的另一个语言程序 ( 称为目标程序 ). 源语言通常是高级语言, 如 C, Fortran 等 ; 目标语言通常是低级语言如汇编或机器语言 ; 随着翻译的进行, 编译程序也报告错误信息以帮助程序员改错, 直到翻译通过为止. 9 源语言源程序 if(a==b) a=2; b=4;... 输入编译器词法分析语法分析语义处理代码生成代码优化错误及警告实现语言目标程序 mov a, R1 mov b, R2... 输出目标语言 10 几个注意的问题语言的抽象层次 1 源语言是高级语言, 目标语言是低级语言时? 源语言和目标语言任意时? 编译器 / 翻译程序 2 书写编译器的语言可以是高级语言也可以是低级语言. 用什么语言编写编译器无关紧要 3 运行编译器的机器跟运行目标程序的机器可以相同也可以不同. 编译器 / 交叉编译器宿主机 / 目标机 11 机器语言 : 汇编语言 : 高级语言 : 能够被计算机的硬件直接执行的指令程序将硬件指令用一些助记符表示如 DD 表示加法操作, SUB 表示减法操作等等相对于前二者而言且更接近于自然语言的程序设计语言 Properties: need to be precise need to be concise need to be expressive need to be at a high-level (lot of abstractions) 12 3

4 编译器的种类诊断编译程序侧重于错误信息, 帮助开发调试优化编译程序侧重于提高代码效率交叉编译程序宿主机和目标机不是同一个机器可变目标编译程序仅定制编译器中跟机器有关部分实现针对新目标机的代码生成解释器和编译器特点概念上的不同 ( 翻译 / 直接执行 ) 基于解释执行的程序可以动态修改自身, 而基于编译执行的程序动态性较弱基于解释方式有利于人机交互基于解释执行的速度较慢解释器需要保存的信息较多, 空间开销大二者实现技术相似编译过程概述 for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 编译过程源程序 ( 字符流 ) 词法分析单词符号 (Token 流 ) 语法分析语法单位 ( 语法树 Parse 树 ) 语义分析中间表示代码优化优化的中间表示代码生成 15 目标代码 ( 汇编代码 ) 16 4

5 Step1 词法分析依循语言的词法规则, 扫描源程序的字符串, 识别每一个单词, 并将其表示成内部表示形式, 即 TOKEN. Step1 词法分析 val#ue 源程序字符流 : 不是数变量名不能有 # 字符 TOKEN 流 : Num(234) mul_op lpar_op Num(11) add_op Num(-22) rpar_op 17 文法 ; 正规式 ; 有限自动机 18 Token 例子例子标识符 ( 用户定义的名字 ); identifier 保留字 ( 关键字 / 基本字 ); reserved words 常数 ( 整数, 双精度数, 浮点数 );constant 界符 ( 分隔符 ); delimiters 运算符 ( 操作符 ); operators < 种属, 值 > b e g i n v a r x 1 : r e a ; v a r z 1 : r e a l ; x : = 0. 5 ; z 1 : = x w r i t e ( z ) ; e a d ( V 1 ) ; z 1 : = z e n d. # l 1 ; r x 19 源程序在文件中的表示 20 5

6 Step2 语法分析 ($begin ($id,z1) ($semi ($line, ($var, ($colon ($line, ($write ($id,x1) ($real ($id,z1) $Lparen ($colon ($semi ($assig ($id,z1) ($real ($line, ($id,x1) ($plus ($semi ($id,x1) ($plus ($realc,5.5) ($line, $assig ($intc, 55) $Rparen ($var, ($realc, 0.5) ($semi, ($semi, 依据语言的语法规则, 将单词的 Token 序列转化为语法单位 ( 语法范畴 )( 短语子句句子程序段程序 ), 并确定整个输入串是否构成一个语法上正确的程序确定 Token 之间有什么关系 ($line, ($read $Lparen ($id,x1) $Rparen ($semi ($line, ($id,z1) ($assig ($id,z1) ($plus ($id,x1) ($end ($stop # 词法分析后的 TOKEN 表示 Token 流 : num * ( num + num ) 语法树 : <expr> num <expr> <op> 语法分析 <expr> 规约 ; ( * <expr> ) LL(1) 分 <expr> <op> 析法 <expr> LR 分析法 num + num 文法 ; 语法树 ; 推导 ; 23 语法分析 int * foo(i, j, k)) int j; for(i=0; i j) fi(i>j) return j; 不是保留字不是表达式多余的括号缺少步长 24 6

7 Step3 语义分析语义分析对语法分析所识别出的各类语法范畴, 分析其含义, 查错, 并产生源程序所对应的中间表示 ( 中间代码 ) 确定整体结构的含义属性文法 ; 语义函数 int * foo(i, j, k) int j; int x; x = x + j + N; return j; 类型未说明变量未说明返回结果类型不匹配使用了没有初始化的变量 for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; Step4 优化 int x, t, u, v; u = (a<<2/b); v = 0; for(i = 0; i <= N; i++) x = x + v + t*t; v = v + u; Constant Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 程序等价变换 ; 控制流数据流分析 7

8 Constant Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; lgebraic Simplification for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; lgebraic Simplification for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x; Copy Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x;

9 Copy Propagation for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); Common Subexpression Elimination for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); Common Subexpression Elimination Dead Code Elimination int x, y, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; 35 int x, y, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; 36 9

10 Dead Code Elimination int x, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Loop Invariant Removal int x, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Loop Invariant Removal int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) x = x + u*i + t*t; Strength Reduction int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) x = x + u*i + t*t;

11 Strength Reduction int x, t, u, v; u = (a<<2/b); v = 0; for(i = 0; i <= N; i++) x = x + v + t*t; v = v + u; 41 Step5 代码生成中间代码变换为特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码

12 1.3 编译程序的结构及生成源程序表格管理表格管理出错处理遍前端与后端 T 型图表格管理词法分析单词符号语法分析语法单位中间代码生成中间代码代码优化中间代码出错处理表格的作用和种类保存编译各阶段的有用信息符号表常数表保留字表其他表格操作关注方便性和时空效率目标代码生成目标代码出错处理一遍与多遍编译语法错误不符合语法 ( 或词法 ) 规则的错误单词拼写错误括号不匹配等语义错误不符合语义规则的错误说明错误作用域错误类型不匹配等是对源程序或编译中间结果从头到尾扫描一次, 并做有关的加工处理, 生成新的中间结果或目标程序注意各遍间的中间结果 ( 内部形式外部形式 ) 全最大限度发现错误准准确指出错误的性质和发生地点局部化将错误的影响限制在尽可能小的范围内 47 One-pass compiler: Type of software compiler that passes through the source code only once. One-pass compilers are faster, but may not generate an as efficient program. In addition, one-pass compilers cannot compile all types of source codes

13 编译前端与后端前端指跟目标机无关的部分, 一般包括 : 词法语法语义分析 ; 后端指跟目标机有关的部分, 一般包括优化和代码生成 ; 前后端之间的接口 : 中间表示符号表

14 T 型图用高级语言 L 构造编译程序 S I T S Source Language T Target Language I Implementation Language 由用 I 语言写的编译程序把用 S 语言写的源程序翻译成用 T 语言写的目标程序 53 P L L 将写好的语言 P 的编译程序用 L 的编译程序编译后就可得到用机器代码实现的 P 编译程序 P 54 编译程序的移植自编译方式 L (2) L B (2) L L B (3) L B (4) B B 先对语言的核心部分构造一个小小的编译程序 ( 可用低级语言实现 ) 再以它为工具构造能编译更多语言成分的较大编译程序如此不断扩展, 最后形成整个编译程序 ( 滚雪球 ) L L (1) 将至此再将 (2), (2) 用将 L (1) 编写能在用机器上的 (3) 编译编译, B 得到机, L 的编即可机译程序器上运行的产生得到已有 B 机器上运行的产生 (1) 机器上的高级移植为 B B L 代码的的语 LB 代码的的 L 言的编译程序 L (2) (3) (1) (4) (4)

15 构造工具构造编译程序的工具称为编译程序 - 编译程序或编译程序产生器自动产生扫描器 LEX FLEX 自动产生语法分析器 YCC BISON Java 编译器的编译器 Jastdd 编译技术的应用高级程序设计语言的实现语言特征与编译优化动态编译针对计算机体系结构的优化并行性存储层次结构新计算机体系结构的设计 RISC 与专用体系结构程序翻译软件生产率工具小结理论方法 : 形式语言与自动机属性文法数据流分析等编译技术 : 词法语法语义分析方法, 代码生成与优化方法编译程序构造 : 编译器结构典型算法数据结构课程内容主要涉及编译器前端本章练习概要了解编译过程的内容和特点掌握交叉编译器 T 形图概念查阅维基百科词条, 了解概念 programming language compiler

Microsoft PowerPoint - 1-Introduction.ppt

Microsoft PowerPoint - 1-Introduction.ppt 任课教师情况编译原理 Principles of Compiler 赵银亮教授联系方式 :zyl9910@mail.xjtu.edu.cn 辅导老师 : 李聪王旭昊张长军韦远科赵银亮 2008 年秋与编译有关的研究背景 : isp 机 isp_m1 系统 (1987-90) Common isp Object System 实现 (1990-95) 并行程序性能分析 (1996-98)