编译原理第01章编译程序概述.ppt

2019/7/10,1/38,编译原理,李红军 E-mail: Tel:2019/7/10,2/38,课程简介,课程内容 介绍编译器构造的一般原理和基本实现方法 介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论等 强调形式描述技术和自动生成技术 强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于某种源语言或目标机器,2019/7/10,3/38,为什么要学习编译原理,是计算机学科中一个非常成功的分支 蕴涵着计算机学科中解决问题的思路、抽象问题和解决问题的方法 有利于加深对程序语言的理解 是一个很好的软件工程实例，所介绍的概念和技术能应用到一般的软件设计之中 在软件逆向工程、程序理解和软件安全等方面有着广泛的应用。,2019/7/10,4/38,教材和参考书,教材 程序设计语言编译原理. 陈火旺著,国防科技大学出版社。 参考书 COMPILER CONSTRUCTION-Principles and Practice. Kenneth C. Louden著(San Jose State University) 编译原理. (美)阿霍(Aho, A. V.)等著. 李建中等译. 北京:机械工业出版社, 2003.8 编译原理考研辅导教程. 电子科技大学出版社,2019/7/10,5/38,课程要求,目标：相互交流，共同进步 课时：48 课程学分：3 先修课程:离散数学数据结构与算法程序设计语言 考核：考试(70%)+平时(30%) 作业：每章至少1题,2019/7/10,6/38,编译程序历史（国外）,1957年，IBM的John Backus带领的一个研究小组设计出了Fortran语言及其编译器。 与此同时，Noam Chomsky开始了他对自然语言结构的研究，发现Chomsky Hierarchy。 70年代后期和80年代早期，编译器其它部分的生成自动化。这些尝试并未取得多少成功。 在九十年代，作为GNU项目或其它开放源代码项目的一部分，许多免费编译器和编译器开发工具被开发出来。,2019/7/10,7/38,编译程序历史（国内）,60年代初期，董韫美院士和杨芙清院士的研究组开发国产机上的ALGOL和FORTRAN编译器。 改革开放前，研制国产计算机，包括大型机和高性能计算机（如向量机、并行机），相应的也在研制高级语言编译器。 90年代以来中科院计算所张兆庆教授研究组(ACTGroup) 先后开发了共享内存多处理机的并行识别器，分布式内存多处理机的并行识别器， SIMD芯片和VLIW芯片的并行优化C编译器。将编译技术与图形学结合，ACTGroup还推出了集成化、可视化的并行编程环境。,2019/7/10,8/38,编译程序现状,并行机的并行编译技术 基于GCC(GNU C Compiler)生成面向特定芯片的编译器工作 反编译技术,2019/7/10,9/38,第一章 编译程序概论,什么是编译程序,本章重点介绍编译程序的基本概念。,编译的过程,编译程序的结构,2019/7/10,10/38,程序设计语言,计算机可以直接接收的语言是机器语言，由二进制(0、1序列)组成，唯一可以在机器上直接执行的语言。难读、难写、与硬件环境密切相关。 汇编语言用助记符表示指令的操作码。 高级程序设计语言摆脱了对硬件的依赖，易读、易写、便于算法交流。,2019/7/10,11/38,1.1 什么是编译程序,翻译程序是指这样一个程序,它把一种语言(称作源语言)所写的程序(源程序)翻译成等价的另一种语言(称作目标语言)的程序(目标程序)。,高级语言程序,机器语言程序,翻译程序,2019/7/10,12/38,1.1 什么是编译程序,编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。,源程序,高级语言程序,编译程序,目标程序,汇编语言或者机器语言程序,2019/7/10,13/38,程序运行阶段,第一种情况：,高级语言 程序,2019/7/10,14/38,第二种情况：,高级语言 程序,程序运行阶段,2019/7/10,15/38,1.2 编译过程和编译程序的基本结构,将英文句子 “I wish you success ”翻译成中文句子的大致过程是：,词法分析,语法分析,语义分析,修饰工作,翻译成文,2019/7/10,16/38,编译过程,编译程序的工作过程：五个阶段,词法分析,语法分析,中间代码生成,代码优化,目标代码生成,2019/7/10,17/38,float r，h，s； s = 2*3.1416 * r *(rh);,例如 计算圆柱体表面积的程序 片断如下：,编译过程,2019/7/10,18/38,词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词( 也称单词符号, 简称符号 )。,1. 词法分析,2019/7/10,19/38,词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。,词法规则,float r，h，s； s = 2*3.1416*r*(hr);,例如,2019/7/10,20/38,词法分析结果： 关键字 float 标识符 r、h、s 常数 3.1416、2 算符 * 、 界符 （、 ）、 ；、 ，、=,词法规则,2019/7/10,21/38,2. 语法分析,语法分析的任务是在词法分析的基 础上, 根据语言的语法规则从单词符 号串中识别出各种语法单位( 如表 达式、说明、语句等 ) ,并进行语法 检查,即检查各种语法单位在语法结 构上的正确性。,2019/7/10,22/38,语法规则,语言的语法规则规定了如何从单词符号形成语法单位，语法规则是语法单位的形成规则。,float r，h，s； s = 2*3.1416*r*(hr);,例如,2019/7/10,23/38,语法规则,单词符号串 s=2*3.1416 * r *(hr)中，“s” 是，单词符号串 “2 * 3.1416 * r *(hr)” 组合成这样的语法单位 , 由=构成这样的语法单位。,规则的表示方法：巴克斯-诺尔范式,2019/7/10,24/38,3. 中间代码生成,语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式 (比源语言更接近于目标语言的一种中间代码或直接用目标语言 ) 来描述这种语义。,2019/7/10,25/38,例如，前例中,将s = 2*3.1416 * r *(hr)翻译成如下形式的四元式中间代码：,(1) ( *, 2, 3.1416, T1 ),(2) ( *, T1, r, T2 ),(3) ( +, h, r, T3 ),(4) ( *, T2, T3, T4 ),(5) ( =, T4, _, s ),2019/7/10,26/38,4. 代码优化,代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。优化主要包括局部优化和循环优化等，例如上述四元式经局部优化后得：,2019/7/10,27/38,5.目标代码生成,目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。,2019/7/10,28/38,表格管理和错误处理,编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息，因此，在编译程序中必须有一组管理各种表格的程序。,在编译程序的各个阶段中，都要涉及表格管理和错误处理。,2019/7/10,29/38,表格管理和错误处理,一个好的编译程序在编译过程中，应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正，因此，在编译程序中还必须有一个出错处理程序。,2019/7/10,30/38,编译程序的结构,源程序,中间代码生成程序,语法分析程序,词法分析程序,代码优化程序,目标代码生成程序,目标程序,表 格 管 理 程 序,出 错 处 理 程 序,( 字符串),2019/7/10,31/38,1.3 编译程序的生成方法,对源语言和目标语言认真分析,设计编译算法,选择语言编制程序,调试编译程序,提交相关文档资料,生成一个编译程序一般要考虑以下几方面：,2019/7/10,32/38,编译程序的自动生成,LEX YACC 可用来自动产生整个编译程序的软件工具：编译程序产生器, 它的功能是将任一语言的词法规则、语法规则和语义解释的描述作为输入，自动生成该语言的编译程序。,编译程序自动生成系统。,2019/7/10,33/38,编译程序的自动生成,生成编译程序的方法还常采用自编译方式和移植方式。,随着并行技术和并行语言的发展，处理并行语言的并行编译技术和将串行程序转换成并行程序的自动并行编译技术正在深入研究之中。,2019/7/10,34/38,1.4 编译技术在软件开发中的应用,虽然我们只有少数人从事构造或维护程序语言编译程序的工作,但是，大部分系统软件和应用软件的开发，通常要用到编译的原理和技术。,2019/7/10,35/38,1.4 编译技术在软件开发中的应用,例如,设计词法分析器的串匹配技术已用于正文编辑器、信息检索系统和模式识别程序; 上下文无关文法和语法制导定义已用于创建诸如排版、绘图系统和语言结构化编辑器中，代码优化技术已用于程序验证器和从非结构化的程序产生结构化程序的编程之中。,2019/7/10,36/38,怎样学习编译原理,做好思想准备,不要畏难,多看书，结合课本后面的习题多做思考和类比, 在学习的过程中归纳出自己的难点和疑惑点,然后重点突破； 自己动手做一个虚拟机,在虚拟机的基础上开发自己的语言和编译器,加强实践；深刻的理解书本上那些抽