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

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