编译原理第1章绪论.ppt

第一章绪论,计算机包括硬件和软件两大部分；裸机从某个固定的地址开始载入“程序”，根据“程序逻辑”执行逻辑操作；pulloneselfupbyonesbootstraps安装了操作系统的计算机，由操作系统载入“文件”，根据文件数据执行逻辑操作。,编译程序,第一章绪论,Intel公司的DavidKuck院士“计算机科学与技术的皇后”图灵奖”计算机界的诺贝尔奖”,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发我一句：我没看懂,Ifyouneverleaveme,Iwillbewithyoustilldeathdousapart,四级：你要不离开我，我就和你同归于尽。结果：我伤心欲绝，再也没联系那姑娘。,六级：“你若不离不弃，我必生死相依”结果：后悔莫及，遗憾终生,1.2编译过程概述,源程序,目标程序,1.2.1词法分析,任务：分离单词，即从左到右一个字符一个字符的读入源程序，识别出一个个单词。,intnSum,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语法分析和语义分析,语法分析：识别语法成分或识别句子，将单词序列分解成各类语法单位，如程序、语句、表达式语义分析：审查各语法单位有无语义错误，并为代码生成阶段收集类型信息等，完成语义解释。依循的原则：语法规则工具：上下文无关文法,intnSum,i=10;nSum=i*100+20;,nSum,1.2.3中间代码生成和优化,中间代码生成：将源程序变成一种内部表示。优化：使生成的目标代码更有效，节省空间和时间。依循的原则：程序的等价变换规则工具：三元式，四元式，树形结构等,intnSum,i=10;nSum=i*100+20;,(1)(*,i,100,t1),(2)(+,t1,20,t2),(3)(=,t2,nSum),1.2.4目标代码生成,目标代码：指机器所能认识的机器指令代码或汇编指令代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码:可直接运行可重新定位指令代码:连接装配汇编指令代码:需要进行汇编,(1)MOVi,R1,(2)MUL#100,R1,(3)ADD#20,R1,(4)MOVR1,nSum,1.2.5表格管理,功能：辅助予以的正确性检查，辅助代码生成。编译过程中的各种信息被保留在各种不同的表格中，并且各阶段都要涉及表格的构造、查找或更新。,1.2.6出错处理,出错处理程序：发现源程序中的错误，把有关错误信息报告给用户；对错误的检测、定位及处理。语法错误语义错误,编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化编译后端：与目标机有关，与目标机有关的优化，目标代码产生,前端,后端,1.3编译程序与程序设计环境,程序设计环境编辑程序编译程序连接程序调试工具集成化的程序设计环境,1.3编译程序与程序设计环境,.NETFramework与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、传地址(callbyreference)：把实参的地址传递给相应的形参2、传值(callbyvalue):调用段把实参的值计算出来并放在被调用段可以拿到的地方，把值带入。3、传名(callbyname)：过程调用的作用相当于把被调用的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数(文字替换)。,参数传递,1.6.1高级程序设计语言参数传递,#include“stdio.h”intmax(intx,inty)return(xy?x:y);voidmain()inta,b,c;scanf(“a=%d,b=%d”,(1)参数：,形式参数,实际参数,1.6.1高级程序设计语言参数传递,#include“stdio.h”intmax(intx,inty)return(xy?x:y);voidmain()inta,b,c;scanf(“a=%d,b=%d”,(2)传值：,main()a=3b=4,公共数据区：a=3b=4,max()：x=3y=4return4,公共数据区：Max=4,main()a=3b=4c=4,1.6.1高级程序设计语言参数传递,#include“stdio.h”voidSwap(int*x,int*y)intn=*x;*x=*y;*y=n;voidmain()inta,b;scanf(“a=%d,b=%d”,(3)传地址：,main()a=3b=4,公共数据区：scanf(“a=%d,b=%d”,1.6.1高级程序设计语言