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

运行时存储空间的组织第六章本章要求•主要内容：程序的静态文本与它运行时的活动之间的关系，源程序运行时各种对象的存储空间主要有三种方式分配方式：静态存储分配、栈式存储分配和堆式存储分配•重点掌握：源程序运行时的活动，参数传递方式，程序中名字的作用域，局部数据区的内容，存储空间的分配方式6.1程序执行时的活动•静态和动态的联系–名字和数据对象–数据对象的动态表示–名字的作用域–数据对象的存储分配–过程和活动–参数处理•运行时支撑程序包过程相关的几个概念•过程定义是一个声明，它的最简单的形式是把一个标识符（过程的名字）和一段语句联系起来。•当过程名出现在可执行语句中时，则称过程在该点被调用•出现在过程定义中的标识符称为形式参数（或形参）•出现在过程调用中的标识符或常数称为实在参数（或实参）•一个过程的一次执行指的是从过程体的起点开始，最后退出该过程，将控制返回到该过程被调用之后的位置。•一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体就产生该过程的一个活动。•从执行该过程体的第一步操作到最后一步操作之间的操作序列所花的时间称为该过程的一个活动的生存期声明的作用域•语言中名字的声明是把信息与名字联系起来的语法结构。•区分同名程序声明：最接近的嵌套规则inta,b;int*p;intfoo(inta){intb,c;char*p;p=malloc(sizeof(char));b=foo(1);…}•作用域：一个声明起作用的程序部分称为该声明的作用域•局部和非局部：过程中名字的出现，如果是在该过程的一个声明的作用域内，则这个出现称为局部于该过程参数的传递•传地址（常用）：把实在参数的地址传递给相应的形式参数•传值（常用）：调用段把实在参数的值传给被调用段。被调用段把实参值抄进形式单元中，再使用。•得结果：形式参数对应有两个单元，第一个单元放实参的地址，第二个单元放实参的值。对形式参数的任何引用或赋值都看成是对第二个单元的直接访问，过程返回前必须把第二个单元的内容存放到第一个单元所指的那个实参单元之中•传名：(ALGOL60)过程调用相当于把被调过程的过程体抄到调用出现的位置，把其中任一出现的形式参数都替换成相应的实在参数（文字替换）名字的绑定静态概念动态概念过程的定义名字的声明声明的作用域过程的活动名字的绑定绑定的生命期•程序中声明的名字和动态数据对象的关系–数据对象是保存值的存储单元–一个名字可能代表不同的数据对象•环境：表示将名字映射到存储单元（即名字的左值）的函数•状态：表示将存储单元映射到它所保存的值（即名字的右值）的函数•赋值操作只改变状态，但不改变环境•结合：如果环境把存储单元s联系到名字x，则称x绑定到s，这个联系本身称为x的绑定名字绑定要考虑的问题•过程是否递归•当控制从过程的活动返回时，局部名字的值是否要保留•过程能否引用非局部的名字•过程调用时参数是如何传递的•过程是否可以作为参数被传递•过程能否作为结果值返回•存储区能否在程序控制下动态地分配•存储区是否必须显式地释放6.2运行时内存的划分•程序运行时如何使用内存：–目标代码的存放•目标代码可以存放在静态确定的区域，其长度在编译时即可确定–数据对象•可静态分配的数据对象，其地址可以编译到目标代码中•动态分配–控制栈：记录过程活动–堆：可以存放动态分配的数据等，但开销要比栈大过程1的目标代码代码区过程2的目标代码……过程n的目标代码全局变量和静态变量静态数据栈自由空间堆动态数据局部数据区的内容•活动记录：过程的依次执行所需要的信息用一块连续的存储区来管理，这块存储区叫做活动记录或帧•并不是所有的语言或编译器都是如此•寄存器的使用•活动记录的操作：–过程被调用时入栈–过程返回时出栈返回值实在参数可选的控制链可选的访问链保存的机器状态局部数据临时数据一般的活动记录活动记录的各个域的作用•临时数据：临时变量的存储等•局部数据：局部于过程执行的数据•机器状态：保存过程调用前的机器状态信息–返回地址•可选的访问链：用于非局部数据的访问•可选的控制链：指向调用者的活动记录•实在参数域：参数个数较少时，可以考虑用寄存器传递，效率高；参数多时用用这个域传递•返回值域：用于存放被调用过程返回给调用过程的值，也可以用寄存器返回（效率高，但形式受限制）6.3存储分配策略•静态存储分配•栈式存储分配•堆式存储分配静态存储分配策略•名字的绑定：–编译时实现，不需要运行时支撑程序–名字和存储的绑定是固定的•允许名字的值在过程停止活动后保持–根据名字的类型，编译器可以在静态时刻确定该名字所需的存储空间，效率–局限：•数据对象的长度和它在内存中位置的限制必须在编译时知道•不允许递归过程•不允许有动态数据结构•在FORTRAN77中，静态存储分配策略，每个过程的活动记录可以与它的代码放在一起静态存储分配策略（2）PROGRAMCNSUMECHARACTER*50BUFINTEGERNEXTCHARACTERC,PRDUCEDATANEXT/1/,BUF/‘’/6C=PRDUCE()BUF(NEXT,NEXT)=CNEXT=NEXT+1IF(C.NE.‘’)GOTO6WRITE(*,‘(A)’)BUFENDCHARACTERFUNCTIONPRDUCE()CHARACTER*80BUFFERINTEGERNEXTSAVEBUFFER,NEXTDATANEXT/81/IF(NEXT.GT.80)THENREAD(*,‘(A)’)BUFFERNEXT=1ENDIFPRDUCE=BUFFER(NEXT,NEXT)NEXT=NEXT+1ENDCHARACTER*80BUFFERINTEGERNEXT一个FORTRAN77程序局部标识符的静态存储CHARACTER*80BUFINTEGERNEXTCHARACTERCPRDUCE的代码CNSUME的代码PRDUCE的活动记录CNSUME的活动记录静态数据代码栈式存储分配策略•递归过程要求栈分配•允许动态数据对象的存在•满足先进后出的次序•控制栈：–活动记录和栈的关系–局部量的存储空间包含在对应调用的活动记录中–局部量的值回随着过程调用结束而丢失–控制栈top的变化和活动记录的长度相关–通常，局部量相对于活动记录开始点的偏移量可以记录在符号表中栈式存储分配策略（2）例：例6.1的快速排序程序的活动记录在栈中的分配Programs；a:的数据说明；procedurer;functionp；procedureqbeginpatition;q(m,i-1);q(i+1,n);end;beginr();q(1,9);}栈上的活动记录活动树注解ssa:arrays的活动记录sa:arrayri:integerr被激活srsa:arrayq(1,9)k:integerr的活动记录弹出栈，q(1,9)的活动记录进栈srq(1,9)sa:arrayq(1,9)k:integer控制刚返回到q(1,3)srq(1,9)q(1,3)k:integerp(1,9)q(1,3)p(1,3)q(1,0)堆式存储分配策略•栈分配的局限–不能使得活动停止时，局部名字的值保持–被调用者的活动不能比调用者的活动活得更长，只能满足先入后出的次序•堆分配把连续存储区域分成块–需要时分配（活动记录或其它对象）–释放次序任意•堆可以与栈分配结合起来–C++语言中，基本保持栈的形式，堆用于动态对象的分配–C、Pascal语言中的指针的动态分配等•堆空间的的释放–不释放•存储空间溢出是停止–显式释放•Free（C，PL/1），deallocation（Ada）…•有可能引起悬挂引用–隐式释放•单引用•引用计数•垃圾收集（Garbagecollection）•堆的分配和释放的优化