编译原理课程设计之第七节-运行时环境PPT课件

mcy,.,1,课程内容第一章概论第二章词法分析第三章上下文无关文法及分析第四章自上而下的语法分析第五章自下而上的语法分析第六章语义分析第七章运行时环境第八章代码生成,mcy,.,2,第7章运行时环境(存储空间),当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息，如必须为源程序中所出现的一些量（常量、变量及某些数组等）分配运行时的存储空间。即编译器要从操作系统得到一块存储区，用于被编译过的目标程序的运行。,mcy,.,3,存储分配是在运行阶段进行的，但编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。(举例说明：函数调用分析.txt)目标代码运行时，存储空间的组织称为目标代码的运行时环境。,mcy,.,4,运行时环境有三个类型：完全静态环境(fullystaticenvironment)、基于栈的环境(stack-basedenvironment)，以及完全动态环境(fullydynamicenvironment)。这3种类型的混合形式也是可能的。,mcy,.,5,7.1程序执行时的存储器组织,7.2完全静态的运行时环境,7.3基于栈的运行时环境,7.4动态存储器,7.5参数存储机制,mcy,.,6,7.1程序执行时的存储器组织,目标代码运行时,操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分:,mcy,.,7,代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，所以在编译时所有目标代码的地址都是可计算的；全程/静态区域：静态数据区用来存放那些具有绝对地址的数据和变量(如静态变量和全程变量)；编译器可以确定其所占用存储空间的大小；栈区：在运行时分配存储空间的数据就分配在栈区；编译器知道存在栈中的具体数据大小和存活时间；堆区：供用户动态申请存储空间，编译器不需要知道究竟得从heap中分配多少空间，也不需要知道从heap上分配的空间究竟需要存在多久。由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。,mcy,.,8,在PASCAL，C语言中,通常采用以过程为单位的动态存储分配方案：当一过程(函数)被调用时，就在栈顶为该过程分配所需的数据空间(过程活动记录)，当一个过程工作完毕返回时，它在栈顶的数据空间(过程活动记录)也即释放。过程的活动记录(activationrecord,AR)是一段连续的存储区，用于存放过程的一次执行所需要的信息，当调用或激活过程或函数时，必须为被调用过程的活动记录分配空间。活动记录存放的信息至少应包括以下几个部分：,mcy,.,9,存放主调过程为被调过程提供的实参信息;,存放目标程序临时变量的值;,存放本次执行中的局部数据,用于指向主调过程的活动记录的控制链和返回地址;,mcy,.,10,b:2a:1,该函数调用结束时的返回地址(00401353),主调函数的控制链,C语言所调用函数的活动记录示例(函数调用分析中的举例),c:3,栈底,栈顶,mcy,.,11,第7章运行时环境,7.1程序执行时的存储器组织,7.2完全静态的运行时环境,7.3基于栈的运行时环境,7.4动态存储器,7.5参数存储机制,mcy,.,12,7.2完全静态的运行时环境,在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的条件是：每个数据名所需的存储空间的大小都是常量不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构过程不可递归调用,mcy,.,13,整个程序存储器如下所示：,mcy,.,14,程序所需的数据空间在程序运行前就可确定，称为_管理技术。静态存储动态存储栈式存储堆式存储,mcy,.,15,静态存储分配允许程序出现_。递归过程可变体积的数据项目静态变量待定性质的名字,mcy,.,16,第7章运行时环境,7.1程序执行时的存储器组织,7.2完全静态的运行时环境,7.3基于栈的运行时环境,7.4动态存储器,7.5参数存储机制,mcy,.,17,7.3基于栈的运行时环境,7.3.1没有局部过程的基于栈的环境,在一个所有过程都是全局的、过程定义不允许嵌套，但允许过程的递归调用的程序设计语言(例如C语言)中，基于栈的动态运行时环境有两个指针：sp:栈顶部(topofstack)指针；对于x86系统来说，它采用sp或esp寄存器存储栈顶部的地址；,mcy,.,18,fp(framepoint)指向当前活动记录的控制链的指针，对于x86系统，它采用bp或ebp寄存器存储当前活动记录的控制链的地址，其作用如下：1.通过该指针可以访问当前执行函数的局部变量；2.通过该指针可以访问主调程序的活动记录；3.允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。,mcy,.,19,b:2a:1,该函数调用结束时的返回地址(cs:eip)00401353,主调函数的控制链(main.fp),C语言当前执行函数的活动记录示例(函数调用分析中的举例),c:3,sp,fp,栈底,栈顶,mcy,.,20,当一个过程被调用时，在栈顶为该过程分配所需的数据空间(过程活动记录)如下：,将实参的值压入在该函数对应的新活动记录中。将被调函数执行完毕后的返回地址压入在新的活动记录中。完成到被调用的过程的代码一个转移。将主调函数的fp作为控制链压入到新的活动记录中。改变fp以使其指向新的活动记录(将sp复制到该fp中)将该函数的局部变量和局部临时变量压入到新的活动记录中。,mcy,.,21,b:2a:1,C语言当前执行函数的活动记录示例：,mcy,.,22,当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：将fp复制到sp中。将控制链装载到fp中。完成到返回地址主调函数的一个转移。改变sp以弹出实参。,mcy,.,23,例：计算两个非负整数的最大公约数的c代码如下：,#includeintx,y;intgcd(intu,intv)if(v=0)returnu;elsereturngcd(v,u%v)main()scanf(“%d%d”,mcy,.,24,mcy,.,25,例：考虑下列程序清单的c代码。intx=2;voidg(int);voidf(intn)staticintx=1;g(n);x-;voidg(intm)inty=m-1;if(y0)f(y);x-;g(y);,main()g(x);return0;,画出第二次对g调用时，程序的运行时环境：,mcy,.,26,mcy,.,27,目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明,mcy,.,28,对名字的访问：,在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。对函数参数和局部变量而言，在大多数的语言中，每个局部声明的偏移量仍是可有编译程序静态地计算出来，因为过程的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定。,mcy,.,29,m:2返回地址控制链y:1,fp,mOffset,yOffset,mOffset=+8,yOffset=-4,高端地址,低端地址,mcy,.,30,例：考虑下面的C过程Viodf(intx,charc)inta10;doubley;对f调用的活动记录为：,cx返回地址控制链a9a1a0y,fp,xOffset,aOffset,cOffset,yOffset,xOffset=+8,cOffset=+12,aOffset=-40,yOffset=-48,现在对ai访问，要求计算地址：(-40+4*i)(fp),mcy,.,31,目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明,mcy,.,32,处理可变长度的数据,有时编译程序必须处理数据变化的可能性，表现在数据对象的数量和每个对象的大小上。发生在支持基于栈的环境的语言中的两种情况如下：调用中的自变量的数量可根据调用的不同而不同。数组参数或局部数组变量的大小可根据调用的不同而不同。,printf(%d%s%c,n,prompt,ch);,printf(Hello,worldn);,通常，C编译程序一般通过把调用的自变量按相反顺序(inreverseorder)压入到运行时栈来处理这一点。,mcy,.,33,目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明,mcy,.,34,局部临时变量：,考虑C表达式：xi=(i+j)*(i/k+f(j)在这个表达式从左到右的求值计算中，在对f的调用过程中需要保存中间结果：xi的地址、i+j的和、i/k的商。这些中间值可计算到寄存器中，根据寄存器进行保存和恢复；或者可将它们作为临时变量存储在对f调用之前的运行时栈中。如下所示：,mcy,.,35,返回地址控制链xi的地址i+j的结果i/j的结果,fp,(栈的其余部分),sp,临时栈,调用f（将要创建的）时的新活动记录,包含表达式过程的活动记录,自由空间,mcy,.,36,目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问如何处理可变长度的问题局部临时变量嵌套声明,mcy,.,37,嵌套声明：,嵌套声明也出现了与局部临时变量同样的问题。考虑以下的C代码：Voidp(intx,doubley)chara;inti;A:doublex;intj;B:char*a;intk;,mcy,.,38,一个简单的处理办法是按照与临时表达式相类似的办法在嵌套的块中处理声明，并在进入块时在栈中分配它们。,x:y:返回地址控制链a:i:x:j:,fp,(栈的其余部分),sp,块A的分配区,调用p时的活动记录,自由空间,当进入块A后，运行时栈如下所示：,mcy,.,39,x:y:返回地址控制链a:i:a:k:,fp,(栈的其余部分),sp,块B的分配区,调用p时的活动记录,自由空间,当进入块B后，运行时栈如下所示：,mcy,.,40,第7章运行时环境,7.1程序执行时的存储器组织,7.2完全静态的运行时环境,7.3基于栈的运行时环境,7.4动态存储器,7.5参数存储机制,mcy,.,41,7.4.1对象类型,在大多数面向对象的语言中，对象都有构造函数和析构函数，它们分别在创建对象和释放对象时被调用。如果这就是全部内容的话，那么对象的实现将非常简单。假定我们有一对象类A，它有方法m1,m2以及字段a1和a2。那么类A对象的运行时表示有包含字段a1和a2记录组成：,a1,a2,m1_A,m2_A,另外，编译程序维护着一张类A的编译时方法表：,7.4动态存储器,mcy,.,42,在上述简单的模块中，字段选择可以像记录字段选择一样实现，方法选择由编译程序内的识别过程来实现。即通过一个指向对象的指针，方法可以像函数一样实现。因此方法m2_A可以翻译为c语言中的函数。voidm2_A(class_A*this,inti)方法m2_A的程序体，通过this-x访问任一对象字段x方法的调用a.m2(3)可以翻译成m2_A(而m2_A_B的翻译形式为：voidm2_A_B(Class_B*this,inti);,mcy,.,46,多态性,当类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的字段开始，因而指针的值并不需要改变，唯一影响的是改变了指针的类型：,mcy,.,47,a1,a2,b1,指向B的指针,指向B中A的指针,但要注意，现在同一指针指向了不同类的对象,mcy,.,48,动态绑定：,因为类型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);,mcy,.,49,动态绑定对于方法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；,mcy,.,50,对于上述的翻译方法，每一个对象的类型信息实现为一个指向分派表的指针，如下图所示(分派表是存储方法地址的记录，下图分派表存储的是方法m1_A_A，m2_A_B和m1_B_B的地址),a1,a2,b1,指向B的指针,指向B中A的指针,m1_A_A,m2_A_B,m3_B_B,类B对象的表示,分派表,B-object,B-class,mcy,.,51,7.4.2堆管理,对于允许程序为变量在运行时动态申请和释放存储空间的语言,采用堆式分配是最有效的解决方案.堆式分配的基本思想是,为运行的程序划出适当大的空间(称为堆Heap),每当程序申请空间时,就从堆的空闲区找出一块空间分配给程序,每当释放时则回收之.,mcy,.,52,在C中处理链表等结构时,常常随机地插入或删除一些结点,利用指针变量和结构类型,可动态地生成新结点(使用malloc()函数),或删除之(使用free()函数).例如structnodechardata;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);,堆分配的必要性,mcy,.,53,将存储空间划分为若干存储块;用户可随机地申请或释放一个或多个块;在存储空间中建立两个队列:空闲队列和忙队列,空闲队列拉成链,链首用FREE指针指明,忙队列用一(已占块)记录表记录各占用块的首址及大小信息(也可用链进行记录).申请时可按需要找到合适的块分配之(分配策略有最佳分配或随机分配等);释放时将该块插入到空闲队列(能合并时可合并),并从占用记录表中删除相应的项.,堆存储管理的实现,mcy,.,54,第7章运行时环境,7.1程序执行时的存储器组织,7.2完全静态的运行时环境,7.3基于栈的运行时环境,7.4动态存储器,7.5参数存储机制,mcy,.,55,7.5参数传递机制,值传递,值传递的处理方法是：进入过程时,送入形参对应的形式单元的是相应实参的值;过程体中对形参的任何赋值都按对形式单元的直接访问来产生代码。因此,一旦把实参之值送入对应形式单元之后,在执行过程体期间,除了以实参值作为形参的初值进行运算之外,将不再与实参发生任何联系。由此可见,过程执行的结果决不会改变实参之值。,voidinc2(intx)/*incorrect!*/+x;+x;,voidinc2(int*x)/*nowok*/+(*x);+(*x);,mcy,.,56,引用传递,控制转入被调过程后,由被调过程将实参的地址写入相应的形式单元。过程体中对形式参数的任何引用或赋值,都按对相应形式单元间接访问的寻址方式为其产生代码。显然,执行过程时,型参就变成了实参的别名，对形参的赋值将会影响相应实参之值。,在C+中，是通过在参数说明中使用特殊字符,mcy,.,57,引用传递不要求复制被传递的值，这与值传递不同。当要复制的值是一个较大的结构时，如果禁止自变量的值有任何变化，在这种情况下，引用传