Microsoft PowerPoint - 1-Introduction09.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 1-Introduction09.ppt"

霹幻汤
5 years ago
Views:

课程简介 Principles of Compiler Yinliang Zhao Xi an Jiaotong University 2009 本课程内容介绍把高级语言程序转换为低级语言程序的原理和实现技术本课程目的是为计算机科学与技术专业的本科生系统地介绍程序分析变换运行管理及优化技术旨在培养学生解决程序构造和处理的能力, 所学知识在编译器设计实现程序分析与验证

1 课程简介 Principles of Compiler Yinliang Zhao Xi an Jiaotong University 2009 本课程内容介绍把高级语言程序转换为低级语言程序的原理和实现技术本课程目的是为计算机科学与技术专业的本科生系统地介绍程序分析变换运行管理及优化技术旨在培养学生解决程序构造和处理的能力, 所学知识在编译器设计实现程序分析与验证程序转换和优化等应用中均能发挥作用 2 任课教师情况教学安排 Instructor: 赵银亮教授联系方式 :zhaoyinliang@gmail.com 办公室 : 西一楼 411 室 T: 赵恒星李挺王一群与编译有关的研究背景 : isp 机 isp_m1 系统 ( ) Common isp Object System 实现 ( ) 并行程序性能分析 ( ) C 语言交叉编译器 ( ) DSP C 编译系统 ( ) SpMT 编译技术 (2006-) 总学时 64 课内学时 56, 主要讲授大纲中的知识点上机实验 8, 将安排具体题目, 提交结果辅导答疑, 每周四下午 3-5 点西一楼 411 室综合成绩 : 上机 10% ( 由各班长去计算机系实验中心登记上机时间 ) 作业 10% 指定时间提交, 过后不补考试 80% 3 4 Granule-Oriented Programming(-) 教材及参考书陈火旺等. 程序设计语言编译原理 ( 第 3 版 ). 国防工业出版社. Kenneth C. ouden. Compiler Construction: Principles and Practice ( 英文版 1997). 机械工业出版社, 2002 lfred V. ho, Ravi Sethi, Jeffrey D. Ullman. Compilers :principles, techniques, and tools(2001) 有翻译本 : 南大赵建华等译. 编译原理. 机械工业, 下载区与讨论区邮件联系方式联系方式 :zhaoyinliang@gmail.com 课件及资料下载问题讨论等 : Yinliang Zhao ( 赵银亮 ) 1

下载区与讨论区 (cont.) There is a Google discussion group for the class at http://groups.google.com/group/xjtucompiler-course-2009.

2 下载区与讨论区 (cont.) There is a Google discussion group for the class at ll students are expected to join this group and to watch it for course announcements. You may also use it to post questions (of general interest to the class) for the instructor and assistant. You may answer questions asked by other students if you are sure that you find right results of the questions. 7 8 主要教学内容几点说明第一章, 第二章, 第三章, , 3.4* 第四章, 第五章, 5.1, 5.2*, 5.3* 第六章, , -* 第七章, 第八章, 第九章, , 9.6* 第十章, , 11.4* 引论形式语言简介词法分析自顶向下语法分析自底向上语法分析属性文法中间代码生成符号表运行时存储空间组织代码优化寄存器分配先修课程 : 离散数学数据结构程序设计语言学习本课程的目标 : 理解编译过程 ; 能够编写编译程序 ; 有进行程序分析变换评价的基础学习的途径 : 原理入手 ( 掌握知识点 ); 掌握相关理论方法和技术方法 ; 多做练习本课程的编程实验推荐采用 C 或 Java 编程 9 10 第一章引论基本概念什么叫编译程序编译过程概述编译程序的结构及生成编译程序是一个程序, 该程序将用某个语言写的程序 ( 称为源程序 ) 作为输入, 并翻译成为功能上等价的另一个语言程序 ( 称为目标程序 ). 源语言通常是高级语言, 如 C, Fortran 等 ; 目标语言通常是低级语言如汇编或机器语言 ; 随着翻译的进行, 编译程序也报告错误警告信息以帮助程序员改错, 直到翻译通过为止. 11 源语言源程序 if(a==b) a=2; b=4;... 输入编译器词法分析语法分析语义处理代码生成代码优化错误及警告实现语言目标程序 mov a, R1 mov b, R2... 输出目标语言 12 Yinliang Zhao ( 赵银亮 ) 2

3 1 源语言是高级语言, 目标语言是低级语言时? 源语言和目标语言任意时? 编译器 / 翻译程序 2 书写编译器的语言可以是高级语言也可以是低级语言. 用什么语言编写编译器无关紧要 3 运行编译器的机器跟运行目标程序的机器可以相同也可以不同. 编译器 / 交叉编译器几个注意的问题宿主机 / 目标机 13 语言的抽象层次机器语言 : 能够被计算机的硬件系统直接执行的指令程序汇编语言 : 将硬件指令用一些助记符表示如 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) 14 编译器的种类诊断编译程序侧重于错误信息, 帮助开发调试优化编译程序侧重于提高代码效率交叉编译程序宿主机和目标机不是同一个机器可变目标编译程序仅定制编译器中跟机器有关部分实现针对新目标机的代码生成解释器和编译器特点概念上的不同 ( 翻译 / 直接执行 ) 基于解释执行的程序可以动态修改自身, 而基于编译执行的程序动态性较弱基于解释方式有利于人机交互基于解释执行的速度较慢解释器需要保存的信息较多, 空间开销大二者实现技术相似编译过程概述 int x, y; y = 0; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 17 编译过程源程序 ( 字符流 ) 词法分析单词符号 (Token 流 ) 语法分析语法单位 ( 语法树 Parse 树 ) 语义分析中间表示代码优化优化的中间表示代码生成目标代码 ( 汇编代码 ) 18 Yinliang Zhao ( 赵银亮 ) 3

4 Step1 词法分析依循语言的词法规则, 扫描源程序的字符串, 识别每一个单词, 并将其表示成内部表示形式, 即 TOKEN. Step1 词法分析 val#ue 源程序字符流 : 不是数变量名不能有 # 字符 TOKEN 流 : Num(234) mul_op lpar_op Num(11) add_op Num(-22) rpar_op 文法 ; 正规式 ; 有限自动机 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 21 源程序在文件中的表示 22 Step2 语法分析 ($begin ($id,z1) ($semi ($var, -) ($colon ($id,x1) ($real ($id,z1) ($colon ($semi ($assig ($real ($id,x1) ($semi ($id,x1) ($plus $assig ($intc, 55) ($var, -) ($realc, 0.5) ($semi, -) 依据语言的语法规则, 将单词的 Token 序列转化为语法单位 ( 语法范畴 )( 短语子句句子程序段程序 ), 并确定整个输入串是否构成一个语法上正确的程序 ($write $paren ($id,z1) ($plus ($realc,5.5) $Rparen ($semi, -) ($read $paren ($id,x1) $Rparen ($semi ($id,z1) ($assig ($id,z1) ($plus ($id,x1) ($end ($stop # 词法分析后的 TOKEN 表示 Yinliang Zhao ( 赵银亮 ) 4

5 语法分析文法 ; Token 流 : num * ( num + num ) 语法树 ; 语法树 : <expr> 推导 ; 规约 ; <expr> <op> <expr> (1) 分 num * ( <expr> ) 析法 R 分析法 <expr> <op> <expr> 语法分析 int * foo(i, j, k)) int j; for(i=0; i j) fi(i>j) return j; 多余的括号缺少步长 num + num 25 不是保留字不是一个表达式 26 Step3 语义分析语义分析对语法分析所识别出的各类语法范畴, 分析其含义, 查错, 并产生源程序所对应的中间表示 ( 中间代码 ) 属性文法 ; 语义函数 int * foo(i, j, k) int j; int x; x = x + j + N; return j; 类型未说明变量未说明返回结果类型不匹配使用了没有初始化的变量 int x, y; y = 0; 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++) t = i+1; x = x + v + t*t; v = v + u; Constant Propagation int x, y; y = 0; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; 29 lgebraic Simplification 30 程序等价变换 ; 控制流数据流分析 Yinliang Zhao ( 赵银亮 ) 5

6 lgebraic Simplification int x, y; y = 0; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x; Copy Propagation 31 Copy Propagation int x, y; y = 0; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); Common Subexpression Elimination 32 Common Subexpression Elimination int x, y, t; y = 0; for(i = 0; i <= N; i++) t = i+1; x = x + (4*a/b)*i + t*t; Dead Code Elimination int x, t; for(i = 0; i <= N; i++) t = i+1; x = x + (4*a/b)*i + t*t; Dead Code Elimination 33 oop Invariant Removal 34 oop Invariant Removal int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) t = i+1; x = x + u*i + t*t; Strength Reduction 35 Strength Reduction int x, t, u, v; u = (a<<2/b); v = 0; for(i = 0; i <= N; i++) t = i+1; x = x + v + t*t; v = v + u; 36 Yinliang Zhao ( 赵银亮 ) 6

7 Step5 代码生成中间代码变换为特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码编译程序的结构及生成源程序词法分析单词符号表语法分析出表格管理语法单位格错出错处理中间代码生成遍管中间代码处前端与后端 T 型图理代码优化中间代码理目标代码生成目标代码表格管理表格的作用和种类保存编译各阶段的有用信息符号表常数表保留字表其他表格操作关注方便性和时空效率出错处理语法错误不符合语法 ( 或词法 ) 规则的错误单词拼写错误括号不匹配等语义错误不符合语义规则的错误说明错误作用域错误类型不匹配等全最大限度发现错误准准确指出错误的性质和发生地点局部化将错误的影响限制在尽可能小的范围内 Yinliang Zhao ( 赵银亮 ) 7

一遍与多遍编译是对源程序或编译中间结果从头到尾扫描一次, 并做有关的加工处理, 生成新的中间结果或目标程序注意各遍间的中间结果 ( 内部形式外部形式 ) One-pass compiler: Type of software compiler that passes through the

In addition, one-pass compilers cannot compile all types of source codes. http://www.computerhope.com/jargon/o/onepassc.

8 一遍与多遍编译是对源程序或编译中间结果从头到尾扫描一次, 并做有关的加工处理, 生成新的中间结果或目标程序注意各遍间的中间结果 ( 内部形式外部形式 ) 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 编译前端与后端前端指跟目标机无关的部分, 一般包括 : 词法语法语义分析 ; 后端指跟目标机有关的部分, 一般包括优化和代码生成 ; 前后端之间的接口 : 中间表示符号表 T 型图 S I T S Source anguage T Target anguage I Implementation anguage 由用 I 语言写的编译程序把用 S 语言写的源程序翻译成用 T 语言写的目标程序 Yinliang Zhao ( 赵银亮 ) 8

9 用高级语言构造编译程序编译程序的移植 P 将写好的语言 P 的编译程序用的编译程序编译后就可得到用机器代码实现的 P 编译程序 P (2) B (2) (1) (4) B B (3) B B 将至此再将 (2), (2) 用将 (1) 编写能在用机器上的 (3) 编译编译, B 得到机, 的编即可机译程序器上运行的产生得到已有 B 机器上运行的产生 (1) 机器上的高级移植为 B B 代码的的 B 代码的的语言的编译程序 (2) (3) (4) (1) (4) 自编译方式先对语言的核心部分构造一个小小的编译程序 ( 可用低级语言实现 ) 再以它为工具构造能编译更多语言成分的较大编译程序如此不断扩展, 最后形成整个编译程序 ( 滚雪球 ) 构造工具构造编译程序的工具称为编译程序 - 编译程序编译程序产生器或翻译程序书写系统自动产生扫描器 EX FEX 自动产生语法分析器 YCC BISON 编译过程 :5 个阶段本章小结编译理论是基础 : 形式语言属性文法数据流方程等编译技术是关键 : 各部分的构造编译中的数据结构等课程学习指导具备一定的程序设计语言背景本课程目标机器采用假想指令, 算法描述使用类 PSC 伪码因为编译程序比较复杂, 故讨论中将其分解成各个部分, 学习中应注意前后联系, 多做练习 Yinliang Zhao ( 赵银亮 ) 9

本章练习概要了解编译过程的内容和特点掌握交叉编译器 T 形图概念 55 56 1. Title 1 2. Title 2 3. Title 3 4. Title 4 5. Title 5 6. Title 6 7. Title 7 8. Title 8 9.

10 本章练习概要了解编译过程的内容和特点掌握交叉编译器 T 形图概念 Title 1 2. Title 2 3. Title 3 4. Title 4 5. Title 5 6. Title 6 7. Title 7 8. Title 8 9. Title 9 Contents Related Documents Competitors You may want to allocate one slide per competitor Strengths Your strengths relative to competitors Weaknesses Your weaknesses relative to competitor Chart Documents 1 Chart Documents B C Yinliang Zhao ( 赵银亮 ) 10

11 Diagram 1 Diagram 2 TITE TITE TITE TITE Diagram 1 Diagram 1 Click to edit sub text Diagram 2 Click to edit sub text Diagram 2 Diagram 3 Diagram 3 Click to edit sub text Yinliang Zhao ( 赵银亮 ) 11

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)