编译第01章.ppt

1、编译原理,陈文宇 电子科技大学计算机科学与工程学院,陈文宇联系方式,科A楼514（实验室） 主楼B1-509（办公室）,程序设计语言与编译 -语言的设计与实现（4版） 王晓斌 陈文宇 等 编著 龚天富 审 2015 电子工业出版社,一.教材,二. 参考书,1. 龚天富等 高级程序设计语言概论 2. 陈火旺等 编译原理(3版)2004 3 Alfred V.Aho 等 赵建华 等译 编译原理龙书 机械工业出版社 4 Andrew W.Appel 等 赵克佳 等译 现代编译原理-虎书 人民邮电出版社,1. 课程设置: 56=48+8 学时 2. 先修课程 ,三. 关于教学

2、,四. 成绩构成,平时 10% 作业+课堂测验 半期 10% 实验 10% 期末 70% 课堂点名、测验、作业 累加到4次： 取消考试资格（教务处要求）,五. 教学内容,涉及语言及其编译系统的设计要素、设计思想、设计方法和设计技术等 1)上篇，程序设计语言的设计 绪论、数据类型 控制结构、语言设计,2)下篇，程序设计语言的实现（编译） 编译概述、词法分析、语法分析 语义分析和中间代码生成 代码优化和目标代码生成 运行时存储空间的组织,六.学习目标,掌握设计和实现一个程序设计语言的基本思想和方法。 具有分析、鉴赏、评价、选择、学习、设计和实现语言的基本能力。,七. 课程的重要性,20世纪50年代

3、，出现了与机器无关的编程语言（高级程序设计语言）。 第一个编译器是由葛丽丝穆雷霍普（ Grace Murray Hopper ）于1952年为A-0 系统编写的。 1957年由IBM的约翰巴科斯领导开发的FORTRAN语言编译器则是第一个具备完整功能的编译器,课程的重要性,编译技术已经成为计算机科学中发展最迅速、最成熟的一个重要分支。 编译技术集中体现了计算机科学发展的重要成果与精华。,课程的重要性,ACM图灵奖是授予在计算机技术领域作出突出贡献的科学家的最高奖励. 自1966年设立以来，程序设计语言、编译理论的成果约占总数的1/3。,课程的重要性,从计算机应用的发展来看，编译技术在其中有着极

4、其重要的和不可替代的作用。 正是在编译技术的支持下，程序设计才从以繁琐的低级语言为工具，发展到以接近自然语言和数学语言的高级程序设计语言为工具;,课程的重要性,编译技术的发展极大地提高了软件开发的效率，深刻地影响着软件开发方法的变革。,通过本课程的学习,1)掌握和理解语言设计的理论和方法； 2)掌握和理解编译系统的各组成部分的设计原理和实现技术； 3)提高对程序设计语言、操作系统、计算机组成原理、算法分析和体系结构等课程知识的综合理解。,结论,从计算机专业人才的知识结构和专业素养的培养而言 编译原理是高等学校培养计算机专业人才的核心课程,内容安排,上篇 程序设计语言的设计 下篇 程序设计语言的

5、实现,第一章 绪论,本章讨论程序设计语言中的一些重要概念，为深入了解程序设计语言打下基础。 简介程序设计语言的发展历史。,1.1 引言,1.程序设计语言的产生 语言是人们交流思想的工具。人类在长期的历史发展过程中，为了交流思想、表达感情和交换信息，逐步形成了语言-自然语言。 程序设计语言:人工语言,程序设计语言programming language,程序设计语言是一组规则，包括： 1）字母表的定义； 2）词法规则：单词符号的形成规则 C语言单词符号包括： 关键字、 标识符、 运算符 常量 、分界符,程序设计语言,3）语法规则：语法单位的形成规则 C语言语法单位包括： 表达式、语句、函数、程序

6、 4）语义规则： 单词符号和语法单位的含义规则；,程序设计语言,5)语用规则：语义规则的发展和延伸 强调在一定的语境中使用单词和语法单位时体现出来的具体意义；要根据上下文（即前、后内容）明确单词和语法单位的具体意义 6）其他规则：包括类型使用规则，参数传递规则，作用域规则等。,程序设计语言,计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级语言的历程。,2.程序设计语言的发展,机器语言汇编语言高级语言 用机器语言编写的程序由二进制指令组成，计算机可以直接执行。 将机器语言符号化，产生了汇编语言。,对于机器语言和汇编语言： 指令的操作码与功能、指令格式、寻址方式、数据格式等，不同的计算机

7、有不同的规定：机器有关的语言，通常称为低级语言。 与机器无关的程序设计语言，通常称为高级语言。,直观、自然、易于理解 易读，易写，易于交流、存档 一般都是独立于机器的,易于移植,3.高级语言的特点,翻译:等价的变换,计算机只可直接执行用机器语言编写的程序。 而用汇编语言和高级语言编写的程序，机器不能直接执行 必须将它们翻译成完全等价的机器语言程序才能执行,将汇编语言程序翻译为机器语言程序的程序称为汇编程序（汇编器） 将高级语言程序翻译为低级语言程序的程序称为编译程序（编译器） 编写一个高级语言的编译程序的工作，通常称为对这个语言的实现。,语言另一种执行方式：解释,BASIC是最简单的高级语言

8、它不是编译执行，而是对源程序进行解释（分析），直接计算出结果。 需要解释程序(解释器)支持,LISP，ML，Prolog和Smalltalk均是解释型的语言。 Java被当作一种解释型语言。 翻译产生字节码的中间代码， 可以在Java虚拟机上运行。,解释执行特别适合于动态语言和交互式环境，便于人机对话。 解释器边翻译边解释执行，重复执行的语句需要重复翻译，比编译执行要花去更多的时间，执行效率较低。,4.与编译有关的三种语言、三种程序 源语言、工具语言、目标语言 源程序、编译程序、目标程序 5.高级语言涉及的三类人 设计者、实现者、使用者,1.2 强制式语言,一.程序设计语言的分类 按设计的理论

9、基础分为4类语言: 强制式语言:基础是冯诺依曼模型 函数式语言:基础是数学函数(函数运算) 逻辑式语言:基础是数理逻辑、谓词演算 对象式语言:基础是抽象数据类型,第一代语言（机器语言） 第二代语言（汇编语言） 第三代语言（高级语言:命令式、过程式） 第四代语言（说明性语言、超高级语言） 新一代语言（函数式、逻辑式语言）,按语言的发展进程分类:,1.基础 存储器,控制器,处理器，ip 2.特点 数据、指令以二进制形式存储; 存储程序的工作方式； 程序顺序执行；可强制修改执行顺序 存储器的内容可以被修改。,二. 冯.诺依曼体系结构（模型）,ip,代码存储器（C）,数据存储器（D）,3.在命令式语言

10、上的表现 变量 存储单元及名称由变量的概念代替。变量可以代表一个或一组单元。 赋值 存储计算结果。 重复 语句顺序执行,指令存储在有限的存储器中,完成复杂计算时需要重复执行某些指令序列。,冯.诺依曼体系结构(模型),实体：程序的组成部分，如变量，表达式、程序单元等。 属性：实体具有的特性。 绑定：实体与其各种属性建立起联系的过程称为绑定，实际上就是建立了某种约束。 描述符：描述实体属性的表格。,三. 绑定（Binding)概念,编译时能确定的特性-静态特性 运行时才能确定的特性-动态特性,静态和动态特性,若绑定在运行之前(即编译时)完成，且在运行时不会改变，则称为静态绑定。 若绑定在运行时完成

11、，则称为动态绑定。,四 变量,变量是对一个或若干个存储单元的抽象 一个变量至少占用一个存储单元；一个存储单元至少一个字节（也可以为2个字节、 4个字节） 变量用名字来标识 变量也可以不具有名字-匿名变量 赋值是对修改存储单元内容的抽象,变量的4个属性： 作用域、生存期、值、类型,1.变量的作用域,可以访问该变量的程序范围。 静态作用域绑定:按照程序的结构定义变量的作用域（C语言等）。 动态作用域绑定:按照程序的执行动态地定义变量的作用域（SNOBL4 语言等） 。,2.变量的生存期,存储区绑定于一个变量的时间区间。 编译阶段 数据由变量和常量表示 运行阶段 数据由数据对象表示 数据对象表示存储

12、区和它保存的值。 变量获得存储区的活动称为分配。 变量分配的存储单元的个数-变量长度。,运行前分配变量存储区 -静态分配（FORTRAN语言） 运行时分配变量存储区 -动态分配（C 、C+语言） 分配原则，由语言(设计者)规定。,动态分配通过两种途径来实现： 用相关的语句显式提出请求(new) 运行变量所对应的程序单元时自动分配。,3.变量的值,存储区单元的内容 变量在生存期内绑定于一个存储区，该存储区中的内容以二进制编码方式表示的变量值，并绑定于变量。 值按变量所绑定的类型来进行解释。,访问匿名变量的基本方法是通过访问路径来实现的。 变量的值在程序运行时可以通过赋值操作来修改，因此，变量与它

13、的值的绑定是动态的。 常数（量）的值不能修改。,初始值问题,变量获得所分配的存储区，完成变量与存储区的绑定。 此时，该变量绑定的值是什么呢？即变量初始化问题。 不同的语言有不同的规则： 不初始化则出错 随机 缺省值0,4.变量的类型,与变量相关联的值，以及对这些值进行的操作的抽象。 类型可用来解释变量绑定的存储区的内容(二进制编码)的意义； 语言定义时,类型绑定于值和操作; 语言实现时,值和操作绑定于某种机器二进制表示。,变量类型可以静态或动态地进行绑定 静态绑定：通过说明语句完成 动态绑定：执行时隐式说明，且动态变化 A 5 整型 A 1 2 51 0 一维数组 A 0 A2:3 0 二维数

14、组 ？,动态绑定的语言实现采用解释方式处理更合适，因为对于一个不能确定变量类型的表达式，在运行之前没有足够的信息来生成合适的代码。 语言实现采用编译还是解释方式，受到变量与类型绑定规则的严重影响。,静态绑定语言是面向编译的语言。 动态绑定语言是面向解释的语言。 动态类型绑定的语言，往往其作用域也是动态绑定的，因此，这类语言又称为动态语言。,M1是实际的机器， 汇编语言程序要在M1和汇编程序上执行， M1+汇编程序=M2 虚拟机M2的机器语言是汇编语言 M2+编译程序=M3 虚拟机M3以高级语言为机器语言(对用户而言),五.虚拟机：软件实现的机器,虚拟机是由实际机器加软件实现的机器。 若一台实际

15、机器配置上C语言编译程序，对用户来说，这台机器就是C语言的虚拟机（C语言机）。,六. 主要的强制式语言及其关系,1.(程序)单元:程序执行过程中的被独立调用单元：子程序,分程序,过程等 2.单元表示 编译时，单元表示为单元的源程序。 运行时，单元表示由一个代码段和一个活动记录组成，称为单元实例。,1.3 程序单元,3.活动记录:执行单元需要的信息,及该单元的局部变量的存储区。 4.非局部变量:一个程序单元可以引用未被本单元说明而被其它单元说明的变量。 5.全局变量:在一个程序中，各个程序单元都可以引用的变量。,6.引用环境,一个程序单元U可以引用的局部变量、非局部变量和全局变量。 局部变量绑定

16、于存储在U的当前活动记录中的数据对象，称为局部环境。,非局部变量绑定于别的(说明该非局部变量)程序单元的活动记录或全局数据区中的数据对象，称为非局部环境,以C语言为例,C程序运行时的存储空间： （1）程序代码区： 存储程序代码（编译后形成的二进制机器指令序列）,（2）数据静态存储区：存储程序的常量数据、全局数据和static数据。 （3）数据动态存储区： 活动记录(桟)：返回地址、CPU现场、形参、局部变量、临时变量 存储动态内存申请数据(堆),7.别名,同一单元的引用环境中有两个或多个变量绑定于同一数据对象，称这些变量具有别名。,8.副作用,对一个非局部变量的进行修改。,随着计算机技术的发展

17、,计算机应用,已经渗透到社会的各个领域 对程序设计语言也提出了新的要求(如可维护性,可靠性,可移植性等)，从而促进了语言的发展。,1.4 程序设计语言发展简介,目标:追求效率 FORTRAN=FORmula TRANslation .主要用于科学计算 .子程序独立编译 .COMMON语句实现了模块之间的通信,一. 早期的高级语言（50年代）,2. ALGOL 60 ALGOrithmic Language 60 .主要用于科学计算 .引入了分程序结构和递归过程 .采用BNF形式描述语法,3. COBOL COmmon Business Oriented Language .广泛应用于各种事务处

18、理领域 .引入了文件和数据描述 .类自然语言程序描述,60年代初，不再盲目地追求效率,出现了基于良好刻画数学原则的语言。 1. LISP .具有很强的符号处理能力 .统一的数据结构 .数据和程序统一的表示方法 .其基础是函数和函数作用,二.早期的突破,2. APL .支持函数式程序设计风格 .广泛应用于涉及大量矩阵运算的科学计算中 .具有丰富的操作符,3. SNOBOL 4 .主要用于字符串处理 .给出了一种与机器无关的宏功能,增加了程序的可移植性,PL/1 .希望将所有语言概念集成大全 .分程序概念和递归过程 .数据描述机能 .动态数据结构 .异常处理 .多任务机能 .可用于科学数值计算,数据处理等 .难以得到广泛的应用,三. 概念的集成（64年）,引入了许多有趣的概念 1. ALGOL 68 .以零型文法描述形成规则 .引入正交性和通用性原则,四. 再一次突破(60年代后期),正交性是从几何中借来的术语。如果两条直线相交成直角，它们们就是正交的。用向量术语来说，这两条直线互不依赖。 在计算技术中，该术语用于表示某种不相依赖性或者解耦性。如果两个或