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

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