编译原理第01章.

编译原理陈文宇电子科技大学计算机科学与工程学院陈文宇联系方式[e-mail]13808181782主楼B1-509（A区）51科研2#楼4课件下载：计算机学院网站师资队伍程序设计语言与编译--语言的设计与实现（3版）王晓斌陈文宇编著龚天富审2009电子工业出版社一.教材二.参考书1.龚天富等高级程序设计语言概论2.陈火旺等编译原理(3版)3AlfredV.Aho等赵建华等译编译原理—龙书机械工业出版社4AndrewW.Appel等赵克佳等译现代编译原理-虎书人民邮电出版社1.课程设置:64=56+8学时2.先修课程数据结构形式语言与自动机C语言三.关于教学四.成绩构成平时10%作业+课堂测验半期10%实验10%期末70%课堂点名、测验、作业累加到4次：取消考试资格五.教学内容涉及语言及其编译系统的设计要素、设计思想、设计方法和设计技术等1)上篇，程序设计语言的设计绪论、数据类型控制结构、语言设计2)下篇，程序设计语言的实现（编译）编译概述、词法分析、语法分析语义分析和中间代码生成代码优化和目标代码生成运行时存储空间的组织六.学习目标掌握设计和实现一个程序设计语言的基本思想和方法。具有分析、鉴赏、评价、选择、学习、设计和实现语言的基本能力。七.课程的重要性20世纪50年代，出现了与机器无关的编程语言（高级程序设计语言）。第一个编译器是由葛丽丝·穆雷·霍普（GraceMurrayHopper）于1952年为A-0(算术语言版本0)系统编写的。1957年由IBM的约翰·巴科斯领导开发的FORTRAN语言编译器则是第一个具备完整功能的编译器课程的重要性编译技术已经成为计算机科学中发展最迅速、最成熟的一个重要分支。编译技术集中体现了计算机科学发展的重要成果与精华。课程的重要性ACM图灵奖是授予在计算机技术领域作出突出贡献的科学家的最高奖励.自1966年设立以来，程序设计语言、编译理论与方法的方面的成果约占总数的1/3。课程的重要性从计算机应用的发展来看，编译技术在其中有着极其重要的和不可替代的作用。正是在编译技术的支持下，程序设计才从以繁琐的低级语言为工具，发展到以接近自然语言和数学语言的高级程序设计语言为工具;课程的重要性编译技术的发展极大地提高了软件开发的效率，深刻地影响着软件开发方法的变革。软件开发也从模块化的开发方法发展到了面向对象的开发方法。通过本课程的学习1)掌握和理解语言设计的理论和方法；2)掌握和理解编译系统的各组成部分的设计原理和实现技术；3)提高对语言、操作系统、计算机原理和体系结构等课程知识的综合理解。结论从计算机专业人才的知识结构和专业素养的培养而言编译原理是高等学校培养计算机专业人才的核心课程内容安排上篇程序设计语言的设计下篇程序设计语言的实现第一章绪论本章讨论程序设计语言中的一些重要概念，为深入了解程序设计语言打下基础。简介程序设计语言的发展历史。1.1引言1.程序设计语言的产生语言是人们交流思想的工具。人类在长期的历史发展过程中，为了交流思想、表达感情和交换信息，逐步形成了语言----自然语言。程序设计语言:人工语言程序设计语言programminglanguage程序设计语言本质上是一组规则：1）字母表的定义；2）词法规则：单词符号的形成规则一个单词对应一条形成规则，规定了该单词由哪些字母按照什么顺序进行排列程序设计语言3）语法规则：语法单位的形成规则（C语言语法单位包括：表达式、语句、函数、程序）；4）语义规则：单词符号和语法单位的含义规则；程序设计语言5)语用规则：语义规则的发展和延伸在一定的语境中使用单词和语法单位时体现出来的具体意义，要根据上下文明确单词和语法单位的具体意义6）其他规则：包括类型使用规则，参数传递规则，作用域规则等等。程序设计语言计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级语言的历程。2.程序设计语言的发展机器语言→汇编语言→高级语言用机器语言编写的程序由二进制指令组成，计算机可以直接执行。将机器语言符号化，产生了汇编语言。不同的机器语言和汇编语言：对于指令的操作码与功能、指令格式、寻址方式、数据格式等，不同的计算机有不同的规定：机器有关的语言通常称为低级语言。与机器无关的程序设计语言，通常称为高级语言。①直观、自然、易于理解②易读，易写，易于交流、存档③一般都是独立于机器的,易于移植3.高级语言的特点翻译:等价的变换。计算机可直接执行用机器语言编写的程序。而用汇编语言和高级语言编写的程序，机器不能直接执行必须将它们翻译成完全等价的机器语言程序才能执行将汇编语言程序翻译为机器语言程序的程序称为汇编程序（汇编器）将高级语言程序翻译为低级语言程序的程序称为编译程序（编译器）编写一个高级语言的编译程序的工作，通常称为对这个语言的实现。程序另一种执行方式：解释BASIC是最简单的高级语言，它不是编译执行，即不需要将源程序编译成目标程序，而是对源程序进行解释（分析），直接计算出结果。需要解释程序（解释器）支持LISP，ML，Prolog和Smalltalk均是解释型的语言。Java被当作一种解释型语言。翻译产生中间代码----字节码可以在Java虚拟机上运行解释执行特别适合于动态语言和交互式环境，因为可以立即得到计算结果，便于人机对话。解释器边翻译边解释执行，重复执行的语句需要重复翻译，比编译执行要花去更多的时间，执行效率较低。4.与编译有关的三种语言、三种程序源语言、工具语言、目标语言源程序、编译程序、目标程序5.高级语言涉及的三类人设计者、实现者、使用者1.2强制式语言一.程序设计语言的分类按设计的理论基础分为4类语言:强制式语言:基础是冯·诺依曼模型函数式语言:基础是数学函数(函数运算)逻辑式语言:基础是数理逻辑、谓词演算对象式语言:基础是抽象数据类型按语言的发展进程分类:第一代语言（机器语言）第二代语言（汇编语言）第三代语言（高级语言:命令式、过程式）第四代语言（说明性语言、超高级语言）新一代语言（函数式、逻辑式语言）1.基础存储器,控制器,处理器，ip2.特点①数据、指令以二进制形式存储(区别？);②存储程序（指令的组合）的工作方式；③程序顺序执行；可强制修改执行顺序④存储器的内容可以被修改。二.冯.诺依曼体系结构（模型）ip代码存储器（C）数据存储器（D）3.在命令式语言上的表现①变量存储单元及名称由变量的概念代替。变量可以代表一个或一组单元。②赋值存储(中间、最终的)计算结果。③重复语句顺序执行,指令存储在有限的存储器中,完成复杂计算时需要重复执行某些指令序列。冯.诺依曼体系结构(模型)实体：程序的组成部分，如变量，表达式、程序单元等。属性：实体具有的特性。绑定：实体与其各种属性建立起某种联系的过程称为绑定，实际上就是建立了某种约束。描述符：描述实体属性的表格。三.绑定（Binding)概念编译时能确定的特性--静态特性运行时才能确定的特性--动态特性静态和动态特性若绑定在运行之前(即编译时)完成，且在运行时不会改变，则称为静态绑定。若绑定在运行时完成，则称为动态绑定。四变量变量是对一个或若干个存储单元的抽象一个存储单元至少一个字节（也可以为2个字节4个字节…）一个变量至少占用一个存储单元赋值是对修改存储单元内容的抽象。变量用名字来标识(变量可以不具有名字--匿名变量)还有4个属性：作用域、生存期、值、类型1.变量的作用域可以访问该变量的程序范围。①静态作用域绑定:按照程序的语法结构定义变量的作用域（C语言等）。②动态作用域绑定:按照程序的执行动态地定义变量的作用域（SNOBL4语言等）。2.变量的生存期存储单元绑定于一个变量的时间区间编译阶段数据由变量和常量表示运行阶段数据由数据对象表示数据对象表示存储区和它保存的值。变量获得存储区的活动称为分配。变量分配的存储单元的个数--变量长度。运行前分配变量存储区--静态分配（FORTRAN语言）运行时分配变量存储区--动态分配（C、C++语言）分配原则，由语言(设计者)规定。动态分配通过两种途径来实现：用相关的语句显式提出请求(new)进入变量的作用域时自动分配。3.变量的值存储区单元的内容变量在生存期内绑定于存储单元，该存储单元中的内容以二进制编码方式表示的变量值，并绑定于变量。值按变量所绑定的类型来进行解释。访问匿名变量的基本方法是通过访问路径来实现的。变量的值在程序运行时可以通过赋值操作来修改，因此，变量与它的值的绑定是动态的。常数（量）的值不能修改。初始值问题变量获得所分配的存储单元，完成变量与存储区的绑定。此时，该变量绑定的值是什么呢？即变量初始化问题。不同的语言有不同的规则：⊙不初始化则出错⊙随机⊙缺省值04.变量的类型①与变量相关联的值，以及对这些值进行的操作的抽象。类型可用来解释变量绑定的存储区的内容(二进制编码)的意义；语言定义时，类型绑定于值和操作;语言实现时，值和操作绑定于某种机器二进制表示②变量类型可以静态或动态地进行绑定静态绑定：通过说明语句完成动态绑定：执行时隐式说明，且动态变化A5整型A12510一维数组A0A[2:3]0二维数组？动态绑定的语言实现采用解释方式处理更合适，因为对于一个不能确定变量类型的表达式，在运行之前没有足够的信息来生成合适的代码。语言实现采用编译还是解释方式，受到变量与类型绑定规则的严重影响。静态绑定语言是面向编译的语言。动态绑定语言是面向解释的语言。类型进行绑定动态的语言，往往其作用域也是动态绑定的，因此，这类语言又称为动态语言。①M1是实际的机器，②汇编语言程序要在M1和汇编程序上执行，M1+汇编程序=M2虚拟机M2的机器语言是汇编语言③M2+编译程序=M3虚拟机M3以高级语言为机器语言(对用户而言)五.虚拟机：软件实现的机器虚拟机是由实际机器加软件实现的机器。若一台实际机器配置上C语言编译程序，对用户来说，这台机器就是C语言的虚拟机（C语言机）。六.主要的强制式语言及其关系ALGOL60ALGOL68ALGOLWCOBOLFORTRANPL/1FORTRAN2000BASICPascalModula-2ConcurrentPascalAdaBCPLCC++Java1.(程序)单元:程序执行过程中的被独立调用单元：子程序,分程序,过程等2.单元表示编译时，单元表示为单元的源程序。运行时，单元表示由一个代码段和一个活动记录组成，称为单元实例。1.3程序单元3.活动记录:执行单元所需要的信息,及局部变量所绑定的数据对象的存储区4.非局部变量:一个程序单元可以引用被其它单元说明的变量。5.全局变量:在一个程序中，各个程序单元都可以引用的变量。6.引用环境引用环境：一个程序单元可以引用的局部变量、非局部变量和全局变量。局部变量绑定于存储在程序单元的当前活动记录中的数据对象，称为局部环境。非局部变量绑定于别的(说明该非局部变量)程序单元的活动记录或全局数据区中的数据对象，称为非局部环境以C语言为例C程序运行时的存储空间：（1）程序代码区：存储程序代码（编译后形成的二进制机器指令序列）（2）数据静态存储区：存储程序的常量数据、全局数据和static数据。（3）数据动态存储区：①活动记录：存储返回地址、CPU现场、形参、函数定义变量、临时变量②存储动态内存申请数据（malloc）7.别名同一单元的引用环境中有两个或多个变量绑定于同一数据对象，称这些变量具有别名。8.副作用对一个非局部变量的进行修改。随着计算机技术的发展,计算机应用,已经渗透到社会的各个领域对程序设计语言也提出了新的要求(如可维护性,可靠性,可移植性等)，从而促进了语言的发展。1.4程序设计语言发展简介目标:追求效率1.FORTRAN=FORmulaTRANslation.主要用于科学计算.子程序独立编译.COMMON语句实现了模块之间的通信一.早期的高级语言（50年代）2.ALGOL60ALGOrithmicLanguage60.主要用于科学计算.引入了分程序结构和递归过程.采用BNF形式描述语法3.COBOLCOmmonBusine