编译原理第1章绪论.ppt

第一章 绪论,计算机包括硬件和软件两大部分； 裸机从某个固定的地址开始载入“程序”，根据“程序逻辑”执行逻辑操作； pull oneself up by ones bootstraps 安装了操作系统的计算机，由操作系统载入“文件”，根据文件数据执行逻辑操作。,编译程序,第一章 绪论,Intel公司的David Kuck院士 “计算机科学与技术的皇后” 图灵奖”计算机界的诺贝尔奖”, 1966年以来54位获奖者 16位研究内容为程序设计语言或编译技术 高级语言的发展，C#（CLR）, Java等,编译程序,第一章 绪论,将高级语言翻译成机器语言的语言处理器： 编译器：将高级语言程序翻译加工成目标程序，然后目标程序在计算机上运行, “笔译”。 解释器：把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身, “口译”。,编译程序又称编译器，是将高级语言符号集合加工成机器指令的转换器。,编译器,解释器,目标程序,源程序,源程序,输入,输出,语言处理器,1.1 程序设计语言概述,机器语言(0, 1)：用计算机指令编写的，可以直接在计算机上运行的程序；枯燥、易出错,(2) 汇编语言：将计算机指令用易于记忆的符号表示；加入宏指令，处理频繁使用的机器指令序列,(3) 高级语言：由表达各种不同意义的“关键词”和“表达式”，按一定的语义规则组成的程序。,语言分类,(4) MSIL和JVM：属于在虚拟机上运行的中间语言，作用类似于汇编语言，但结构要比汇编语言高级的多，需要虚拟机二次编译或者解释才能执行。,1.1.1高级程序设计语言的特点和发展,(2) 20世纪6070年代：结构化设计方法，如Pascal、C等。,a. 支持模块化设计方法（顺序、判断、循环），具有完备的数据结构、灵活通用的语句、清晰的书写格式、优美的设计风格；,b. 编制更大规模的程序问题百出，无法管理和维护。,(1) 20世纪60年代初期出现高级程序设计语言，如Fortran（科学计算）, Cobol（商业数据处理）, Algol60等。,a. 降低了编程劳动强度，将程序员从繁琐的低级语言中解放出来；,b. 数据类型单调，程序依赖于程序员的技巧，难读、难改、不易移植，难以编制更大规模的程序。,1.1.1高级程序设计语言的特点和发展,(3) 20世纪70年代中期：借助软件工程的方法。,a. 使编制软件的规模进一步扩大；,b. 传统软件工程对软件危机没有多大缓解，大型软件投资失败依然大量存在。,(4) 20世纪80年代：面向对象的程序设计语言Smalltalk问世。,a. OOP立意于创建软件重用代码，更好的模拟现实世界；,b. 早期的面向对象语言不能轻松的刻画可视化对象，与用户交互能力差。,(5) 20世纪90年代中期：基于可视化和面向对象的编程语言，如VB、VC、Delphi等。,a. 使得可视化编程与面向对象紧密结合起来；,b. 代码复用在源代码级别上。,1.1.1高级程序设计语言的特点和发展,(6) 二进制级别的软件复用：Ole、COM、Cobar等。,(7) 进一步发展：软件标准件的生产。,Web编程工具的发展：,(1) 20世纪90年代：Script技术，如ASP、JavaScript。,(2) 21世纪初：可视化与面向对象结合，如ASP.Net。,1.1 程序设计语言概述,Java语言处理器结合了编译和解释过程,a. 一个Java源程序首先被编译成一个称为字节码的中间表示形式,b. 由一个虚拟机对得到的字节码加以解释执行（一台机器上编译得到的字节码可以再另一台机器上解释执行，通过网络就可以完成机器之间的转换）,构建编译器的相关科学,1、编译器设计和实现中的建模,2、代码优化的科学,接收所有遵循语言规范的源程序。源程序的集合无限大 所做的翻译工作都不能改变编译源程序的含义,优化必须正确 优化必须能够改善很多程序的性能 优化所需的时间必须保证在合理的范围内 所需要的工程方面的工作必须是可管理的,把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。,1.2 编译过程概述,追了一姑娘很多年了，那天她QQ发我一句：我没看懂,If you never leave me, I will be with you still death do us apart,四级：你要不离开我，我就和你同归于尽。 结果：我伤心欲绝，再也没联系那姑娘。,六级：“你若不离不弃，我必生死相依” 结果：后悔莫及，遗憾终生,1.2 编译过程概述,源程序,目标程序,1.2.1 词法分析,任务：分离单词，即从左到右一个字符一个字符的读入源程序，识别出一个个单词。,int nSum, i = 10; nSum = i * 100 + 20;,1.保留字 int,2.标识符 nSum,3.逗号 ,4.标识符 i,5.赋值号 =,6.整数 10,7.分号 ;,8.标识符 nSum,9.赋值号 =,10.标识符 i,11.乘号 *,12.整数 100,13.加号 +,14.整数 20,15.分号 ;,依循的原则：构词规则 工具：正规式和有限自动机,1.2.2 语法分析和语义分析,语法分析：识别语法成分或识别句子，将单词序列分解成各类 语法单位，如程序、语句、表达式 语义分析：审查各语法单位有无语义错误，并为代码生成阶段收集类型信息等，完成语义解释 。 依循的原则：语法规则 工具：上下文无关文法,int nSum, i = 10; nSum = i * 100 + 20;,nSum,1.2.3 中间代码生成和优化,中间代码生成：将源程序变成一种内部表示。 优化：使生成的目标代码更有效，节省空间和时间。 依循的原则：程序的等价变换规则 工具：三元式，四元式，树形结构等,int nSum, i = 10; nSum = i * 100 + 20;,(1) (*, i, 100, t1),(2) (+, t1, 20, t2),(3) (=, t2, , nSum),1.2.4 目标代码生成,目标代码：指机器所能认识的机器指令代码或汇编指令代码。 依赖于硬件系统结构和机器指令的含义 目标代码三种形式: 绝对指令代码: 可直接运行 可重新定位指令代码: 连接装配 汇编指令代码: 需要进行汇编,(1) MOV i, R1,(2) MUL #100, R1,(3) ADD #20, R1,(4) MOV R1, nSum,1.2.5 表格管理,功能：辅助予以的正确性检查，辅助代码生成。 编译过程中的各种信息被保留在各种不同 的表格中，并且各阶段都要涉及表格的构造、查找或更新。,1.2.6 出错处理,出错处理程序：发现源程序中的错误，把有关错误信息报告给用户；对错误的检测、定位及处理。 语法错误 语义错误,编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化 编译后端 ：与目标机有关，与目标机有关的优化，目标代码产生,前端,后端,1.3 编译程序与程序设计环境,程序设计环境 编辑程序 编译程序 连接程序 调试工具 集成化的程序设计环境,1.3 编译程序与程序设计环境,.NET Framework与VS.NET,机器语言或汇编语言 主要优点：编出来的程序效率高。 主要缺点：编程效率低，可读性差，不便于修改和移植。 高级程序设计语言已基本取代汇编语言 优点：编程效率高，可读性好，利于移植。 缺点：编译程运行效率较低。,1.4 编译程序生成,自编译性： 如果一个高级语言能用来书写自己的编译程序，则该语言具有自编译性，并称该语言为自编译语言。,通常用自编译语言除可编写本语言的编译程序以外，也可用来编写别的语言的编译程序。 如果某台机器上已配备有某种自编译语言，则可利用这种语言为本台机器配置其它的高级语言。,1.4.1 自编译性,自编译方式产生编译程序：,先对语言的核心部分构造一个小的编译程序； 以它为工具构造一个能够编译更多语言成分的较大编译程序； 如此扩展，最后形成所期望的整个编译程序。,1.4.1 自编译性,I,S,T,源语言S,目标语言T,用I语言编写的编译器,1.4.1 自编译性,A机器上已有用A机器代码实现的高级语言C的编译程序 A机器上用A机器代码实现的高级语言C#的编译程序,A机器,1.4.1 自编译性,1.4.2 编译程序的移植,移植：将某台机上的成熟软件移植到另一台机器上，也就是将宿主机上的软件移植到目标机上。如果使用具有自编译性的高级语言来书写程序，则移植是方便的。,移植,通过移植，在B机上可得到语言L的编译程序， 具有B机目标形式，可在B机上运行。,1.4.2 编译程序的移植,A机器上已有用A机器代码实现的高级语言C的编译程序 B机器上用B机器代码实现的高级语言C的编译程序,A,A,C语言描述的交叉编译器,A代码描述的交叉编译器,C语言描述的交叉编译器,可在B机器上运行的C语言编译器,1.5 并行编译概述,提高程序在向量计算机、并行体系结构计算机上的运行速度，有两种方法： 由用户直接编写并行语言程序； 将用户编写的串行程序并行化。,1.6 高级语言程序简介,模块之间进行参数传递有三种形式： 1、传地址(call by reference)： 把实参的地址传递给相应的形参 2、传值(call by value): 调用段把实参的值计算出来并放在被调用段可以拿到的地方，把值带入。 3、传名(call by name)： 过程调用的作用相当于把被调用的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数(文字替换)。,参数传递,1.6.1 高级程序设计语言参数传递,#include “stdio.h” int max(int x, int y) return (x y ? x : y); void main() int a,b,c; scanf(“a=%d,b=%d”, ,(1) 参数：,形式参数,实际参数,1.6.1 高级程序设计语言参数传递,#include “stdio.h” int max(int x, int y) return (x y ? x : y); void main() int a,b,c; scanf(“a=%d,b=%d”, ,(2) 传值：,main() a=3 b=4,公共数据区： a=3 b=4,max()： x=3 y=4 return 4,公共数据区： Max = 4,main() a=3 b=4 c=4,1.6.1 高级程序设计语言参数传递,#include “stdio.h” void Swap(int *x, int *y) int n = *x; *x = *y; *y = n; void main() int a,b; scanf(“a=%d,b=%d”, ,(3) 传地址：,main() a=3 b=4,公共数据区： &a &b,Swap()： &a &b,1.6.1 高级程序设计语言参数传递,#include “stdio.h” void Swap(int ,(4) 传名字（引用）：,#include “stdio.h” void main() int a,b; scanf(“a=%d,b=%d”, ,1.6.1 高级程序设计语言参数传递,/