编译原理和技术课件.ppt

1、编译原理和技术编译原理和技术编译原理课程在计算机科学技术中的地位：编译原理课程在计算机科学技术中的地位：程序设计语言离散数学数据结构编译原理操作系统系统软件应用软件软件工程信息系统电子商务编译理论与方法计算机科学与技术中理论和实践相结合的最好典范 ACM 图灵奖，授予在计算机技术领域作出突出贡献的科学家程序设计语言、编译理论与方法约占1/3（。课课 程程 简简 介介学习的意义学习的意义在计算机专业考研或者各大公司招聘时，必在计算机专业考研或者各大公司招聘时，必考内容。考内容。在在x86/Linuxx86/Linux工作站上，以下两个结构的工作站上，以下两个结构的sizesize分别是分别是20

2、20和和1616，为什么不一样？为什么不一样？typedef struct _atypedef struct _atypedef struct _btypedef struct _bchar char c1;c1;char c1;char c1;long long i;i;char char c2;c2;charcharc2;c2;long i;long i;double f;double f;double f;double f;a;a;b;b;vc结果结果vs Linux下下gcc的结果的结果vc6中的编译选项有中的编译选项有/Zp1|2|4|8|16，/Zp1表示表示以以1字节边界对齐，相

3、应的，字节边界对齐，相应的，/Zpn表示以表示以n字节边字节边界对齐。界对齐。n字节边界对齐的意思是说，一个成员字节边界对齐的意思是说，一个成员的地址必须安排在成员的尺寸的整数倍地址上或的地址必须安排在成员的尺寸的整数倍地址上或者是者是n的整数倍地址上，取它们中的最小值。的整数倍地址上，取它们中的最小值。要使用这个选项，可以在要使用这个选项，可以在vc6中打开工程属性页，中打开工程属性页，c/c+页，选择页，选择Code Generation分类，在分类，在Struct member alignment可以选择。可以选择。FORTRAN(FORmula TRANslation)第一个实用的高级

4、语言第一个实用的高级语言 擅长于数学函数运算擅长于数学函数运算 常用于科学计算中常用于科学计算中 第一个编译器第一个编译器 历史上第一个实用的编译器历史上第一个实用的编译器(John Backus)：Fortran compiler for the IBM 704/709/7090/7094 John Backus，引入了编译器的，引入了编译器的“阶段阶段”或或称为称为“遍遍”的概念，是编译设计的模块化的开的概念，是编译设计的模块化的开始始编译器从逻辑上可以分成若干阶段每个阶段把源程序从一种表示变换成另一种表示本章通过描述编译器的各个阶段来介绍编译这个课题词法分析器词法分析器 id,1 =id

5、,2 +id,3 60 position=initial+rate 60 id,1 =id,2 +id,3 60 第一章 引 论 词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器 后三个阶后三个阶段对源程段对源程序进行综序进行综合合第一章 引 论 词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器

6、 分析和综合：把编译过程分成分析和综合两步把编译过程分成分析和综合两步分析：分析源程序以计算其特性所涉及到的分析源程序以计算其特性所涉及到的操作（词法分析、语法分析、语义分析）操作（词法分析、语法分析、语义分析）综合：生成目标代码时所涉及到的操作（生成目标代码时所涉及到的操作（中中间代码生成、代码优化、代码生成）间代码生成、代码优化、代码生成）辅助：符号表管理、出错处理符号表管理、出错处理8项功能对应8个模块。第一章 引 论前端和后端：把编译过程分成前端和后端两部分把编译过程分成前端和后端两部分前端：只依赖于源程序，独立于目标机器只依赖于源程序，独立于目标机器（生成中间代码）（生成中间代码）后

7、端：依赖于目标机器，与源程序无关，只与中间：依赖于目标机器，与源程序无关，只与中间语言有关（从中间代码生成目标代码）语言有关（从中间代码生成目标代码）好处：提高开发编译器的效率提高开发编译器的效率取一个编译器的前端，重写它的后端以产生同一源语言在取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器另一机器上的编译器不同的前端使用同一个后端，从而得到一个机器上的几个不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）编译器（采用同一中间语言）遍（趟）：一遍或或一趟：是指编译程序在编译时刻把源程序或源程序是指编译程序在编译时刻把源程序或源程序的等价物（中间程

8、序）从头到尾扫描一遍并转换成另一紧邻的等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等价物的全过程。的等价物的全过程。单遍扫描与多遍扫描：每一遍的扫视可完成上述一个阶每一遍的扫视可完成上述一个阶段或多个阶段的工作。每一遍的输入都是上一遍的输出，第段或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码。一遍的输入是源程序正文，最后一遍的输出是目标代码。单遍与多遍的比较：遍数多：编译器结构清晰，但时间效率不高遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高遍数少：编译速度快，但对机器的内存要求高遍数的确定：主要因素是

9、源程序和机器（目标机）的特征。主要因素是源程序和机器（目标机）的特征。虚拟机虚拟机BASIC年代的解释器功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器Java年代的解释器解释器的上述两个功能分在两个程序中前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序后一个叫做解释器，它对字节码程序进行解释执行编译器和解释器的区别编译器和解释器的区别三种奶牛三种嗜好三种奶牛三种嗜好编译器和解释器的区别编译器和解释器的区别改进后的方案改进后的方案编译器和解释器的区别编译器和解释器的区别牧草牧草 我们

10、的各种编程语言，我们的各种编程语言，C/C+/C#,Java,Pascal,PHP,Perl,Java Script等等切割机切割机 各种编译器各种编译器奶牛奶牛 各种各种CPU，比如，比如x86，ARM，MIPS等等奶牛会有吃不同形状牧草的嗜好，这个奇奶牛会有吃不同形状牧草的嗜好，这个奇怪的比喻是为了表示不同的怪的比喻是为了表示不同的CPU接受的不接受的不同的机器语言。同的机器语言。编译器和解释器的区别编译器和解释器的区别编译器与解释器的区别编译器与解释器的区别编译器是把源程序的每一条语句都编译成编译器是把源程序的每一条语句都编译成机器语言机器语言,并保存成二进制文件并保存成二进制文件,这样

11、运行时这样运行时计算机可以直接以机器语言来运行此程序计算机可以直接以机器语言来运行此程序,速度很快速度很快;而解释器则是只在执行程序时而解释器则是只在执行程序时,才一条一条才一条一条的解释成机器语言给计算机来执行的解释成机器语言给计算机来执行,所以运所以运行速度是不如编译后的程序运行的快的行速度是不如编译后的程序运行的快的.1.2 编译器技术的应用 高级语言的实现高级编程语言易于编程，但程序运行较慢低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护流行编程语言的大多数演变都是朝着提高抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化的新研究编程语言演义编程语

12、言演义编程语言编程语言机器语言机器语言汇编语言汇编语言高级语言（高级语言（Fortran,C,Java,)编程语言演义编程语言演义机器语言特点机器语言特点0,1串串打卡输入打卡输入c7 06 0000 0002 mov x,c 其中符号其中符号x的地址是的地址是0000，c=2计算机可以直接理解机器语言程序计算机可以直接理解机器语言程序机器语言缺点机器语言缺点可读性差可读性差可维护性差可维护性差编程语言演义编程语言演义汇编语言形式汇编语言形式mov x,2c7 06 0000 0002 变量变量x的地址可以由汇编器维护，的地址可以由汇编器维护，而不需要固定到某个绝对地址而不需要固定到某个绝对地

13、址编程语言演义编程语言演义高级语言形式高级语言形式赋值语句：赋值语句：x=2贴近人类思维方式，贴近实际问题贴近人类思维方式，贴近实际问题描述形式描述形式计算机无法直接理解计算机无法直接理解需要编译器辅助，将其转换为机器语需要编译器辅助，将其转换为机器语言形式言形式1.2 编译器技术的应用 高级语言的实现每一轮编程语言新特征的出现都刺激编译器优化的新研究支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java类型安全的语言：Java没有指针，也不允许指针算

14、术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存1.2 编译器技术的应用 针对计算机体系结构的优化计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要并行化 编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上内存分层 编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效1.2 编译器技术的应用 新计算机体系结构的设计现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，

15、以评价拟采用体系结构的特征编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明1.2 编译器技术的应用 程序翻译二进制翻译 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码数据库查询解释器 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令1.2 编译器技术的应用 提高软件开发效率的工具源于编译器中代码优化技术的程序分析一直在改进软件开发效率类型检查 类型检查是一种捕捉程序中前后不一致的成熟而有效的技术边界检查 数据流分析技术可用来定位缓冲区溢出内存管理 自动的内存管理删除内存泄漏等内存管理错误