《编译原理简明教程》普通高等教育“十二五”规划计算机教材---太原理工大学---计算机科学与技术学院---冯秀芳、崔冬华、段富等第一章 引言
第二章 形式语言理论基础第三章 自动机理论基础第四章 词法分析第五章 语法分析—自顶向下分析方法第六章 语法分析—自底向上分析方法
第七章 语义分析及中间代码的生成第八章 代码优化第九章 目标代码的生成第十章 符号表第十一章 目标程序运行时的存储组织与分配第十二
章 出错处理第十三章 编译程序自动生成工具简介第十四章 面向对象语言的编译第十五章 并行编译技术目 录第十四章 面向对象语言
的编译 学习目标了解和掌握面向对象的基本概念、类和成员的属性构造以及面向对象编译器的特性了解和掌握面向对象语言的编译
了解和掌握面向对象的动态存储分配 14.1 概述14.2 面向对象语言的编译14.3 面向对
象的动态存储分配目 录14.1 概述14.1.1 面向对象语言的基本特征对象之间通过消息相互通信封装继承多态性 1
4.1 概述14.1.2 类和成员的属性构造声明类的文法规则： (1) dec→classdec(2) class
dec→ class class_id {memberspec}| class class_id : class_id {memb
erspec}(3) memberspec→ memberdec memberspec | memberdec(4) member
dec→accessspec : type var ;| accessspec:funcdec;(5) accessspec→pr
ivate | protected | public(6) type→comtype|classtype(7) classtype
→ID(8) var→ID|ObjDef(9) funcdec→type ID (paramlist); | type ID (p
aramlist) funcbody; |ID (paramlist);|ID (paramlist) procbody;类名的属
性和结构 类名的特有属性包括种类、继承链和类的成员集 。(1)种类：种类属性用于区分有效类、延迟类、继承类、基类等 。如果一个类定
义的全部成员中至少有一个成员尚未被具体实现，该类就是一个不能用来创建对象的类，我们称之为延迟类。如果一个类定义中的全部成员都已经按
照某种方式具体实现，该类就是一个可以用来创建对象的类，我们称之为有效类。类名的属性和结构类名的特有属性包括种类、继承链和类的成员集
。(2)继承链：对于继承类来说，可以有若干个父类(被直接继承的类)，并且它们在类的定义中的次序必须是严格确定的 。类名的属性和结
构这两个成员集的具体实现有两种方式：① 这些成员(包括属性和方法)名的符号表项与它们的类名的符号表项放在一张符号表中，而这两个成员
集中存放的是指向各自对应的符号表项的指针；② 每个类构造两张子符号表，即类的属性成员符号表和类的方法成员符号表，这两个成员集中存放
这些成员名的符号表项。类名的特有属性包括种类、继承链和类的成员集 。(3)类成员集 ：类具有属性成员和方法成员，可以用两张成员表来
表示。类成员名的属性及其结构 类的定义中，属性成员是某个类型的实例，这种属性成员的类型有两种方式：其一，定义该属性成员的类型在包含
该成员的类型之外的另一个类型中进行定义；其二，定义该属性成员的类型在包含该成员的类型之内的一个嵌套的类型定义。如果属性成员的类型嵌
套定义在属性成员所在的类中，属性的结构就会出现嵌套的情况，为了避免下推处理，当一个类中有多个嵌套类型定义的属性成员时，这些局部定义
的类型名的符号表项可以组成一张符号表， 类成员名的属性及其结构类成员的特有属性如下。① 类成员的导入属性。通常，类中的成员包括从
父类继承的成员和该类自定义的成员，当从父类中继承的成员被重定义或重命名时，需要给出相应的标志。类成员名的属性及其结构② 类成员的访
问权限属性。类成员被外部对象访问的权限有三种：类的公有成员、类的私有成员和类的保护成员。属性和方法的私有性是由编译器的类型检查阶段
来保证的，在类的成员符号表项中，一个域用来指出该成员的访问权限。 类成员名的属性及其结构③类成员的延迟属性。如果一个类定义的全部成
员中至少有一个成员尚未被具体实现，该类就是一个不能用来创建对象的类，我们称之为延迟类，尚未被具体实现的成员，我们称之为延迟成员。在
成员符号表项中用一个域指出该成员是类的延迟成员，还是类的有效成员， 14.1.3 面向对象编译程序的特点词法和语法分析 由于类本
身是一种数据类型，它也作为符号表中的一个表项，但面向对象建模具有较高的抽象层次，其语义处理与语法分析的关系更密切，整个分析流程、编
译程序内部数据结构的组织和运行时的环境都和传统的编译程序有一定差别。语义分析 由于类及其对象具有的封装、继承、多态性等语言特征，不
仅使静态语义分析更为复杂，也使运行时环境更为复杂。 内存管理 14.2 面向对象语言的编译14.2.1 单一继承 1．属性编译在
仅支持单继承的语言中，每个类最多只能继承一个父类，子类不仅可以访问该类中定义的新方法，还可以访问父类中的方法。可以采用下面两种方式
处理。① 简单的前缀技术来处理。如果类B是由类A扩展得到的，则将类B中从父类A继承过来的属性放在类B符号表的开始处，并保持这些属性
与类A符号表中相同的顺序；而类B中定义的特有属性放在继承属性的后面。② 在符号表中，对子类进行处理时，仅给出在子类中直接定义的属性
，而对父类中定义的成员，则通过在子类的符号表项中增加指向父类的指针来表示，当需要对父类属性进行相关处理时，可根据此指针获取父类的相
关信息。 14.2 面向对象语言的编译14.2.1 单一继承 2．方法编译编译一个方法类似于编译一个过程：方法被转
换成驻存在指令空间中一个特定地址的机器代码。在语义分析阶段，每个对象的符号表项中有一个指向其类符号表的指针，每个类的符号表有一个指
向其父类的指针和一张方法的链表，每一个方法都有一个地址。①对于静态方法，一些面向对象语言允许将方法声明为静态的，调用c.f(?)(
其中c是类C的对象)时执行的机器代码取决于变量c的类型。 ②对于动态方法，如果类B中的方法f是从父类A中继承的，且类B对方法f进行
了重载，则编译期间，调用f时无法确定是类B的一个对象还是类A的一个对象。为了解决该问题，类符号表必须包含一个向量，该向量中每个方法
名对应一个方法实例。 14.2 面向对象语言的编译14.2.2 多重继承 在支持多重继承的语言中，一个类可以有多个直接父类。使用
多重继承的目的在于使一个对象同时具有多个对象的表达能力。 例如，假定有类M包含属性m1、m2和方法f 1、f 2，类E包含属性e1
和方法f 3、f 4，类T继承了类M和类E，但增加了属性t1，并且重新定义了方法f 2、f 4，增加了方法f 5。 14.2 面
向对象语言的编译14.2.2 多态性 当类B继承类A并且该语言允许“类B的指针”类型的指针能够赋值给一个“类A的指针”类型的变量时
，那么该语言支持多态性。多态性的实现要求一种新的操作，即指针supertyping，它将指向子类B对象的指针转换为指向其父类A对象
的指针。假定类A有属性a1、a2和方法f1、f2，类B是类A的子类，类B通过增加属性b1和方法f3来扩展A类，例如：Class B
b=…;Class A a=b;在上面的语句中，第二行代码被翻译成Class A a=covert_ptr_to_B_to
_ptr_to_A(b);14.2 面向对象语言的编译14.2.4 动态绑定 动态绑定是语言处理多态的机制，类的成员函数的行为能
根据调用它的对象类型自动做出适应性调整，而且调整发生在程序运行时。假定类A包含属性a1、a2和方法f1、f2，类B是类A的子类，类
B增加属性b1和方法f3，并重载类A中的方法f2。例如： a : A； b : B；a是多态引用，因而根据多态引用规则
：a可引用类B的对象，对方法f2的动态绑定情况如下：? a.f2(?)引用类A的对象时，绑定类A定义的方法f2；当执行a: =
b之后，绑定类B重新定义的方法f2。? b.f2(?)只能绑定类B重新定义的方法f2。14.2 面向对象语言的编译14.2.4
动态绑定 Java语言包括了一种扩展，这种扩展由所谓的接口组成。接口与类相似，由许多方法说明组成，但接口只有常量和抽象的方法。接
口不能像对象那样实例化，但可以声明接口类型的Java变量，并从它们的接口声明中调用方法，该Java变量实质上就是指向对象的指针。编
译程序必须为类所实现的每一个接口建立单独的符号表，每个符号表只包含该接口声明中方法的入口，由入口引用对象类型的方法。 14.3
面向对象的动态存储分配14.3.1 对象的存储区管理方式 对象的存储管理采用了3种模型：静态存储区管理、栈式存储区管理、堆式存储区
管理。在静态模型中，程序装入或开始执行时为所有对象一次分配所有空间，一个实体在整个软件运行过程中最多只能与一个运行时对象联系。在栈
式模型中，一个实体在运行时可以相继与多个对象联系，它以先进后出的方式分配和释放对象。在堆式模式中，存储分配是完全动态的，对象通过显
式的请求动态创建，堆式模型最具有通用性，它是面向对象的计算所需要的。14.3 面向对象的动态存储分配14.3.2 静态模型和栈式
模型废弃单元的回收 在静态模型下，每个对象只与一个实体联系，执行时只要实体存在，就要保留对象的空间，因此一般情况下静态模型不存在废
弃单元回收的问题，在栈式模型下，与某一实体联系的对象可以在栈中分配。在分程序结构的语言中，声明实体的同时为对象分配空间，整个程序可
以只使用一个栈。例如，每当执行一次函数调用时，就将该函数运行所需的所有局部变量进栈，在栈顶为该函数建立运行的工作区，并且每当一个函
数执行结束时，它在栈顶的工作区退栈，该函数运行所占用的空间得到了释放，释放的空间回收后可提供给下次调用的函数使用。14.3 面向
对象的动态存储分配14.3.3 堆式模型废弃单元的回收 堆中分配且通过任何程序变量形成的指针链都无法到达的对象称为不可到达的对象。
不可到达的对象是废弃单元，需要回收。废弃单元的回收不是由编译器完成的，而是由运行时系统完成的，运行时系统是与编译好的代码连接在一起
的一些支持程序。废弃单元回收技术 主要有：标记-清扫技术 引用计数技术 复制式收集 分代收集14.3 面向对象的动态存储分配14
.3.3 堆式模型废弃单元的回收 1、标记-清扫技术 实体和堆分配的对象构成了一个有向图，每一个实体是图中的一个根。如果从某个根节
点r出发，存在由有向边r→…→n组成的一条路径，则称这个结点n是可到达的对象，图搜索算法可以标记出所有可到达的对象。2、引用计数技
术 每一个对象都设置了一个统计量，用于对该对象的引用进行计数，该统计量称为对象的引用计数。它与每个对象存储在一起，当该引用计数为0
时，对象可以被回收。 引用计数技术实现简单，但它存在两个主要的问题。① 无法回收构成环的垃圾； ② 增加引用计数所需的操作代价(时
间和空间)非常大。14.3 面向对象的动态存储分配14.3.3 堆式模型废弃单元的回收 3、复制式收集 堆中的可到达部分是一个有
向图，堆中的对象是图中的结点，指针是图中的边，每一个原对象在图中是一个根。复制式垃圾收集遍历这个图(称为源空间)，并在堆的新区域(
称为目标空间)建立一个同构的副本。副本目标空间是紧凑的，它占据连续的、不含碎片的存储单元。原来指向源空间的所有的根在复制之后变成指向目标空间副本，在此之后，整个源空间便成为不可达的。14.3 面向对象的动态存储分配14.3.3 堆式模型废弃单元的回收 4、分代收集 将堆划分成若干“代”，最年轻的(即最近分配的)对象属于G0代，所有属于G1代的对象都比G0代的对象“老”，所有属于G2代的对象都比G1代的对象“老”，依次类推。为了只收集G0代中的对象，回收器只需要从根结点开始进行深度优先标记或宽度优先复制。这些根不仅仅是原对象，其中还包括G1，G2，…中那些指向G0中对象的指针。为了避免在所有的G1，G2，…中搜索G0的各个根节点，让编译好的程序记住这种从老对象指向新对象的指针。 |
|
