编译原理第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：属于在虚拟机上运行的中间语言，作用类似于汇编语言，但结构要比汇编语言高级的多，需要虚拟机二次编译或者解释才能执行。,高级程序设计语言的特点和发展,(2)20世纪6070年代：结构化设计方法，如Pascal、C等。,a.支持模块化设计方法（顺序、判断、循环），具有完备的数据结构、灵活通用的语句、清晰的书写格式、优美的设计风格；,b.编制更大规模的程序问题百出，无法管理和维护。,(1)20世纪60年代初期出现高级程序设计语言，如Fortran（科学计算）,Cobol（商业数据处理）,Algol60等。,a.降低了编程劳动强度，将程序员从繁琐的低级语言中解放出来；,b.数据类型单调，程序依赖于程序员的技巧，难读、难改、不易移植，难以编制更大规模的程序。,高级程序设计语言的特点和发展,(3)20世纪70年代中期：借助软件工程的方法。,a.使编制软件的规模进一步扩大；,b.传统软件工程对软件危机没有多大缓解，大型软件投资失败依然大量存在。,(4)20世纪80年代：面向对象的程序设计语言Smalltalk问世。,a.OOP立意于创建软件重用代码，更好的模拟现实世界；,b.早期的面向对象语言不能轻松的刻画可视化对象，与用户交互能力差。,(5)20世纪90年代中期：基于可视化和面向对象的编程语言，如VB、VC、Delphi等。,a.使得可视化编程与面向对象紧密结合起来；,b.代码复用在源代码级别上。,高级程序设计语言的特点和发展,(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;,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=3b=4,公共数据区：a=3b=4,max()：x=3y=4return 4,公共数据区：Max=4,main()a=3b=4c=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=3b=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 高级程序设计语言参数传递,/*C程序*/void Add(int x,int y,out int nResult)nResult=x+y;void main()int a,b;scanf(“a=%d,b=%d”,(5)传结果：,1、静态存贮分配 编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项目的单元地址。2、动态存贮分配 如果允许递归、可变数据结构，则必须动态分配。栈式：整个程序数据空间安排在一个栈中 堆式：允许自由地申请和退还空间,1.6.2 存储管理,存储管理,
