《编译原理课程教案》第6章：运行时存储分配.ppt

《《编译原理课程教案》第6章：运行时存储分配.ppt》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第6章：运行时存储分配.ppt（20页珍藏版）》请在三一办公上搜索。

1、运行时存储空间的组织,第六章,本章要求,主要内容：程序的静态文本与它运行时的活动之间的关系，源程序运行时各种对象的存储空间主要有三种方式分配方式：静态存储分配、栈式存储分配和堆式存储分配重点掌握：源程序运行时的活动，参数传递方式，程序中名字的作用域，局部数据区的内容，存储空间的分配方式,6.1 程序执行时的活动,静态和动态的联系名字和数据对象数据对象的动态表示名字的作用域数据对象的存储分配过程和活动参数处理运行时支撑程序包,过程相关的几个概念,过程定义是一个声明，它的最简单的形式是把一个标识符（过程的名字）和一段语句联系起来。当过程名出现在可执行语句中时，则称过程在该点被调用 出现在过程定义中

2、的标识符称为形式参数（或形参）出现在过程调用中的标识符或常数称为实在参数（或实参）,一个过程的一次执行指的是从过程体的起点开始，最后退出该过程，将控制返回到该过程被调用之后的位置。一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体就产生该过程的一个活动。从执行该过程体的第一步操作到最后一步操作之间的操作序列所花的时间称为该过程的一个活动的生存期,声明的作用域,语言中名字的声明是把信息与名字联系起来的语法结构。区分同名程序声明：最接近的嵌套规则int a,b;int*p;int foo(int a)int b,c;char*p;p=malloc(sizeof(char);b=foo

3、(1);,作用域：一个声明起作用的程序部分称为该声明的作用域局部和非局部：过程中名字的出现，如果是在该过程的一个声明的作用域内，则这个出现称为局部于该过程,参数的传递,传地址（常用）：把实在参数的地址传递给相应的形式参数 传值（常用）：调用段把实在参数的值传给被调用段。被调用段把实参值抄进形式单元中，再使用。得结果：形式参数对应有两个单元，第一个单元放实参的地址，第二个单元放实参的值。对形式参数的任何引用或赋值都看成是对第二个单元的直接访问，过程返回前必须把第二个单元的内容存放到第一个单元所指的那个实参单元之中 传名：(ALGOL60)过程调用相当于把被调过程的过程体抄到调用出现的位置，把其中

4、任一出现的形式参数都替换成相应的实在参数（文字替换）,名字的绑定,程序中声明的名字和动态数据对象的关系数据对象是保存值的存储单元一个名字可能代表不同的数据对象环境：表示将名字映射到存储单元（即名字的左值）的函数状态：表示将存储单元映射到它所保存的值（即名字的右值）的函数赋值操作只改变状态，但不改变环境结合：如果环境把存储单元s联系到名字x，则称x绑定到s，这个联系本身称为x的绑定,名字绑定要考虑的问题,过程是否递归当控制从过程的活动返回时，局部名字的值是否要保留过程能否引用非局部的名字过程调用时参数是如何传递的过程是否可以作为参数被传递过程能否作为结果值返回存储区能否在程序控制下动态地分配存储

5、区是否必须显式地释放,6.2 运行时内存的划分,程序运行时如何使用内存：目标代码的存放目标代码可以存放在静态确定的区域，其长度在编译时即可确定数据对象可静态分配的数据对象，其地址可以编译到目标代码中动态分配控制栈：记录过程活动堆：可以存放动态分配的数据等，但开销要比栈大,局部数据区的内容,活动记录：过程的依次执行所需要的信息用一块连续的存储区来管理，这块存储区叫做活动记录或帧并不是所有的语言或编译器都是如此寄存器的使用活动记录的操作：过程被调用时入栈过程返回时出栈,活动记录的各个域的作用,临时数据：临时变量的存储等局部数据：局部于过程执行的数据机器状态：保存过程调用前的机器状态信息返回地址可选

6、的访问链：用于非局部数据的访问可选的控制链：指向调用者的活动记录实在参数域：参数个数较少时，可以考虑用寄存器传递，效率高；参数多时用用这个域传递返回值域：用于存放被调用过程返回给调用过程的值，也可以用寄存器返回（效率高，但形式受限制）,6.3 存储分配策略,静态存储分配栈式存储分配堆式存储分配,静态存储分配策略,名字的绑定：编译时实现，不需要运行时支撑程序名字和存储的绑定是固定的允许名字的值在过程停止活动后保持根据名字的类型，编译器可以在静态时刻确定该名字所需的存储空间，效率局限：数据对象的长度和它在内存中位置的限制必须在编译时知道不允许递归过程不允许有动态数据结构在FORTRAN77中，静态

7、存储分配策略，每个过程的活动记录可以与它的代码放在一起,静态存储分配策略（2）,PROGRAM CNSUMECHARACTER*50BUFINTEGERNEXTCHARACTERC,PRDUCEDATA NEXT/1/,BUF/6C=PRDUCE()BUF(NEXT,NEXT)=CNEXT=NEXT+1IF(C.NE.)GOTO 6WRITE(*,(A)BUFENDCHARACTER FUNCTION PRDUCE()CHARACTER*80BUFFERINTEGERNEXTSAVE BUFFER,NEXTDATA NEXT/81/IF(NEXT.GT.80)THENREAD(*,(A)BUF

8、FERNEXT=1END IFPRDUCE=BUFFER(NEXT,NEXT)NEXT=NEXT+1END,栈式存储分配策略,递归过程要求栈分配允许动态数据对象的存在满足先进后出的次序控制栈：活动记录和栈的关系局部量的存储空间包含在对应调用的活动记录中局部量的值回随着过程调用结束而丢失控制栈top的变化和活动记录的长度相关通常，局部量相对于活动记录开始点的偏移量可以记录在符号表中,栈式存储分配策略（2）,例：例6.1的快速排序程序的活动记录在栈中的分配,Program s；a:的数据说明；procedure r;function p；procedure q begin patition;q(m

9、,i-1);q(i+1,n);end;begin r();q(1,9);,堆式存储分配策略,栈分配的局限不能使得活动停止时，局部名字的值保持被调用者的活动不能比调用者的活动活得更长，只能满足先入后出的次序堆分配把连续存储区域分成块需要时分配（活动记录或其它对象）释放次序任意堆可以与栈分配结合起来C+语言中，基本保持栈的形式，堆用于动态对象的分配C、Pascal语言中的指针的动态分配等,堆空间的的释放不释放存储空间溢出是停止显式释放Free（C，PL/1），deallocation（Ada）有可能引起悬挂引用隐式释放单引用引用计数垃圾收集（Garbage collection）堆的分配和释放的优化,