程序设计语言与编译陈文宇电子科技大学计算机科学与工程学院陈文宇联系方式cwy@uestc.edu.cn13808181782程序设计语言与编译--语言的设计与实现(2版)龚天富2003电子工业出版社一.教材二.参考书1.龚天富等高级程序设计语言概论2.陈火旺等,程序设计语言编译原理3.AndrewW.Appel现代编译原理1.课程设置:56+8学时2.先修课程:数据结构,形式语言,PASCAL、C语言三.关于教学四.教学内容涉及语言及其编译系统的设计要素,设计思想,设计方法和设计技术等知识。1)上篇,程序设计语言的设计包括:绪论,数据类型,控制结构,语言设计;2)下篇,程序设计语言的实现(编译)包括:编译概述,词法分析,语法分析,语义分析和中间代码生成,代码优化和目标代码生成,运行时存储空间的组织。五.学习目标掌握设计和实现一个程序设计语言的基本思想和方法。具有分析、鉴赏、评价、选择、学习、设计和实现一个语言的基本能力。六.课程的重要性自从1954年世界上第一个高级语言编译器—FORTRAN语言编译器问世以来,编译技术不断进步,它已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华。课程的重要性ACM图灵奖是授予在计算机技术领域作出突出贡献的科学家的最高奖励.自1966年设立以来,程序设计语言、编译理论与方法的方面的得奖成果约占总数的1/3。(参见WORD文档)课程的重要性从计算机应用的发展来看,编译技术在其中有着极其重要的和不可替代的作用。正是在编译技术的支持下,程序设计才从以繁琐的低级语言为工具,发展到以接近自然语言和数学语言的高级程序设计语言为工具;软件开发也从模块化的软件开发方法发展到了面向对象的开发方法。编译技术的发展极大地提高了软件开发的效率,深刻地影响着软件开发方法的变革。课程的重要性语言是软件设计与开发最重要的工具.程序设计语言数以千计,千姿百态,在发展与变化之中体现出很多共性,又各具特点和优势,更有不少的创新。有必要从语言设计和实现层面展现这些共性和语言发展的脉络及全貌,这是计算机专业人员需要透彻了解的。课程的重要性编译原理课程以介绍程序设计语言的设计和编译程序构造的基本原理和设计方法为教学目标。通过本课程的学习1)掌握和理解语言设计的理论和方法;2)掌握和理解编译系统的结构、工作流程以及编译程序各组成部分的设计原理和实现技术,获得分析、设计、实现和维护编译系统的初步能力;3)提高对程序设计语言、操作系统、计算机原理和体系结构等课程知识的综合理解。结论从计算机专业人才的知识结构和专业素养的培养而言,编译原理是高等学校培养计算机专业人才的核心课程。内容安排上篇程序设计语言的设计下篇程序设计语言的实现第一章绪论本章将讨论程序设计语言中的一些重要概念,为深人了解程序设计语言打下基础。简介程序设计语言的发展历史。1.1引言1.程序设计语言的产生语言是人们交流思想的工具。人类在长期的历史发展过程中,为了交流思想、表达感情和交换信息,逐步形成了语言----自然语言。用于计算机的各种人工语言称为程序设计语言。目的是进行人机通信。2.程序设计语言的发展机器语言→汇编语言→高级语言用机器语言编写的程序由二进制代码组成,计算机可以直接执行。将机器语言符号化,于是产生了汇编语言。机器语言和汇编语言都是与机器有关的语言,通常称为低级语言。其他与机器无关的程序设计语言,通常称为高级语言。①直观、自然、易于理解②易读,易写,易于交流、存档③一般都是独立于机器的,易于移植3.高级语言的特点翻译:等价的变换。计算机只理解机器语言,可直接执行用机器语言编写的程序。而用汇编语言和高级语言编写的程序,机器不能直接执行,必须将它们翻译成功能完全等价的机器语言程序才能执行。将汇编语言程序翻译为机器语言程序的程序称为汇编程序(汇编器)将高级语言程序翻译为低级语言程序的程序称为编译程序(编译器)编写一个高级语言的编译程序的工作,通常称为对这个语言的实现。BASIC是最简单的高级语言,它不是编译执行,即不需要将源程序编译成目标程序,而是对源程序进行解释(分析),直接计算出结果。通常的做法是,将源程序转换成一种中间代码(这种中间代码与机器代码不同),中间代码的解释由软件支持。通常称这种支持解释的软件为解释程序(解释器)。Pascal语言最早实现是先将源程序编译成抽象的中间代码P码(P-code),然后再对P码解释执行。LISP,ML,Prolog和Smalltalk均是解释型的语言。Java被当作一种解释型语言。Java编译器产生一种字节码的中间语言,这种字节码可以在Java虚拟机上运行。解释执行特别适合于动态语言和交互式环境,因为可以立即得到计算结果,便于人机对话。解释器边翻译边解释执行,重复执行的程序需要重复翻译,比编译执行要花去更多的时间,执行效率较低。4.与编译有关的三种语言、三种程序源语言、工具语言、目标语言源程序、编译程序、目标程序5.高级语言涉及的三类人设计者、实现者、使用者①介绍程序设计语言的设计和实现的最基本的理论和技术;提高鉴赏和评估语言的能力②在了解语言的重要概念、功能和限制的基础上,以便具有选择、设计和实现程序设计语言的能力6.本课程的目标1.2强制式语言一.程序设计语言的分类按设计的理论基础分为4类语言:强制式语言:基础是冯·诺依曼模型函数式语言:基础是数学函数逻辑式语言:基础是数理逻辑谓词演算对象式语言:基础是抽象数据类型按语言的发展进程分类:第一代语言(机器语言)第二代语言(汇编语言)第三代语言(高级语言,命令式、过程式)第四代语言(说明性语言、超高级语言新一代语言(函数式、逻辑式语言)1.基础存储器,控制器,处理器,ip2.特点①数据或指令以二进制形式存储;②存储程序的工作方式;③程序顺序执行;可强制修改执行顺序④存储器的内容可以被修改。二.冯.诺依曼体系结构(模型)ip代码存储器(C)数据存储器(D)3.在命令式语言上的表现①变量存储单元及名称由变量的概念来代替。可以代表一个或一组单元。②赋值存储计算结果。③重复语句顺序执行,指令存储在有限的存储器中,完成复杂计算时需要重复执行某些指令序列。实体:程序的组成部分,如变量,程序单元等。属性:实体具有的特性。绑定:实体与其各种属性建立起某种联系的过程称为绑定,实际上就是建立了某种约束。描述符:描述实体的属性的表格。绑定时间:把实体与它的某个属性联系起来的时刻。三.绑定(Binding)概念编译时能确定的特性--静态特性运行时才能确定的属性--动态特性静态和动态特性若一个绑定在运行之前(即编译时)完成,且在运行时不会改变,则称为静态绑定。若一个绑定在运行时完成(此后可能在运行过程中被改变),则称为动态绑定。四变量变量是对或若干个存储单元的抽象赋值是对修改存储单元内容的抽象。变量用名字来标识,还有4个属性:作用域、生存期、值、类型注:变量可以不具有名字--匿名变量1.变量的作用域可以访问该变量的程序范围。①静态作用域绑定:按照程序的语法结构定义变量的作用域(C语言等)。②动态作用域绑定:按照程序的执行动态地定义变量的作用域(SNOBL4语言等)。2.变量的生存期存储区绑定于一个变量的时间区间。数据对象表示存储区和它保存的值。变量获得存储区的活动称为分配。变量所分配的存储单元的个数--变量的长度。语言在运行前进行分配变量存储区--静态分配(FORTRAN语言)语言在运行时进行分配变量存储区--动态分配(C、C++语言)采用什么样的分配,由语言规定。动态分配通过两种途径来实现:用相关的语句显式提出请求(new)进入变量的作用域时自动分配。3.变量的值存储区单元的内容变量在生存期内绑定于一个存储区,该存储区中的内容以二进制编码方式表示的变量值,并绑定于变量。值按变量所绑定的类型来进行解释。访问匿名变量的基本方法是通过访问路径来实现的。变量的值在程序运行时可以通过赋值操作来修改,因此,变量与它的值的绑定是动态的。符号常数(量)的值不能修改。变量,获得所分配的存储区,完成变量与存储区的绑定。此时,该变量绑定的值是什么呢?即变量初始化问题。⊙不初始化则出错⊙随机⊙缺省值04.变量的类型①与变量相关联的值,以及对这些值进行的操作的说明。类型可用来解释变量绑定的存储区的内容(二进制编码)的意义;语言定义时,类型绑定于值和操作;语言实现时,值和操作绑定于某种机器二进制表示。②变量可以静态或动态地绑定于类型。静态绑定:通过说明语句完成动态绑定:执行时隐式说明,且动态变化A5整型A12510一维数组A0A[2:3]0二维数组?动态绑定的语言实现采用解释方式处理更合适,因为对于一个不能确定变量类型的表达式,在运行之前没有足够的信息来生成合适的代码。语言实现采用编译还是解释方式,受到变量与类型绑定规则的严重影响。静态绑定语言是面向编译的语言。动态绑定语言是面向解释的语言。动态类型绑定的语言,往往其作用域也是动态绑定的,因此,这类语言又称为动态语言。①M1是实际的机器,②汇编语言程序要在M1和汇编程序上执行,M1+汇编程序=M2M2称为虚拟机,M2的机器语言是汇编语言③若高级语言是虚拟机M3的机器语言,则M3=M2+编译程序五.虚拟机:软件实现的机器虚拟机是由实际机器加软件实现的机器。若一台实际机器配置上C语言编译程序,对用户来说,这台机器就是以C语言(为机器语言)的虚拟机(C语言机)。六.主要的强制式语言及其关系ALGOL60ALGOL68ALGOLWCOBOLFORTRANPL/1FORTRAN2000BASICPascalModula-2ConcurrentPascalAdaBCPLCC++Java1.(程序)单元:程序执行过程中的独立调用单元。如子程序,分程序,过程等。2.单元表示编译时,单元表示为单元的源程序。运行时,单元表示由一个代码段和一个活动记录组成,称为单元实例。1.3程序单元3.活动记录:执行单元需要的信息,及该单元的局部变量所绑定的数据对象的存储区。4.非局部变量:一个程序单元可以引用未被本单元说明而被其它单元说明的变量。5.全局变量:在一个程序中,各个程序单元都可以引用的变量。6.引用环境:一个程序单元U可以引用的局部变量和非局部变量。局部变量绑定于存储在U的当前活动记录中的数据对象,称为局部环境。非局部变量绑定于别的(说明该非局部变量)程序单元的活动记录(或全局数据区)中的数据对象,称为非局部环境。7.别名同一单元的引用环境中有两个或多个变量绑定于同一数据对象,称这些变量具有别名。8.副作用对一个非局部变量的进行修改。随着计算机技术的发展,计算机应用,已经渗透到社会的各个领域,对程序设计语言也提出了新的要求(诸如可维护性,可靠性,可移植性等),从而促进了语言的发展。1.4程序设计语言发展简介目标:追求效率1.FORTRAN=FORmulaTRANslation.主要用于科学计算.子程序独立编译.COMMON语句实现了模块之间的通信一.早期的高级语言(50年代)2.ALGOL60ALGOrithmicLanguage60.主要用于科学计算.引入了分程序结构和递归过程.采用BNF形式描述语法3.COBOLCOmmonBusinessOrientedLanguage.广泛应用于各种事务处理领域.引入了文件和数据描述.类自然语言程序描述60年代初,不再盲目地追求效率,出现了基于良好刻画数学原则的语言。1.LISP.具有很强的符号处理能力.统一的数据结构.数据和程序统一的表示方法.其基础是函数和函数作用二.早期的突破2.APL.支持函数式程序设计风格.广泛应用于涉及大量矩阵运算的科学计算中.具有丰富的操作符3.SNOBOL4.主要用于字符串处理.给出了一种与机器无关的宏功能,增加了程序的可移植性PL/1.希望将所有语言概念集成大全.分程序概念和递归过程.数据描述机能.动态数据结构.异常处理.多任务机能.可用于科学数值计算,数据处理等.难以得到广泛的应用三.概念的集成(64年)引入了许多有趣的概念