Microsoft PowerPoint - 1-Introduction.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 1-Introduction.ppt"

衩紬羞顾
5 years ago
Views:

1 任课教师情况编译原理 Principles of Compiler 赵银亮教授联系方式辅导老师 : 李聪王旭昊张长军韦远科赵银亮 2008 年秋与编译有关的研究背景 : isp 机 isp_m1 系统 ( ) Common isp Object System 实现 ( ) 并行程序性能分析 ( ) C 语言交叉编译器 ( ) DSP C 编译系统 ( ) SpMT 编译技术 (2006-) 教学安排教材及参考书总学时 64 课内学时 56, 主要讲授大纲中的知识点上机实验 8, 将安排具体题目, 提交结果辅导答疑, 每周五下午 3-5 点西一楼 411 室综合成绩 : 上机 10% ( 由各班长于计算机系实验中心登记上机时间 ) 作业 10% 指定时间提交, 过后不补考试 80% 陈火旺等. 程序设计语言编译原理 ( 第 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) 课件及参考资料下载地址 : ftp 用户名和密码均为 parallel 主要教学内容几点说明第一章, 第二章, 第三章, * 第四章, 第五章, * 第六章, 第七章, 第八章, 第九章, 第十章, 引论形式语言简介词法分析自顶向下语法分析自底向上语法分析属性文法中间代码生成符号表运行时存储空间组织代码优化先修课程 : 离散数学数据结构程序设计语言学习本课程的目标 : 理解编译过程 ; 能够编写编译程序 ; 有进行程序分析变换评价的基础学习的途径 : 原理入手 ( 掌握知识点 ); 掌握相关理论方法和技术方法 ; 多做练习本课程的编程实验推荐采用 C 或 Java 编程 Yinliang Zhao 1

2 第一章引论基本概念什么叫编译程序编译过程概述编译程序的结构及生成编译程序是一个程序, 该程序将用某个语言写的程序 ( 称为源程序 ) 作为输入, 并翻译成为功能上等价的另一个语言程序 ( 称为目标程序 ). 源语言通常是高级语言, 如 C, Fortran 等 ; 目标语言通常是低级语言如汇编或机器语言 ; 随着翻译的进行, 编译程序也报告错误或其他警告信息以帮助程序员改错, 直到翻译通过为止. 源语言源程序 if(a==b) a=2; b=4;... 输入词法分析语法分析语义处理代码生成代码优化编译器错误及警告实现语言目标程序 mov a, R1 mov b, R2... 输出目标语言 1 源语言是高级语言, 目标语言是低级语言时? 源语言和目标语言任意时? 编译器 / 翻译程序 2 书写编译器的语言可以是高级语言也可以是低级语言. 3 运行编译器的机器跟运行目标程序的机器可以相同也可以不同. 用什么语言编写编译器无关紧要编译器 / 交叉编译器宿主机 / 目标机语言的抽象层次机器语言 : 能够被计算机的硬件系统直接执行的指令程序汇编语言 : 将硬件指令用一些助记符表示如 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) 编译器的种类诊断编译程序侧重于错误信息, 帮助开发调试优化编译程序侧重于提高代码效率交叉编译程序宿主机和目标机不是同一个机器可变目标编译程序仅定制编译器中跟机器有关部分实现针对新目标机的代码生成解释器和编译器特点概念上的不同基于解释执行的程序可以动态修改自身, 而基于编译执行的程序动态性较弱基于解释方式有利于人机交互基于解释执行的速度较慢解释器需要保存的信息较多, 空间开销大二者实现技术相似 Yinliang Zhao 2

3 1.2 编译过程概述 int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*y; 源程序 ( 字符流 ) 词法分析单词符号 (Token 流 ) 语法分析语法单位 ( 语法树 Parse 树 ) 语义分析中间表示代码优化优化的中间表示编译过程代码生成目标代码 ( 汇编代码 ) 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 源程序在文件中的表示 Yinliang Zhao 3

4 Step2 语法分析 ($begin ($semi ($var, -) ($colon ($real ($colon ($semi ($assig ($real ($semi ($plus $assig ($intc, 55) ($var, -) ($realc, 0.5) ($semi, -) 依据语言的语法规则, 将单词的 Token 序列转化为语法单位 ( 语法范畴 )( 短语子句句子程序段程序 ), 并确定整个输入串是否构成一个语法上正确的程序 ($write $paren ($plus ($realc,5.5) $Rparen ($semi, -) ($read $paren $Rparen ($semi ($assig ($plus ($end ($stop # 词法分析后的 TOKEN 表示 num * ( num + num ) <expr> <expr> num 语法分析 <op> * <expr> ( <expr> ) <expr> <op> <expr> 文法 ; 语法树 ; 推导 ; 规约 ; (1) 分析法 R 分析法语法分析 int * foo(i, j, k)) int j; for(i=0; i j) fi(i>j) return j; 多余的括号缺少步长 num + num 不是保留字不是一个表达式 Step3 语义分析语义分析对语法分析所识别出的各类语法范畴, 分析其含义, 查错, 并产生源程序所对应的中间表示 ( 中间代码 ) 属性文法 ; 语义函数 int * foo(i, j, k) int j; int x; x = x + j + N; return j; 类型未说明变量未说明返回结果类型不匹配使用了没有初始化的变量 Yinliang Zhao 4

5 Step4 优化 int x, y; int x, t, u, v; u = (a<<2/b); for(i = 0; i <= N; i++) v = 0; x = x + (4*a/b)*i + for(i = 0; i <= N; i++) (i+1)*(i+1); x = x + b*y; x = x + v + t*t; v = v + u; 程序等价变换 ; 控制流数据流分析 Constant Propagation int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x + b*0; lgebraic Simplification lgebraic Simplification int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); x = x; Copy Propagation int x, y; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + (i+1)*(i+1); Copy Propagation Common Subexpression Elimination Common Subexpression Elimination int x, y, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Dead Code Elimination int x, t; for(i = 0; i <= N; i++) x = x + (4*a/b)*i + t*t; Dead Code Elimination oop Invariant Removal Yinliang Zhao 5

6 oop Invariant Removal int x, t, u; u = (4*a/b); for(i = 0; i <= N; i++) x = x + u*i + t*t; Strength Reduction 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; Step5 代码生成中间代码变换为特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码指令系统 1.3 编译程序的结构及生成表格管理出错处理遍前端与后端 T 型图表格管理源程序词法分析单词符号语法分析语法单位中间代码生成中间代码代码优化中间代码出错处理目标代码生成目标代码 Yinliang Zhao 6

表格管理表格的作用和种类保存编译各阶段的有用信息符号表常数表保留字表其他表格操作关注方便性和时空效率出错处理语法错误不符合语法 ( 或词法 ) 规则的错误单词拼写错误括号不匹配等语义错误不符合语义规则的错误说明错误作用域错误类型不匹配等全最大限度发现错误准准确指出错误的性质和发生地点局部化

the source code only once. One-pass compilers are faster, but may not generate an as efficient program.

7 表格管理表格的作用和种类保存编译各阶段的有用信息符号表常数表保留字表其他表格操作关注方便性和时空效率出错处理语法错误不符合语法 ( 或词法 ) 规则的错误单词拼写错误括号不匹配等语义错误不符合语义规则的错误说明错误作用域错误类型不匹配等全最大限度发现错误准准确指出错误的性质和发生地点局部化将错误的影响限制在尽可能小的范围内一遍与多遍编译是对源程序或源程序的中间结果从头到尾扫描一次, 并作有关的加工处理, 生成新的中间结果或目标程序注意各遍间的中间结果 ( 内部形式外部形式 ) 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. 编译前端与后端前端指跟目标机无关的部分, 一般包括 : 词法语法语义分析 ; 后端指跟目标机有关的部分, 一般包括优化和代码生成 ; 前后端之间的接口 : 中间表示符号表 Yinliang Zhao 7

8 T 型图 S I T S Source anguage T Target anguage I Implementation anguage 由用 I 语言写的编译程序把用 S 语言写的源程序翻译成用 T 语言写的目标程序用高级语言构造编译程序编译程序的移植 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 Yinliang Zhao 8

9 本章小结编译过程 :5 个阶段编译理论是基础 : 形式语言属性文法数据流方程等编译技术是关键 : 各部分的构造编译中的数据结构等课程学习指导具备一定的程序设计语言背景本课程目标机器采用假想指令, 算法描述使用类 PSC 伪码因为编译程序比较复杂, 故讨论中将其分解成各个部分, 学习中应注意前后联系, 多做练习本章练习概要了解编译过程的内容和特点 Yinliang Zhao 9

Microsoft PowerPoint - 1-Introduction09.ppt

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