编译原理运行时环境课件

machunyan西北工业大学软件与微电子学院1第7章运行时环境(存储空间)当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息例如为源程序中出现的一些量（常量、变量及某些数组等）分配运行时的存储空间。目标代码要从操作系统得到一块存储区，用于它的运行。machunyan西北工业大学软件与微电子学院1第7章运行machunyan西北工业大学软件与微电子学院2存储分配是在运行阶段进行的，但编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。(举例说明：函数调用分析.txt)目标代码运行时，存储空间的组织称为目标代码的运行时环境。第7章运行时环境(存储空间)(续)machunyan西北工业大学软件与微电子学院2存储分配是在machunyan西北工业大学软件与微电子学院3运行时环境有三个类型：完全静态环境(fullystaticenvironment)、基于栈的环境(stack-basedenvironment)，以及完全动态环境(fullydynamicenvironment)。这3种类型的混合形式也是可能的。第7章运行时环境(存储空间)(续)machunyan西北工业大学软件与微电子学院3运行时环境有machunyan西北工业大学软件与微电子学院4

7.1程序执行时的存储器组织7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制7.2完全静态的运行时环境第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院47.1machunyan西北工业大学软件与微电子学院57.1程序执行时的存储器组织目标代码运行时,操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分:由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。machunyan西北工业大学软件与微电子学院57.1程序执machunyan西北工业大学软件与微电子学院67.1程序执行时的存储器组织（续）代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，在编译时所有目标代码的地址都是可计算的，程序执行结束后代码区域内存由系统释放。全程/静态区域：静态数据区用来存放那些具有绝对地址的数据和变量(如静态变量和全程变量)；编译器可以确定其所占用存储空间的大小，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，程序执行结束后由系统释放。本章案例分析.docmachunyan西北工业大学软件与微电子学院67.1程序执7.1程序执行时的存储器组织（续）栈区：函数中的形参和在函数中定义的局部变量以及局部临时变量（C、C++、Java），这些变量分配在栈区，每次函数执行的时候会在栈中为函数的执行分配相应的存储区，而在函数执行完毕后，释放相应的存储区。编译器“知道”存在栈中的具体数据所占内存大小和内存分配和释放的“时刻”；machunyan西北工业大学软件与微电子学院77.1程序执行时的存储器组织（续）栈区：函数中的形参和在函数堆区：供用户动态申请存储空间，编译器“不需要”知道究竟得从heap中分配多少空间，也不需要知道从heap上分配的空间究竟需要存在多久。在c中由malloc，free运算产生释放的存储空间，在c++中由new和delete运算符作用的存储空间，以及在Java中由new分配的存储空间都在堆中进行分配。machunyan西北工业大学软件与微电子学院87.1程序执行时的存储器组织（续）堆区：供用户动态申请存储空间，编译器“不需要”知道究竟得从hmachunyan西北工业大学软件与微电子学院9machunyan西北工业大学软件与微电子学院9machunyan西北工业大学软件与微电子学院10machunyan西北工业大学软件与微电子学院10machunyan西北工业大学软件与微电子学院117.1程序执行时的存储器组织（续）在C语言中,采用以函数（或过程）为单位的动态存储分配方案：当一函数被调用时，就在栈顶为该函数分配所需的数据空间(过程活动记录)，当一个函数工作完毕返回时，它在栈顶的数据空间(过程活动记录)也即释放。过程的活动记录(activationrecord,AR)是一段连续的存储区，用于存放函数的一次执行所需要的信息，当调用或激活函数时，必须为被调用函数的活动记录分配空间。machunyan西北工业大学软件与微电子学院117.1程序活动记录存放的信息至少应包括以下几个部分：machunyan西北工业大学软件与微电子学院12存放主调函数为被调函数提供的实参信息;存放目标程序临时变量的值;存放本次执行中的局部数据用于指向主调函数的活动记录的控制链和返回地址;7.1程序执行时的存储器组织（续）活动记录存放的信息至少应包括以下几个部分：machunyanmachunyan西北工业大学软件与微电子学院137.1程序执行时的存储器组织（续）实参返回地址控制链临时变量和局部数据实参返回地址控制链临时变量和局部数据调用者的活动记录被调用者的活动记录调用者的职责machunyan西北工业大学软件与微电子学院137.1程序C语言所调用函数的活动记录示例(函数调用分析中的举例)控制链：指向调用函数活动记录的一个地址。machunyan西北工业大学软件与微电子学院14b:2a:1该函数调用结束时的返回地址(00401014)主调函数的控制链c:3栈底栈顶7.1程序执行时的存储器组织（续）当前函数的控制链C语言所调用函数的活动记录示例(函数调用分析中的举例)macmachunyan西北工业大学软件与微电子学院157.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院157.1程machunyan西北工业大学软件与微电子学院167.2完全静态的运行时环境在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的条件是：每个数据名所需的存储空间的大小都是常量不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构过程不可递归调用machunyan西北工业大学软件与微电子学院167.2完machunyan西北工业大学软件与微电子学院17整个程序存储器如右所示：7.2完全静态的运行时环境（续）machunyan西北工业大学软件与微电子学院17整个程序7machunyan西北工业大学软件与微电子学院187.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院187.1程machunyan西北工业大学软件与微电子学院197.3基于栈的运行时环境在一个所有函数都是全局的、函数定义不允许嵌套，但允许函数递归调用的程序设计语言(例如C语言)中，基于栈的动态运行时环境有两个指针：sp:栈顶部(topofstack)指针；对于x86系统来说，它采用sp或esp寄存器存储栈顶部的地址；注：用它只可访问栈顶machunyan西北工业大学软件与微电子学院197.3基machunyan西北工业大学软件与微电子学院207.3基于栈的运行时环境（续）fp(framepoint)：控制链指针，即存储当前活动记录的控制链（即一个地址），对于x86系统，它采用bp或ebp寄存器存储当前活动记录的控制链，其作用如下：1.通过该指针可以访问主调函数的活动记录；即允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。2.通过该指针可以访问当前执行函数的实参和局部变量；machunyan西北工业大学软件与微电子学院207.3基machunyan西北工业大学软件与微电子学院21b:2a:1该函数调用结束时的返回地址(cs:eip)00401014主调函数的控制链(main.ebp)void__stdcallf_stdcall(inta,intb){ intc; c=a+b;}c:3esp栈底栈顶ebp7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院21b:2该函machunyan西北工业大学软件与微电子学院22当一个函数被调用时，在栈顶为该函数分配所需的数据空间(过程活动记录)如下：将实参的值压入在该函数对应的新活动记录中。将被调函数执行完毕后的返回地址压入在新的活动记录中。完成到被调用的过程代码一个转移。将主调函数的fp作为控制链压入到新的活动记录中。改变fp以使其指向新的活动记录(将sp复制到fp中)将该函数的局部变量和局部临时变量压入到新的活动记录中。7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院22当一个函数machunyan西北工业大学软件与微电子学院23b:2a:1该函数调用结束时的返回地址(cs:eip)00401014主调函数的控制链(main.fp)C语言当前执行函数的活动记录示例：c:3sp栈底栈顶fp7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院23b:2该函machunyan西北工业大学软件与微电子学院24当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：①将fp复制到sp中。②将控制链装载到fp中。③完成到返回地址主调函数的一个转移。④改变sp以弹出实参。7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院24当被调函数machunyan西北工业大学软件与微电子学院25例：计算两个非负整数最大公约数的c代码如下：#include<studio.h>intx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v)}main(){scanf(“%d%d”,&x,&y);printf(“%d\n”,gcd(x,y));return0;}7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院25例：计算两machunyan西北工业大学软件与微电子学院26x:15y:10全局/静态区域main的活动记录sp,fpv:10u:15返回地址main的fp第一次调用gcd时的活动记录sp,fp第二次调用gcd时的活动记录v:5u:10返回地址第一次调用gcd时的fp第三次调用gcd时的活动记录v:0u:5返回地址第二次调用gcd时的fpsp,fpsp,fp栈生长方向自由空间7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院26x:15全machunyan西北工业大学软件与微电子学院27例：考虑下列程序清单的c代码。intx=2;voidg(int);voidf(intn){staticintx=1;g(n);x--;}voidg(intm){inty=m-1;if(y>0){f(y);x--;g(y);}}main(){g(x);return0;}画出至第二次对g调用时，程序的运行时环境：7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院27例：考虑下machunyan西北工业大学软件与微电子学院28x:2x（fromf）:1全局/静态区域main的活动记录sp,fpm:2返回地址main的fpy:1第一次调用g时的活动记录fpsp第一次调用f时的活动记录n:1

返回地址第一次调用g时的fpsp,fp第二次调用g时的活动记录m:1返回地址第一次调用f时的fpy:0fpsp栈生长方向自由空间7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院28x:2全局machunyan西北工业大学软件与微电子学院29目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院29目标代码的machunyan西北工业大学软件与微电子学院30对名字的访问：在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。对函数参数和局部变量而言，在大多数的语言中，如果函数的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定，每个实参和局部声明的偏移量可由编译程序计算。machunyan西北工业大学软件与微电子学院30对名字的访machunyan西北工业大学软件与微电子学院31m:2返回地址控制链

y:1fpmOffsetyOffsetmOffset=+8yOffset=-4高端地址低端地址对名字的访问：（续）machunyan西北工业大学软件与微电子学院31m:2machunyan西北工业大学软件与微电子学院32例：考虑下面的C过程Viodf(intx,charc){inta[10];doubley;

……}cx

返回地址控制链a[9]…a[1]a[0]yfpcOffsetaOffsetxOffsetyOffsetxOffset=+8cOffset=+12aOffset=-40yOffset=-48现在对a[i]访问，要求计算地址：(-40+4*i)(fp)对名字的访问：（续）对f调用的活动记录为：machunyan西北工业大学软件与微电子学院32例：考虑下machunyan西北工业大学软件与微电子学院33目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院33目标代码的machunyan西北工业大学软件与微电子学院34局部临时变量：考虑C表达式：x[i]=(i+j)*(i/k+f(j))，在这个表达式从左到右的求值计算中，在对f的调用过程中需要保存中间结果：x[i]的地址、i+j的和、i/k的商。这些中间值可计算到寄存器中，根据寄存器进行保存和恢复；或者可将它们作为临时变量存储在对f调用之前的运行时栈中。如下所示：machunyan西北工业大学软件与微电子学院34局部临时变machunyan西北工业大学软件与微电子学院35…

返回地址控制链…x[i]的地址i+j的结果i/j的结果fp(栈的其余部分)sp临时栈调用f（将要创建的）时的新活动记录包含表达式过程的活动记录自由空间局部临时变量：（续）machunyan西北工业大学软件与微电子学院35fp(栈的machunyan西北工业大学软件与微电子学院36目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院36目标代码的machunyan西北工业大学软件与微电子学院37嵌套声明也出现了与局部临时变量同样的问题。考虑以下的C代码：Voidp(intx,doubley){chara;inti;…A:{doublex;intj;…}…B:{char*a;intk;…}…}嵌套声明：machunyan西北工业大学软件与微电子学院37嵌套声明也machunyan西北工业大学软件与微电子学院38x:y:

返回地址控制链a:i:x:j:fp(栈的其余部分)sp块A的分配区调用p时的活动记录自由空间嵌套声明：（续）一个简单的处理办法是按照与临时表达式相类似的办法在嵌套的块中处理声明，并在进入块时在栈中分配它们。当进入块A后，运行时栈如下所示：machunyan西北工业大学软件与微电子学院38x:fp(machunyan西北工业大学软件与微电子学院39x:y:

返回地址控制链a:i:a:k:fp(栈的其余部分)sp块B的分配区调用p时的活动记录自由空间当进入块B后，运行时栈如下所示：嵌套声明：（续）machunyan西北工业大学软件与微电子学院39x:fp(machunyan西北工业大学软件与微电子学院40目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院40目标代码的machunyan西北工业大学软件与微电子学院41处理可变长度的数据有时编译程序必须处理数据变化的可能性，表现在数据对象的数量和每个对象的大小上。发生在支持基于栈的环境的语言中的一种情况如下：①调用中的自变量的数量可根据调用的不同而不同。printf(“%d%s",n,prompt);printf(“%d%d%d”,3,4,50);通常，C编译程序一般通过把调用的自变量按相反顺序(inreverseorder)压入到运行时栈来处理这一点。machunyan西北工业大学软件与微电子学院41处理可变长machunyan西北工业大学软件与微电子学院42printf(“%d%d%d”,3,4,50);设置一指针ap；让ap指向第一个可变参数(地址为ebp+控制链所占的空间+返回地址所占的空间+固定参数所占的空间)，即3所在的空间；返回3，ap的值加4即指向4所在的存储空间……,通过指针ap的移动读取所有的可变参数，根据固定参数“%d%d%d”，该字符串中每出现一个“%d”就执行一次；固定参数指出了后面的可变参数的个数；清除变量ap。处理可变长度的数据(续)machunyan西北工业大学软件与微电子学院42printmachunyan西北工业大学软件与微电子学院437.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院437.1程machunyan西北工业大学软件与微电子学院447.4.1对象类型在大多数面向对象的语言中，对象都有构造函数和析构函数，它们分别在创建对象和释放对象时被调用。假定我们有一对象类A，它有方法m1,m2以及字段a1和a2。那么类A对象的运行时表示有包含字段a1和a2记录组成：a1a2m1_Am2_A另外，编译程序维护着一张类A的编译时方法表：7.4动态存储器machunyan西北工业大学软件与微电子学院447.4.1在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法选择由编译程序内的识别过程来实现。即通过一个指向对象的指针，方法可以像函数一样实现。因此方法m2_A可以翻译为c语言中的函数。

voidm2_A(class_A*this,inti){

方法m2_A的程序体，通过this->x访问任一对

象字段x}方法的调用a.m2(3)可以翻译成m2_A(&a,3)machunyan西北工业大学软件与微电子学院457.4动态存储器（续）在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法machunyan西北工业大学软件与微电子学院46继承特性现在假定类B通过增添方法m3和字段b1来扩展类A,那么类B的运行时表示如下：a1a2m1_Am2_Ab1另外类B的方法编译时表如下：m3_B7.4动态存储器（续）machunyan西北工业大学软件与微电子学院46继承特性现machunyan西北工业大学软件与微电子学院47方法重载假定上例中类B重新定义了方法m2，那么A中方法m2的定义既是它唯一的声明也是它的第一次定义，而它在类B中的定义为重定义。为使名字既可以反映声明它的类，也可以反映定义它的类。方法的名字可有三部分组成：方法名、声明方法的类名、定义方法类名。各部分之间用下划线（—）分开。因此在类A中声明在类B中定义的方法m2其名字记为m2_A_B。方法重载影响方法的编译时表，现在类A的方法的编译时表如下：m1_A_Am2_A_Am1_A_Am2_A_Bm3_B_B类B的方法的编译时表如右：7.4动态存储器（续）machunyan西北工业大学软件与微电子学院47方法重载假现在假定a是类A的一个对象，而b是类B的一个对象方法调用a.m2(…)将翻译成对m2_A_A的调用，而方法调用b.m2(…)将翻译成对m2_A_B的调用。2_A_A在类A中声明和定义。m2_A_B在类A中生明，在类B中定义。m2_A_A翻译形式为：voidm2_A_A(Class_A*this,inti);m2_A_B的翻译形式为：voidm2_A_B(Class_B*this,inti);machunyan西北工业大学软件与微电子学院487.4动态存储器（续）现在假定a是类A的一个对象，而b是类B的一个对象machunmachunyan西北工业大学软件与微电子学院49多态性当类B继承类A，并且该语言允许“类B的指针”类型的指针能够赋给一个“类A的指针”类型的变量时，那么该语言支持多态型。例如：ClassB*b=…;ClassA*a=b;则第二行被翻译成：classA*a=convert_ptr_to_B_to_ptr_to_A(b);现在，过程convert_ptr_to_B_to_ptr_to_A()为一编译时类型的操作,它将指向子类B的一个对象指针转换为指向其父类A对象的指针。因为类B的对象也是从类A的字段开始，因而指针的值并不需要改变，唯一影响的是改变了指针的类型：7.4动态存储器（续）machunyan西北工业大学软件与微电子学院49多态性当类machunyan西北工业大学软件与微电子学院50a1a2b1指向B的指针指向B中A的指针现在同一指针指向了不同类的对象7.4动态存储器（续）machunyan西北工业大学软件与微电子学院50a1a2bmachunyan西北工业大学软件与微电子学院517.4动态存储器（续）动态绑定：类型classA*的指针p可能引用了类B的一个对象，动态绑定认为如果实际上为类B的对象，那就应该调用m2_A_B,如果实际为A的对象，那么就应该调用m2_A_A.对于方法调用p->m2(3)p是一指向类A对象指针，可以将p->m2(3)被翻译成如下形式：switch(dynamic_type_of(p)){caseDynamic_class_A:m2_A_A(p,3);caseDynamic_class_B:m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);}当p为一指向类B对象指针时，可以将p->m2(3)翻译为：m2_A_B(p,3);machunyan西北工业大学软件与微电子学院517.4动machunyan西北工业大学软件与微电子学院52对于上述的翻译方法，每一个对象的类型信息实现为一个指向分派表的指针，如下图所示(分派表是存储方法地址的记录，下图分派表存储的是方法m1_A_A，m2_A_B和m1_B_B的地址)a1a2b1指向B的指针指向B中A的指针m1_A_Am2_A_Bm3_B_B类B对象的表示分派表B-objectB-class7.4动态存储器（续）machunyan西北工业大学软件与微电子学院52对于上述的machunyan西北工业大学软件与微电子学院537.4.2堆管理7.4动态存储器（续）对于允许程序为变量在运行时动态申请和释放存储空间的语言,采用堆式分配是最有效的解决方案.堆式分配的基本思想是,为运行的程序划出适当大的空间(称为堆Heap),每当程序申请空间时,就从堆的空闲区找出一块空间分配给程序,每当释放时则回收之.machunyan西北工业大学软件与微电子学院537.4.2machunyan西北工业大学软件与微电子学院54堆分配的必要性7.4动态存储器（续）在C中处理链表等结构时,常常随机地插入或删除一些结点,利用指针变量和结构类型,可动态地生成新结点(使用malloc()函数),或删除之(使用free()函数).例如structnode{chardata;structnode*next;}定义了链表的结点,下面函数可在表的尾部添加新结点:

voidAppend(structnode*head,charch){structnode*p=head;while(*p)p=p->next;p->next=malloc(sizeof(structnode));p->next->data=ch;p->next->next=NULL;}还可用下面的函数在表头删除一结点:voidDelete(structnode*head){structnode*p=head;if(*p){head=head->next;free(p);}}machunyan西北工业大学软件与微电子学院54堆分配的必machunyan西北工业大学软件与微电子学院55堆存储管理的实现7.4动态存储器（续）将存储空间划分为若干存储块;用户可随机地申请或释放一个或多个块;在存储空间中建立两个队列:空闲队列和忙队列,空闲队列拉成链,链首用FREE指针指明,忙队列用一(已占块)记录表记录各占用块的首址及大小信息(也可用链进行记录).申请时可按需要找到合适的块分配之(分配策略有最佳分配或随机分配等);释放时将该块插入到空闲队列(能合并时可合并),并从占用记录表中删除相应的项.machunyan西北工业大学软件与微电子学院55堆存储管理machunyan西北工业大学软件与微电子学院567.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院567.1程machunyan西北工业大学软件与微电子学院577.5参数传递机制voidinc2(intx)/*incorrect!*/{++x;++x;}voidinc2(int*x)/*nowok*/{++(*x);++(*x);}值传递：值传递的处理方法是：进入过程时,送入形参对应的形式单元的是相应实参的值；过程体中对形参的任何赋值都按对形式单元的直接访问来产生代码。形参和实参不是同一个存储单元。因此,一旦把实参之值送入对应形式单元之后,在执行过程体期间,除了以实参值作为形参的初值进行运算之外,将不再与实参发生任何联系。由此可见,过程执行的结果决不会改变实参之值。machunyan西北工业大学软件与微电子学院577.5参machunyan西北工业大学软件与微电子学院58voidinc2(int&x)/*C++referenceparameter*/{++x;++x;}7.5参数传递机制（续）引用传递：将实参的地址写入相应的形式单元，过程体中对形式参数的任何引用或赋值,都按对相应形式单元间接访问的寻址方式为其产生代码。所以，执行过程时,对形参的赋值将会影响相应实参之值。在C++中，是通过在参数说明中使用特殊字符&来得到引用传递：machunyan西北工业大学软件与微电子学院58voidmachunyan西北工业大学软件与微电子学院597.5参数传递机制（续）引用传递不要求复制被传递的值，这与值传递不同。当要复制的值是一个较大的结构时，在这种情况下，引用传递能够做到值传递而无需覆盖值的拷贝。当要复制的值是一个较大的结构时，如果禁止实参变量的值有任何变化，在C++中可将调用写作：voidf(constMuchData&x)其中的MuchData是带有大型结构的数据类型。这仍是引用传递，但是编译程序还必须执行一个静态检查：x从不出现在一个赋值的左边或是被改变。machunyan西北工业大学软件与微电子学院597.5参machunyan西北工业大学软件与微电子学院60已知C程序：#include<stdio.h>inti,b[4];voidfunc(intx,inty){i=2;x+=2;b[i]=15;y+=3;b[i+1]=20;}voidmain(){ for(i=0;i<4;i++)b[i]=i; i=1; func(b[i],b[i+1]); for(i=0;i<4;i++)printf(“%d”,b[i]); printf(“%d\n”,i);}1．给出该程序的输出结果；2．若C语言采用的是引用调用的形实结合方式，输出结果又如何？7.5参数传递机制（续）machunyan西北工业大学软件与微电子学院60已知C程序machunyan西北工业大学软件与微电子学院61值结果传递在过程中复制和使用实参的值，然后当过程退出时，再将形参的最终值复制回实参变量的地址。因此，这个方法有时也被称为复制进，复制出，或复制存储。在调用p之后，若使用了引用传递，则a的值为3；若使用了值结果传递，则a的值为2。例如，在以下的代码中(C语法)：voidp(intx,inty){++x;++y;}main(){inta=1;p(a,a);return0;}7.5参数传递机制（续）machunyan西北工业大学软件与微电子学院61值结果传递machunyan西北工业大学软件与微电子学院62名字传递实参的名称或是它在调用点上的结构表示取代了它对应的形式参数的名字。main(){i=1;a[1]=1;a[2]=2;p(a[i]);return0;}inti;inta[10];voidp(intx){++i;++x;}对p的调用的结果是将a[2]设置为3并保持a[1]不变。7.5参数传递机制（续）machunyan西北工业大学软件与微电子学院62名字传递实小结machunyan西北工业大学软件与微电子学院63什么是活动记录？请给出C语言活动记录的内容。设有c语言程序:main(){ printf(“%d\n”,f(3));}f(intx){ if(x==1) return1; else returnx*f(x-1);}

试给出运行该程序在返回主函数之前运行栈的活动记录示意图。小结machunyan西北工业大学软件与微电子学院63什么是演讲完毕，谢谢观看！演讲完毕，谢谢观看！machunyan西北工业大学软件与微电子学院65第7章运行时环境(存储空间)当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息例如为源程序中出现的一些量（常量、变量及某些数组等）分配运行时的存储空间。目标代码要从操作系统得到一块存储区，用于它的运行。machunyan西北工业大学软件与微电子学院1第7章运行machunyan西北工业大学软件与微电子学院66存储分配是在运行阶段进行的，但编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。(举例说明：函数调用分析.txt)目标代码运行时，存储空间的组织称为目标代码的运行时环境。第7章运行时环境(存储空间)(续)machunyan西北工业大学软件与微电子学院2存储分配是在machunyan西北工业大学软件与微电子学院67运行时环境有三个类型：完全静态环境(fullystaticenvironment)、基于栈的环境(stack-basedenvironment)，以及完全动态环境(fullydynamicenvironment)。这3种类型的混合形式也是可能的。第7章运行时环境(存储空间)(续)machunyan西北工业大学软件与微电子学院3运行时环境有machunyan西北工业大学软件与微电子学院68

7.1程序执行时的存储器组织7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制7.2完全静态的运行时环境第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院47.1machunyan西北工业大学软件与微电子学院697.1程序执行时的存储器组织目标代码运行时,操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分:由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。machunyan西北工业大学软件与微电子学院57.1程序执machunyan西北工业大学软件与微电子学院707.1程序执行时的存储器组织（续）代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，在编译时所有目标代码的地址都是可计算的，程序执行结束后代码区域内存由系统释放。全程/静态区域：静态数据区用来存放那些具有绝对地址的数据和变量(如静态变量和全程变量)；编译器可以确定其所占用存储空间的大小，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，程序执行结束后由系统释放。本章案例分析.docmachunyan西北工业大学软件与微电子学院67.1程序执7.1程序执行时的存储器组织（续）栈区：函数中的形参和在函数中定义的局部变量以及局部临时变量（C、C++、Java），这些变量分配在栈区，每次函数执行的时候会在栈中为函数的执行分配相应的存储区，而在函数执行完毕后，释放相应的存储区。编译器“知道”存在栈中的具体数据所占内存大小和内存分配和释放的“时刻”；machunyan西北工业大学软件与微电子学院717.1程序执行时的存储器组织（续）栈区：函数中的形参和在函数堆区：供用户动态申请存储空间，编译器“不需要”知道究竟得从heap中分配多少空间，也不需要知道从heap上分配的空间究竟需要存在多久。在c中由malloc，free运算产生释放的存储空间，在c++中由new和delete运算符作用的存储空间，以及在Java中由new分配的存储空间都在堆中进行分配。machunyan西北工业大学软件与微电子学院727.1程序执行时的存储器组织（续）堆区：供用户动态申请存储空间，编译器“不需要”知道究竟得从hmachunyan西北工业大学软件与微电子学院73machunyan西北工业大学软件与微电子学院9machunyan西北工业大学软件与微电子学院74machunyan西北工业大学软件与微电子学院10machunyan西北工业大学软件与微电子学院757.1程序执行时的存储器组织（续）在C语言中,采用以函数（或过程）为单位的动态存储分配方案：当一函数被调用时，就在栈顶为该函数分配所需的数据空间(过程活动记录)，当一个函数工作完毕返回时，它在栈顶的数据空间(过程活动记录)也即释放。过程的活动记录(activationrecord,AR)是一段连续的存储区，用于存放函数的一次执行所需要的信息，当调用或激活函数时，必须为被调用函数的活动记录分配空间。machunyan西北工业大学软件与微电子学院117.1程序活动记录存放的信息至少应包括以下几个部分：machunyan西北工业大学软件与微电子学院76存放主调函数为被调函数提供的实参信息;存放目标程序临时变量的值;存放本次执行中的局部数据用于指向主调函数的活动记录的控制链和返回地址;7.1程序执行时的存储器组织（续）活动记录存放的信息至少应包括以下几个部分：machunyanmachunyan西北工业大学软件与微电子学院777.1程序执行时的存储器组织（续）实参返回地址控制链临时变量和局部数据实参返回地址控制链临时变量和局部数据调用者的活动记录被调用者的活动记录调用者的职责machunyan西北工业大学软件与微电子学院137.1程序C语言所调用函数的活动记录示例(函数调用分析中的举例)控制链：指向调用函数活动记录的一个地址。machunyan西北工业大学软件与微电子学院78b:2a:1该函数调用结束时的返回地址(00401014)主调函数的控制链c:3栈底栈顶7.1程序执行时的存储器组织（续）当前函数的控制链C语言所调用函数的活动记录示例(函数调用分析中的举例)macmachunyan西北工业大学软件与微电子学院797.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院157.1程machunyan西北工业大学软件与微电子学院807.2完全静态的运行时环境在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的条件是：每个数据名所需的存储空间的大小都是常量不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构过程不可递归调用machunyan西北工业大学软件与微电子学院167.2完machunyan西北工业大学软件与微电子学院81整个程序存储器如右所示：7.2完全静态的运行时环境（续）machunyan西北工业大学软件与微电子学院17整个程序7machunyan西北工业大学软件与微电子学院827.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院187.1程machunyan西北工业大学软件与微电子学院837.3基于栈的运行时环境在一个所有函数都是全局的、函数定义不允许嵌套，但允许函数递归调用的程序设计语言(例如C语言)中，基于栈的动态运行时环境有两个指针：sp:栈顶部(topofstack)指针；对于x86系统来说，它采用sp或esp寄存器存储栈顶部的地址；注：用它只可访问栈顶machunyan西北工业大学软件与微电子学院197.3基machunyan西北工业大学软件与微电子学院847.3基于栈的运行时环境（续）fp(framepoint)：控制链指针，即存储当前活动记录的控制链（即一个地址），对于x86系统，它采用bp或ebp寄存器存储当前活动记录的控制链，其作用如下：1.通过该指针可以访问主调函数的活动记录；即允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。2.通过该指针可以访问当前执行函数的实参和局部变量；machunyan西北工业大学软件与微电子学院207.3基machunyan西北工业大学软件与微电子学院85b:2a:1该函数调用结束时的返回地址(cs:eip)00401014主调函数的控制链(main.ebp)void__stdcallf_stdcall(inta,intb){ intc; c=a+b;}c:3esp栈底栈顶ebp7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院21b:2该函machunyan西北工业大学软件与微电子学院86当一个函数被调用时，在栈顶为该函数分配所需的数据空间(过程活动记录)如下：将实参的值压入在该函数对应的新活动记录中。将被调函数执行完毕后的返回地址压入在新的活动记录中。完成到被调用的过程代码一个转移。将主调函数的fp作为控制链压入到新的活动记录中。改变fp以使其指向新的活动记录(将sp复制到fp中)将该函数的局部变量和局部临时变量压入到新的活动记录中。7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院22当一个函数machunyan西北工业大学软件与微电子学院87b:2a:1该函数调用结束时的返回地址(cs:eip)00401014主调函数的控制链(main.fp)C语言当前执行函数的活动记录示例：c:3sp栈底栈顶fp7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院23b:2该函machunyan西北工业大学软件与微电子学院88当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：①将fp复制到sp中。②将控制链装载到fp中。③完成到返回地址主调函数的一个转移。④改变sp以弹出实参。7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院24当被调函数machunyan西北工业大学软件与微电子学院89例：计算两个非负整数最大公约数的c代码如下：#include<studio.h>intx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v)}main(){scanf(“%d%d”,&x,&y);printf(“%d\n”,gcd(x,y));return0;}7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院25例：计算两machunyan西北工业大学软件与微电子学院90x:15y:10全局/静态区域main的活动记录sp,fpv:10u:15返回地址main的fp第一次调用gcd时的活动记录sp,fp第二次调用gcd时的活动记录v:5u:10返回地址第一次调用gcd时的fp第三次调用gcd时的活动记录v:0u:5返回地址第二次调用gcd时的fpsp,fpsp,fp栈生长方向自由空间7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院26x:15全machunyan西北工业大学软件与微电子学院91例：考虑下列程序清单的c代码。intx=2;voidg(int);voidf(intn){staticintx=1;g(n);x--;}voidg(intm){inty=m-1;if(y>0){f(y);x--;g(y);}}main(){g(x);return0;}画出至第二次对g调用时，程序的运行时环境：7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院27例：考虑下machunyan西北工业大学软件与微电子学院92x:2x（fromf）:1全局/静态区域main的活动记录sp,fpm:2返回地址main的fpy:1第一次调用g时的活动记录fpsp第一次调用f时的活动记录n:1

返回地址第一次调用g时的fpsp,fp第二次调用g时的活动记录m:1返回地址第一次调用f时的fpy:0fpsp栈生长方向自由空间7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院28x:2全局machunyan西北工业大学软件与微电子学院93目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院29目标代码的machunyan西北工业大学软件与微电子学院94对名字的访问：在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。对函数参数和局部变量而言，在大多数的语言中，如果函数的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定，每个实参和局部声明的偏移量可由编译程序计算。machunyan西北工业大学软件与微电子学院30对名字的访machunyan西北工业大学软件与微电子学院95m:2返回地址控制链

y:1fpmOffsetyOffsetmOffset=+8yOffset=-4高端地址低端地址对名字的访问：（续）machunyan西北工业大学软件与微电子学院31m:2machunyan西北工业大学软件与微电子学院96例：考虑下面的C过程Viodf(intx,charc){inta[10];doubley;

……}cx

返回地址控制链a[9]…a[1]a[0]yfpcOffsetaOffsetxOffsetyOffsetxOffset=+8cOffset=+12aOffset=-40yOffset=-48现在对a[i]访问，要求计算地址：(-40+4*i)(fp)对名字的访问：（续）对f调用的活动记录为：machunyan西北工业大学软件与微电子学院32例：考虑下machunyan西北工业大学软件与微电子学院97目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院33目标代码的machunyan西北工业大学软件与微电子学院98局部临时变量：考虑C表达式：x[i]=(i+j)*(i/k+f(j))，在这个表达式从左到右的求值计算中，在对f的调用过程中需要保存中间结果：x[i]的地址、i+j的和、i/k的商。这些中间值可计算到寄存器中，根据寄存器进行保存和恢复；或者可将它们作为临时变量存储在对f调用之前的运行时栈中。如下所示：machunyan西北工业大学软件与微电子学院34局部临时变machunyan西北工业大学软件与微电子学院99…

返回地址控制链…x[i]的地址i+j的结果i/j的结果fp(栈的其余部分)sp临时栈调用f（将要创建的）时的新活动记录包含表达式过程的活动记录自由空间局部临时变量：（续）machunyan西北工业大学软件与微电子学院35fp(栈的machunyan西北工业大学软件与微电子学院100目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院36目标代码的machunyan西北工业大学软件与微电子学院101嵌套声明也出现了与局部临时变量同样的问题。考虑以下的C代码：Voidp(intx,doubley){chara;inti;…A:{doublex;intj;…}…B:{char*a;intk;…}…}嵌套声明：machunyan西北工业大学软件与微电子学院37嵌套声明也machunyan西北工业大学软件与微电子学院102x:y:

返回地址控制链a:i:x:j:fp(栈的其余部分)sp块A的分配区调用p时的活动记录自由空间嵌套声明：（续）一个简单的处理办法是按照与临时表达式相类似的办法在嵌套的块中处理声明，并在进入块时在栈中分配它们。当进入块A后，运行时栈如下所示：machunyan西北工业大学软件与微电子学院38x:fp(machunyan西北工业大学软件与微电子学院103x:y:

返回地址控制链a:i:a:k:fp(栈的其余部分)sp块B的分配区调用p时的活动记录自由空间当进入块B后，运行时栈如下所示：嵌套声明：（续）machunyan西北工业大学软件与微电子学院39x:fp(machunyan西北工业大学软件与微电子学院104目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）machunyan西北工业大学软件与微电子学院40目标代码的machunyan西北工业大学软件与微电子学院105处理可变长度的数据有时编译程序必须处理数据变化的可能性，表现在数据对象的数量和每个对象的大小上。发生在支持基于栈的环境的语言中的一种情况如下：①调用中的自变量的数量可根据调用的不同而不同。printf(“%d%s",n,prompt);printf(“%d%d%d”,3,4,50);通常，C编译程序一般通过把调用的自变量按相反顺序(inreverseorder)压入到运行时栈来处理这一点。machunyan西北工业大学软件与微电子学院41处理可变长machunyan西北工业大学软件与微电子学院106printf(“%d%d%d”,3,4,50);设置一指针ap；让ap指向第一个可变参数(地址为ebp+控制链所占的空间+返回地址所占的空间+固定参数所占的空间)，即3所在的空间；返回3，ap的值加4即指向4所在的存储空间……,通过指针ap的移动读取所有的可变参数，根据固定参数“%d%d%d”，该字符串中每出现一个“%d”就执行一次；固定参数指出了后面的可变参数的个数；清除变量ap。处理可变长度的数据(续)machunyan西北工业大学软件与微电子学院42printmachunyan西北工业大学软件与微电子学院1077.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)machunyan西北工业大学软件与微电子学院437.1程machunyan西北工业大学软件与微电子学院1087.4.1对象类型在大多数面向对象的语言中，对象都有构造函数和析构函数，它们分别在创建对象和释放对象时被调用。假定我们有一对象类A，它有方法m1,m2以及字段a1和a2。那么类A对象的运行时表示有包含字段a1和a2记录组成：a1a2m1_Am2_A另外，编译程序维护着一张类A的编译时方法表：7.4动态存储器machunyan西北工业大学软件与微电子学院447.4.1在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法选择由编译程序内的识别过程来实现。即通过一个指向对象的指针，方法可以像函数一样实现。因此方法m2_A可以翻译为c语言中的函数。

voidm2_A(class_A*this,inti){

方法m2_A的程序体，通过this->x访问任一对

象字段x}方法的调用a.m2(3)可以翻译成m2_A(&a,3)machunyan西北工业大学软件与微电子学院1097.4动态存储器（续）在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法machunyan西北工业大学软件与微电子学院110继承特性现在假定类B通过增添方法m3和字段b1来扩展类A,那么类B的运行时表示如下：a1a2m1_Am2_Ab1另外类B的方法编译时表如下：m3_B7.4动态存储器（续）machunyan西北工业大学软件与微电子学院46继承特性现machunyan西北工业大学软件与微电子学院111方法重载假定上例中类B重新定义了方法m2，那么A中方法m2的定义既是它唯一的声明也是它的第一次定义，而它在类B中的定义为重定义。为使名字既可以反映声明它的类，也可以反映定义它的类。方法的名字可有三部分组成：方法名、声明方法的类名、定义方法类名。各部分之间用下划线（—）分开。因此在类A中声明在类B中定义的方法m2其名字记为m2_A_B。方法重载影响方法的编译时表，现在类A的方法的编译时表如下：m1_A_Am2_A_Am1_A_Am2_A_Bm3_B_B类B的方法的编译时表如右：7.4动态存储器（续）machunyan西北工业大学软件与微电子学院47方法重载假现在假定a是类A的一个对象，而b是类B的一个对象方法调用a.m2(…)将翻译成对m2_A_A的调用，而方法调用b.m2(…)将翻译成对m2_A_B的调用。2_A_A在类A中声明和定义。m2_A_B在类A中生明，在类B中定义。m2_A_A翻译形式为：voidm2_A_A(Class_A*this,inti);m2_A_B的翻译形式为：voidm2_A_B(Class_B*this,inti);machunyan西北工业大学软件与微电子学院1127.4动态存储器（续）现在假定a是类A的一个对象，而b是类B的一个对象machunmachunyan西北工业大学软件与微电子学院113多态性当类B继承类A，并且该语言允许“类B的指针”类型的指针能够赋给一个“类A的指针”类型的变量时，那么该语言支持多态型。例如：ClassB*b=…;ClassA*a=b;则第二行被翻译成：classA*a=convert_ptr_to_B_to_ptr_to_A(b);现在，过程convert_ptr_to_B_to_ptr_to_A()为一编译时类型的操作,它将指向子类B的一个对象指针转换为指向其父类A对象的指针。因为类B的对象也是从类A的字段开始，因而指针的值并不需要改变，唯一影响的是改变了指针的类型：7.4动态存储器（续）machunyan西北工业大学软件与微电子学院49多态性当类machunyan西北工业大学软件与微电子学院114a1a2b1指向B的指针指向B中A的指针现在同一指针指向了不同类的对象7.4动态存储器（续）machunyan西北工业大学软件与微电子学院50a1a2bmachunyan西北工业大学软件与微电子学院1157.4动态存储器（续）动态绑定：类型classA*的指针p可能引用了类B的一个对象，动态绑定认为如果实际上为类B的对象，那就应该调用m2_A_B,如果实际为A的对象，那么就应该调用m2_A_A.对于方法调用p->m2(3)p是一指向类A对象指针，可以将p->m2(3)被翻译成如下形式：switch(dynamic_type_of(p)){caseDynamic_class_A:m2_A_A(p,3);caseDynamic_class_B:m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);}当p为一指向类B对象指针时，可以将p->m2(3)翻译为：m2_A_B(p,3);machunyan西北工业大学软件与微电子学院517.4动machunyan西北工业大学软件与微电子学院116对于上述的翻译方法，每一个对象的类型信息实现为一个指向分派表的指针，如下图所示(分派表是存储方法地址的记录，下图分派表存储的是方法m1_A_A，m2_A_B和m1_B_B的地址)a1a2b1指向B的指针指向B中A的指针m1_A_Am2_A_Bm3_B_B类B对象的表示分派表B-objectB-class7.4动态存储器（续）machunyan西北工业大学软件与微电子学院52对于上述的machunyan西北工业大学软件与微电子学院1177.4.2堆管理7.4动态存储器（续）对于允许程序为变量在运行时动态申请和释放存储空间的语言,采用堆式分配是最有效的解决方案.堆式分配的基本思想是,为运行的程序划出适当大的空间(称为堆Heap),每当程序申请空间时,就从堆的空闲区找出一块空间分配给程序,每当释放时则回收之.machunyan西北工业大学软件与微电子学院537.4.2machunyan西北工业大学软件与微电子学院118堆分配的必要性7.4动态存储器（续）在C中处理链表等结构时,常常随机地插入或删除一些结点,利用指针变量和结构类型,可动态地生成新结点(使用malloc()函数),或删除之(使用f