编译原理课程设计之运行时环境

会计学1编译原理课程设计之运行时环境mcy2第7章运行时环境(存储空间)当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息，如必须为源程序中所出现的一些量（常量、变量及某些数组等）分配运行时的存储空间。即编译器要从操作系统得到一块存储区，用于被编译过的目标程序的运行。第1页/共62页mcy3存储分配是在运行阶段进行的，但编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。(举例说明：函数调用分析.txt)目标代码运行时，存储空间的组织称为目标代码的运行时环境。第2页/共62页mcy4运行时环境有三个类型：完全静态环境(fullystaticenvironment)、基于栈的环境(stack-basedenvironment)，以及完全动态环境(fullydynamicenvironment)。这3种类型的混合形式也是可能的。第3页/共62页mcy57.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第4页/共62页mcy67.1程序执行时的存储器组织目标代码运行时,操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分:第5页/共62页mcy7代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，所以在编译时所有目标代码的地址都是可计算的；全程/静态区域：静态数据区用来存放那些具有绝对地址的数据和变量(如静态变量和全程变量)；编译器可以确定其所占用存储空间的大小；栈区：在运行时分配存储空间的数据就分配在栈区；编译器知道存在栈中的具体数据大小和存活时间；堆区：供用户动态申请存储空间，编译器不需要知道究竟得从heap中分配多少空间，也不需要知道从heap上分配的空间究竟需要存在多久。由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。第6页/共62页mcy8在PASCAL，C语言中,通常采用以过程为单位的动态存储分配方案：当一过程(函数)被调用时，就在栈顶为该过程分配所需的数据空间(过程活动记录)，当一个过程工作完毕返回时，它在栈顶的数据空间(过程活动记录)也即释放。过程的活动记录(activationrecord,AR)是一段连续的存储区，用于存放过程的一次执行所需要的信息，当调用或激活过程或函数时，必须为被调用过程的活动记录分配空间。活动记录存放的信息至少应包括以下几个部分：第7页/共62页mcy9存放主调过程为被调过程提供的实参信息;存放目标程序临时变量的值;存放本次执行中的局部数据用于指向主调过程的活动记录的控制链和返回地址;第8页/共62页mcy10b:2a:1该函数调用结束时的返回地址(00401353)主调函数的控制链C语言所调用函数的活动记录示例(函数调用分析中的举例)c:3栈底栈顶第9页/共62页mcy11第7章运行时环境7.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第10页/共62页mcy127.2完全静态的运行时环境在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的条件是：每个数据名所需的存储空间的大小都是常量不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构过程不可递归调用第11页/共62页mcy13整个程序存储器如下所示：第12页/共62页mcy14程序所需的数据空间在程序运行前就可确定，称为_______管理技术。静态存储动态存储栈式存储堆式存储第13页/共62页mcy15静态存储分配允许程序出现_______。递归过程可变体积的数据项目静态变量待定性质的名字第14页/共62页mcy16第7章运行时环境7.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第15页/共62页mcy177.3基于栈的运行时环境7.3.1没有局部过程的基于栈的环境在一个所有过程都是全局的、过程定义不允许嵌套，但允许过程的递归调用的程序设计语言(例如C语言)中，基于栈的动态运行时环境有两个指针：sp:栈顶部(topofstack)指针；对于x86系统来说，它采用sp或esp寄存器存储栈顶部的地址；第16页/共62页mcy18fp(framepoint)指向当前活动记录的控制链的指针，对于x86系统，它采用bp或ebp寄存器存储当前活动记录的控制链的地址，其作用如下：1.通过该指针可以访问当前执行函数的局部变量；2.通过该指针可以访问主调程序的活动记录；3.允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。第17页/共62页mcy19b:2a:1该函数调用结束时的返回地址(cs:eip)00401353主调函数的控制链(main.fp)C语言当前执行函数的活动记录示例(函数调用分析中的举例)c:3spfp栈底栈顶第18页/共62页mcy20当一个过程被调用时，在栈顶为该过程分配所需的数据空间(过程活动记录)如下：将实参的值压入在该函数对应的新活动记录中。将被调函数执行完毕后的返回地址压入在新的活动记录中。完成到被调用的过程的代码一个转移。将主调函数的fp作为控制链压入到新的活动记录中。改变fp以使其指向新的活动记录(将sp复制到该fp中)将该函数的局部变量和局部临时变量压入到新的活动记录中。第19页/共62页mcy21b:2a:1该函数调用结束时的返回地址(cs:eip)00401353主调函数的控制链(main.fp)C语言当前执行函数的活动记录示例：c:3sp栈底栈顶fp第20页/共62页mcy22当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：①将fp复制到sp中。②将控制链装载到fp中。③完成到返回地址主调函数的一个转移。④改变sp以弹出实参。第21页/共62页mcy23例：计算两个非负整数的最大公约数的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;}第22页/共62页mcy24x: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栈生长方向自由空间第23页/共62页mcy25例：考虑下列程序清单的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调用时，程序的运行时环境：第24页/共62页mcy26x:2x（fromf）:1全局/静态区域main的活动记录sp,fpm:2返回地址main的fpy:1第一次调用g时的活动记录fpsp第一次调用f时的活动记录n:1

返回地址第一次调用g时的fpsp,fp第二次调用g时的活动记录m:1返回地址第一次调用f时的fpy:0fpsp栈生长方向自由空间第25页/共62页mcy27目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明第26页/共62页mcy28对名字的访问：在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。对函数参数和局部变量而言，在大多数的语言中，每个局部声明的偏移量仍是可有编译程序静态地计算出来，因为过程的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定。第27页/共62页mcy29m:2返回地址控制链

y:1fpmOffsetyOffsetmOffset=+8yOffset=-4高端地址低端地址第28页/共62页mcy30例：考虑下面的C过程Viodf(intx,charc){inta[10];doubley;

……}对f调用的活动记录为：cx

返回地址控制链a[9]…a[1]a[0]yfpxOffsetaOffsetcOffsetyOffsetxOffset=+8cOffset=+12aOffset=-40yOffset=-48现在对a[i]访问，要求计算地址：(-40+4*i)(fp)第29页/共62页mcy31目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明第30页/共62页mcy32处理可变长度的数据有时编译程序必须处理数据变化的可能性，表现在数据对象的数量和每个对象的大小上。发生在支持基于栈的环境的语言中的两种情况如下：①调用中的自变量的数量可根据调用的不同而不同。②数组参数或局部数组变量的大小可根据调用的不同而不同。printf("%d%s%c",n,prompt,ch);printf("Hello,world\n");通常，C编译程序一般通过把调用的自变量按相反顺序(inreverseorder)压入到运行时栈来处理这一点。第31页/共62页mcy33目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明第32页/共62页mcy34局部临时变量：考虑C表达式：x[i]=(i+j)*(i/k+f(j))在这个表达式从左到右的求值计算中，在对f的调用过程中需要保存中间结果：x[i]的地址、i+j的和、i/k的商。这些中间值可计算到寄存器中，根据寄存器进行保存和恢复；或者可将它们作为临时变量存储在对f调用之前的运行时栈中。如下所示：第33页/共62页mcy35…

返回地址控制链…x[i]的地址i+j的结果i/j的结果fp(栈的其余部分)sp临时栈调用f（将要创建的）时的新活动记录包含表达式过程的活动记录自由空间第34页/共62页mcy36目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明第35页/共62页mcy37嵌套声明：嵌套声明也出现了与局部临时变量同样的问题。考虑以下的C代码：Voidp(intx,doubley){chara;inti;

…A:{doublex;intj;

…}

…B:{char*a;intk;

…}

…}第36页/共62页mcy38一个简单的处理办法是按照与临时表达式相类似的办法在嵌套的块中处理声明，并在进入块时在栈中分配它们。x:y:

返回地址控制链a:i:x:j:fp(栈的其余部分)sp块A的分配区调用p时的活动记录自由空间当进入块A后，运行时栈如下所示：第37页/共62页mcy39x:y:

返回地址控制链a:i:a:k:fp(栈的其余部分)sp块B的分配区调用p时的活动记录自由空间当进入块B后，运行时栈如下所示：第38页/共62页mcy40第7章运行时环境7.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第39页/共62页mcy417.4.1对象类型在大多数面向对象的语言中，对象都有构造函数和析构函数，它们分别在创建对象和释放对象时被调用。如果这就是全部内容的话，那么对象的实现将非常简单。假定我们有一对象类A，它有方法m1,m2以及字段a1和a2。那么类A对象的运行时表示有包含字段a1和a2记录组成：a1a2m1_Am2_A另外，编译程序维护着一张类A的编译时方法表：7.4动态存储器第40页/共62页mcy42在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法选择由编译程序内的识别过程来实现。即通过一个指向对象的指针，方法可以像函数一样实现。因此方法m2_A可以翻译为c语言中的函数。

voidm2_A(class_A*this,inti){

方法m2_A的程序体，通过this->x访问任一对象字段x}方法的调用a.m2(3)可以翻译成m2_A(&a,3)第41页/共62页mcy43继承特性现在假定类B通过增添方法m3和字段b1来扩展类A,那么类B的运行时表示如下：a1a2m1_Am2_Ab1另外类B的方法编译时表如下：m3_B第42页/共62页mcy44方法重载假定上例中类B重新定义了方法m2，那么A中方法m2的定义既是它唯一的声明也是它的第一次定义，而它在类B中的定义为重定义。为使名字既可以反映声明它的类，也可以反映定义它的类。方法的名字可有三部分组成：方法名、声明方法的类名、定义方法类名。各部分之间用下划线（—）分开。因此在类A中声明在类B中定义的方法m2其名字记为m2_A_B。方法重载影响方法的编译时表，现在类A的方法的编译时表如下：m1_A_Am2_A_Am1_A_Am2_A_Bm3_B_B类B的方法的编译时表如右：第43页/共62页mcy45现在假定a是类A的一个对象，而b是类B的一个对象。方法调用a.m2(…)将翻译成对m2_A_A的调用，而方法调用b.m2(…)将翻译成对m2_A_B的调用。m2_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);第44页/共62页mcy46多态性当类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的字段开始，因而指针的值并不需要改变，唯一影响的是改变了指针的类型：第45页/共62页mcy47a1a2b1指向B的指针指向B中A的指针但要注意，现在同一指针指向了不同类的对象第46页/共62页mcy48动态绑定：因为类型classA*的指针p可能实际上引用了类B的一个对象，动态绑定认为如果实际上为类B的对象，那就应该调用m2_A_B,如果实际为A的对象，那么就应该调用m2_A_A.对于方法调用P->m2(3),p是一指向类A对象指针，可以被翻译成如下形式：switch(dynamic_type_of(p)){caseDynamic_class_A:m2_A_A(p,3);break;caseDynamic_class_B:m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);break;}当p为一指向类B对象指针时，可以立即将p->m2(3)调用翻译为：m2_A_B(p,3);第47页/共62页mcy49动态绑定对于方法P->m2(3)的更好翻译方法为：如果p是一指向类A对象指针，则进行如下处理有：(dynamic_type_of(p)==Dynamic_Class_A?m2_A_A:m2_A_B)(p,3);如果指针p实际上引用了类B的一个对象，则执行步骤2中的方法。voidm2_A_B(Class_A*this_A,inti){Class_B*this=convert_ptr_to_A_to_ptr_to_B(this_A);方法m2_A_B的程序体，通过this->x访问任一对象字段x}如果p是一指向类B对象指针，则进行如下处理有：m2_A_B(convert_ptr_to_B_to_ptr_to_A(p),3);执行的方法同上述的步骤2；第48页/共62页mcy50对于上述的翻译方法，每一个对象的类型信息实现为一个指向分派表的指针，如下图所示(分派表是存储方法地址的记录，下图分派表存储的是方法m1_A_A，m2_A_B和m1_B_B的地址)a1a2b1指向B的指针指向B中A的指针m1_A_Am2_A_Bm3_B_B类B对象的表示分派表B-objectB-class第49页/共62页mcy517.4.2堆管理对于允许程序为变量在运行时动态申请和释放存储空间的语言,采用堆式分配是最有效的解决方案.堆式分配的基本思想是,为运行的程序划出适当大的空间(称为堆Heap),每当程序申请空间时,就从堆的空闲区找出一块空间分配给程序,每当释放时则回收之.第50页/共62页mcy52在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);}}堆分配的必要性第51页/共62页mcy53将存储空间划分为若干存储块;用户可随机地申请或释放一个或多个块;在存储空间中建立两个队列:空闲队列和忙队列,空闲队列拉成链,链首用FREE指针指明,忙队列用一(已占块)记录表记录各占用块的首址及大小信息(也可用链进行记录).申请时可按需要找到合适的块分配之(分配策略有最佳分配或随机分配等);释放时将该块插入到空闲队列(能合并时可合并),并从占用记录表中删除相应的项.堆存储管理的实现第52页/共62页mcy54第7章运行时环境7.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第53页/共62页mcy557.5参数传递机制值传递值传递的处理方法是：进入过程时,送入形参对应的形式单元的是相应实参的值;过程体中对形参的任何赋值都按对形式单元的直接访问来产生代码。因此,一旦把实参之值送入对应形式单元之后,在执行过程体期间,除了以实参值作为形参的初值进行运算之外,将不再与实参发生任何联系。由此可见,过程执行的结果决不会改变实参之值。voidinc2(intx)/*incorrect!*/{++x;++x;}voidinc2(int*x)/*nowok*/{++(*x);++(*x);}第54页/共62页mcy56引用传递控制转入被调过程后,由被调过程将实参的地址写入相应的形式单元。过程体中对形式参数的任何引用或赋值,都按对相应形式单元间接访问的寻址方式为其产生代码。显然,执行过程时,型参就变成了实参的别名，对形参的赋值将会影响相应实参之值。在C++中，是通过在参数说明中使用特殊字符&来得到引用传递：voidinc2(int&x)/*C++referenceparameter*/{++x;++x;}第55页/共62页mcy57引用传递不要求复制被传递的值，这与值传递不同。当要复制的值是一个较大的结构时，如果禁止自变量的值有任何变化，在这种情况下，引用传递能够做到值传递而无需覆盖值的拷贝。在C++中可将调用写作：voidf(constMuchData&x)其中的MuchData是带有大型结构的数据类型。这仍是引用传递，但是编译程序还必须执行一个静态检查：x从不出现在一个赋值的左边或是被改变。第56页/共62页mcy58已知C程序：#include<