《编译程序概论》PPT课件.ppt

1、1,编译原理,主讲： 马 力 单位： 计通学院 计算机科学系 Email: 电话:考核：平时考勤、表现： 10% 平时作业： 20% 期末考试（闭卷）： 70%,2,前 言,课程内容 课程特点 教学安排 学习章节 考试安排,3,课程内容,主要阐述编译程序的基本结构、编译技术的一般理论和常用的有效方法与技术。 包括: 文法和形式语言 自动机理论 词法分析 语法分析 语义分析 中间语言 代码生成,4,理论与实践的结合 理论： 编译基础理论 实践： 自己编写编译器（专门课程设计课） 涉及的知识面广 形式语言 自动机理论 离散数学 数据结构 算 法,课程特点,有,点,难,?,

2、5,教学安排,教学: 48课时 主要采用幻灯片辅导教学 课后作业：从第3章起一般每章交1次，大约5-6次 课终复习、串讲一次 要求：课前预习、课后认真作业,6,学习章节,第一章 编译程序概论(一般了解) 第二章 PL/0编译程序的实现(一般了解) 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析 - LL（1）文法 第六章 自底向上语法分析 -优先分析法 第七章 自底向上语法分析 -LR分析法 第八章 语法制导翻译及代码生成,7,考试安排,考核范围:重点考察编译原理中的基本概念，编译基础理论以及编译过程的各个阶段的功能和实现方法。 考核方式：期末考核与平时成绩相结合的方式。 1）

3、期末考核： 笔试、闭卷，答题时限120分钟，占70%； 2）平时成绩： 视平时考勤、表现、课堂提问、作业完成情况等给分，占30%。 以上成绩累计60分以上（包括60分）算考核通过。,8,参考书,1编译原理（第二版），张素琴、吕映芝、蒋维杜、戴桂兰编著，清华大学出版社，2011年 (教材) 2程序设计语言编译原理（第三版），陈火旺、刘春林等编著，国防工业出版社，2000年 3编译原理与编译程序构造，高仲仪等编著，北京航空航天大学出版社，2001年 4编译原理，胡伦骏、徐兰芳、刘建农编，电子工业出版社，2002年,9,5、龙书（Dragon book）英文名：Compilers: Principl

4、es,Techniques,and Tools作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman中文名：编译原理技术和工具6、虎书（Tiger book）英文名：Modern Compiler Implementation in C作者：Andrew W.Appel,with Jens Palsberg中文名：现代编译原理-C语言描述7、鲸书（Whale book）英文名：Advanced Compiler Design and Implementation作者：Steven S.Muchnick中文名：高级编译器设计与实现,10,第一章 编译程序概论,1.

5、1 什么是编译程序 1.2 编译过程概述 1.3 编译程序的结构 1.4 编译技术的发展和应用,11,1.1 什么是编译程序(compiler),一、基本概念 1. 编译程序 编译程序是现代计算机系统的基本组成部分。 从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。,12,程序设 计语言,低级语言,高级语言,汇编语言,机器语言,翻译 程序,翻译 程序,2.程序设计语言及其翻译,源程序,目标程序,翻译程序,13,翻译程序Translator,汇编程序 Assembler,编译程序 Compiler,解释程序 Inte

6、rpreter,高级语言,3.翻译程序,14,4. 高级语言程序处理的两种方法,(1) 编译途径 方法一：,源程序,运行程序,目标程序,编译程序,结果,初始数据,编译阶段,运行阶段,15,4.高级语言程序处理的两种方法,(1) 编译途径 方法二：,源程 序,运行程序,目标 代码,编译程序,结 果,初始数据,编译阶段,运行阶段,汇编语言,汇编程序,汇编阶段,16,(2) 解释途径,源程序,结果,解释程序,初始数据,直接解释执行、中间代码,与编译的主要区别：解释程序不产生目标代码,4.高级语言程序处理的两种方法,17,编译程序 vs. 解释程序,编译,解释,18,二、编译程序的功能,功能,术语 编

7、译程序的源语言(源程序S) 编译程序的目标语言(目标程序O、T) 编译程序的实现语言(I),高级语言 书写的程序,编译程序,低级语言程序,19,三、编译程序在软件中的地位,软件 系统软件 语言处理系统,1.属于系统软件类,20,2.计算机软件相关概念 (1) 软件：计算机系统中的程序及其文档 (2)系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。 (3)语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。 (4)软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语

8、言以及文档语言。,21,预处理器,编译器,汇编器,装配连接编辑,骨架程序,源程序,目标汇编程序,可重定位机器代码,绝对机器码,可重定位目标文件库,3.语言处理过程,22,编译工作重要贡献者,Grace Hopper ，计算机软件的第一夫人 Hopper“全美技术奖 。1952年，世界上第一个将高级符号语言转变为机器语言的编译，COBOL语言和编译器。 John Cocke ，“IBM小子” 1987图灵奖，高性能计算机的体系结构方面（RISC） ，编译器的优化方面的贡献。 A.J. Perlis 1966图灵奖，获奖原因：在先进编程技术和编译架构方面的贡献。,23,1.2 编译过程概述,24,

9、把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。,词法分析,语法分析（含语义）,中间代码生成,优化,目标代码产生,举例,25,编译逻辑过程: 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 编译辅助工作: 表格管理 出错处理,26,1. 词法分析,扫描源程序的ASCII码序列,拼出每一个单词,并把每个单词的ASCII码序列替换为所谓的机内表示TOKEN形式，这时还检查词法错误。但词法分析阶段不依靠语法关系。 简单地说，就是从左至右读字符流的源程序、识别(拼)单词。 例： position =

10、 initial + rate * 60;,27,词法分析 position = initial + rate * 60;,单词类型单词值 标识符1(id1) position 算符(赋值) = 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号 ；,28,又如一个C源程序片断： int a; a = a + 2; 词法分析后可能返回: 单词类型单词值 保留字 int 标识符(变量名) a 界符 ; 标识符(变量名) a 算符(赋值) = 标识符(变量名) a 算符(加) + 整数 2 界符 ；,29,2. 语法分析,功能：层次分

11、析。依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树). 扫描对象可能是源程序的ASCII码序列，也可能是词法分析后的TOKEN序列。主要任务是检查源程序的形式语法错误,每当发现错误时将输出有关信息。 position = initial + rate * 60 ; 规则 :=“=” :=“+” :=“*” :=“(”“)” := := :=,30,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,=,表达式,*,31,id1=id2+id3*N,32,3.语义分析,语义审查(静态语义) 上下文相关性 类型匹配 类型转换,例:main p(); flo

12、at rate; void initial; position = initial + rate * 60; /* error */ /* error */ /* warning */; ,33,又如: int arr 2,abc; abc = arr * 10; main p(); float rate; float initial; float position ; position = initial + rate * 60;,34,语义分析例：,35,4.中间代码生成,扫描对象通常是语法分析后的结果，这部分把源程序的TOKEN序列转换成更接近目标代码的中间代码三元式或四元式的序列。 源

13、程序的内部(中间)表示： 后缀式、三元式、四元式、树、波兰式、逆波兰式等 例如： 后缀式：ab+c* 表示(a+b)*c 三元式： ( *，id3，t1) 四元式： ( *，id3，t1，t2),36,中间代码生成例：,id1= id2 + id3 * 60 (1)(inttoreal,60-t1) (2)(*,id3t1t2) (3)(+,id2t2t3) (4)(=,t3-id1),37,5.代码优化,按代码级别，可分成源代码优化、中间代码优化和目标代码优化三种。 其中：中间代码优化扫描对象是中间代码,任务是把优化前的中间代码转换成可产生高质量目标代码的中间代码。 优化工作包括表达式优化、

14、公共子表达式优化、不便表达式外提和削减运算强度等。,38,代码优化例：,t1 = b* c t1 = b* c t2 = t1+ 0 优化后： a= t1 + t1 t3 = b* c t4 = t2 + t3 a = t4,39,6.目标代码生成,(*,id3，60.0，t1) (+,id2，t1，id1),movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1,扫描对象是中间代码，任务是从中间代码产生目标代码，这一部分的工作与目标机紧密相关，其它部分的工作几乎与目标机无关。,40,7.表格管理,较大的编译程序用到很多表格，甚至可达几十

15、种表。不少编译程序都设立一些专门子程序（称为表格管理程序），它们专门负责管理表格。 记录源程序中使用的名字 收集每个名字的各种属性信息，包括： 类型、作用域、分配存储信息， 例如： Const1常量值：35 Var1变量类型：实,41,8.出错处理,出错处理包括词法错误、语法错误、静态语义错误、动态语义错误等； 出错处理模块的作用是：检查错误、报告出错信息、排错、恢复编译工作。,42,1.3 编译程序的结构 (components),词法分析程序 语法分析程序 语义分析程序 中间代码生成程序 代码优化程序 目标代码生成程序 符号表管理程序 出错处理程序,43,出 错 处 理,表 格 管 理,4

16、4,1.4 编译技术的发展和应用,一、实现方式 手工 机器语言 汇 编 系统程序设计语言 自动构造工具 lex yacc 分类：命令行 集成环境,45,二、程序设计语言范型,1. 命令式（过程式）： 程序特点： 语句1； 语句2； 语句3； 与冯诺曼机的体系结构一致,46,2.应用式（函数式） 程序特点： Function n(funetion2(funetion1(data) 程序执行： 执行一个个函数施用在数据上的变换最终得到的结果 编译： 语法分析容易； 语义处理复杂。,二、程序设计语言范型,47,3.基于规则的语言（prolog, yacc)： 程序特点： 使能条件1 动作1 使能条件

17、2 动作2 使能条件3 动作3 4. 面向对象语言： 抽象数据类型，继承机制 编译： 动态绑定；,二、程序设计语言范型,48,三、执行环境,批处理环境：将源程序作为整体处理 排除程序错误不能依靠用户的外部帮助 交互环境：解释 增量式编译 嵌入式系统环境：交叉编译 分布并行环境： 并行编译 程序创建和测试环境： 独立编译 编译和调试同时设计考虑,49,高级语言的实现 高级编程语言易于编程，但程序运行较慢 低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护 流行编程语言的大多数演变都是朝着提高抽象级别的方向 每一轮编程语言新特征的出现都刺激编译器优化的新研究,四、编译

18、技术的应用,50,高级语言的实现 每一轮编程语言新特征的出现都刺激编译器优 化的新研究 支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran 面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java 类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存 Java设计来支持代码移植和代码移动,四、编译技术的应用,51,针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化 编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上 内存分层 编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效,四、编译技术的应用,52,新计算机体系结构的设计 现在计算机系统