编译原理-第9章分析.ppt

第九章运行时存储空间组织,在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。,标识符对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。,程序中使用的存储单元都由标识符来表示。,第九章运行时存储空间组织,9.1目标程序运行时的活动（略）9.2运行时存储器的划分9.3静态存储分配（略）9.4简单的栈式存储分配9.5嵌套过程语言的栈式实现9.6堆式动态存储分配,9.2运行时存储器的划分,一、运行时存储器的划分1.编译器需要在存储区保护的对象（1）目标代码编译时可确定，故可放在一个静态确定的区域（2）数据对象部分数据对象的大小在编译时可确定，故也可放在一个静态确定的区域（3）跟踪过程活动的控制栈,2.栈和堆A.栈：用扩充的栈来管理过程的活动，当发生过程调用时，中断当前活动的执行，激活新被调用过程的活动，并把包含在这个活动生存期中的数据对象以及该活动有关的其它信息存入栈中。当控制从调用返回时，将所占存储空间弹出栈顶。同时，被中断的活动恢复执行。B.堆（heap）存放动态数据，大小可随程序的运行而改变。,9.2运行时存储器的划分,二、活动记录1.活动记录：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，该连续的存储块叫活动记录。当过程调用时，产生一个过程的新的活动，用一个活动记录表示该活动的相关信息，并将其压入栈。当过程返回时，将该活动记录从栈中弹出。,9.2运行时存储器的划分,2.活动记录的内容（1）连接数据SP指向现行过程的活动记录在栈里的起始位置。返回地址动态链指向调用该过程前的最新活动记录地址的指针。静态链指向静态直接外层最新活动记录地址的指针，用来访问非局部数据.（2）形式单元存放相应的实在参数的地址或值（3）局部数据区局部变量简单变量内情向量局部数据的内情向量，即数组元素临时工作单元存放对表达式求值的结果,9.2运行时存储器的划分,9.2运行时存储器的划分,三、存储分配策略1.静态存储分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。,2.栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。,3.堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆.,9.4简单的栈式存储分配,1.前提：假设程序语言无分程序结构，过程定义不允许嵌套，但允许过程的递归调用。例如：C语言2.过程：运行时每当进入一个过程即一个新的活动开始，就把其它活动记录压入栈（置于栈顶），从而形成过程工作时的数据区.当活动结束即过程退出时，再把其活动记录弹出栈，这样，它在栈顶上的数据区也随即不复存在.,3.举例（1）主程序调用过程Q，而Q又调用R，在R进入运行后的存储结构.,9.4简单的栈式存储分配,3.举例（2）主程序调用过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构.,9.4简单的栈式存储分配,9.4简单的栈式存储分配,3.举例（3）主程序先调用过程Q，然后主程序调用R，且过程Q不调用Q和R.,4.指示器SP总是指向现行过程活动记录的起点，用于访问局部数据.指示器TOP始终指向（已占用）栈顶单元.,9.4简单的栈式存储分配,一、C的活动记录1.C的活动记录的项目（1）连接数据A.老SP值:即前一活动记录的地址B.返回地址（2）参数个数（3）形式单元存放实在参数的值或地址（4）过程的局部变量数组内情向量临时工作单元,9.4简单的栈式存储分配,2.（1）不允许过程嵌套非局部量仅能出现在源程序头，可采用静态存储分配，编译时可确定其地址（2）局部变量或形参在活动记录中的位置确定即对它们都分配了存储单元，其地址是相对于活动记录的基地址SP的绝对地址=活动记录基地址+相对地址变址访问XSPX代表相对数，即相对于活动记录起点的地址，编译时可完全确定下来.,9.4简单的栈式存储分配,9.4简单的栈式存储分配,9.5嵌套过程语言的栈式实现,前提：假定允许过程定义嵌套，如Pascal语言，但去掉Pascal中的“文件。,程序举例：课本P258图9.15,一、非局部名字的访问的实现,9.5嵌套过程语言的栈式实现,1.静态链和活动记录A.静态链活动记录的一个域，从一个过程的当前活动记录指向其静态直接外层的最新活动记录。,动态链活动记录一个域，从一个过程的当前活动记录指向调用该过程前正在运行的过程的最新的活动记录的基地址。,B.活动记录结构P259图9.16,C.程序运行时栈的变化过程举例：,过程S中调用Q时,过程P中调用S时,过程Q中调用R时,32313029282726252423222120191817,161514131211109876543210,过程R中递归调用R,静态链:通过其值可以找到当前过程/活动可以引用的“非局部变量”的过程的活动记录的基址，从而找到要引用的“非局部变量”。,9.5嵌套过程语言的栈式实现,动态链:通过其值可以找到当前过程/活动结束后，需要返回的上一层活动记录的基址SP。,D.含义：,2.嵌套层次显示表（display）和活动记录,9.5嵌套过程语言的栈式实现,A.嵌套层次显示表：每进入一个过程后，在建立它的活动区的同时建立该表。,B.表的内容：,举例：令过程R的外层为Q，Q的外层为P，则R运行时display表为：,C.“非局部量”地址的确定：绝对地址=display静态层数+相对地址D.活动记录结构:P261图9.18E.程序运行时栈的变化过程P262-263图9.19,9.5嵌套过程语言的栈式实现,9.5嵌套过程语言的栈式实现,F.静态链方法与显示表方法的比较：通过显示表访问非局部量要比沿着静态链访问非局部量的速度快。,原因：因为通过显示表的一个域，可以确定任意外层活动记录的指针，再沿着这个指针便可以找到处于外层活动记录的非局部量。,9.5嵌套过程语言的栈式实现,1.parTT为数组（1）或者传递数组T的首地址（2）或者传递数组T的内情向量地址2.ParTT为过程假设：过程P把过程T作为在世在参数传递过程Q，随后，Q又通过引用相应的形式参数调用T。3.ParTT为标号,二.参数传递的实现,在进入T之后，为了建立T自己的display，T必须知道它直接外层的display。又P的display或者正好就是这个外层的display，或者包含了这个外层display而由于T的层数是已知的只要知道P的display，T就可以用它来建立自己的display。即假定T的层数为1，则T的display乃是由P的display的前1个单元的内容和SP的现行值所组成。,为了使得过程T工作时能够知道过程P的display，必须在P把T作为实参传递给Q的时候把P自身的display地址也传过去。即：过程P中的parT的作用可刻画为建立如下所示的两个相继临时单元：第一个临时单元B1：过程T的入口地址；第二个临时单元B2：现行的display地址。；然后执行（i+1）TOP:=addr(B1)把第一临时单元B1的地址传给Q,9.5嵌套过程语言的栈式实现,2.ParTT为过程,假定过程Q现在执行到调用语句callZ,mZ形式参数，形式单元Z中已含有上述B1的地址故B1的内容将用来作为转子指令的目的地址（即转进过程T）B2的内容将作为“全局display地址”（第三项连接数据）传送给T,9.5嵌套过程语言的栈式实现,2.ParTT为过程,9.6堆式动态存储分配,1.堆式动态存储分配使用的情况（1）允许用户自由地申请数据空间和退还空间（2）不仅有过程而且有进程的程序结构即空间的使用未必服从“先请后还，后请先还”的原则例如：Pascal语言中的标准过程new-dispose,2.该种分配方法必须考虑的几个主要问题（1）当运行程序要求一块体积为N的空间时，应该分配哪一块给它？（2）如果运行程序要求一块体积为N的空间，但所有空闲块的总和也不够N，那该怎么办？,一、堆式动态存储分配的实现1.定长块管理（1）实现方法：（2）优点：,9.6堆式动态存储分配,2.变长块管理（1）实现方法（2）实现的非配策略A.首次满足法B.最有满足法C.最差满足法（3）3种分配策略的比较A.适用情况B.时间比较,9.6堆式动态存储分配,二、隐式存储回收1.隐式存储回收的要求：用户程序和支持运行的回收子程序并行工作.原因:回收子程序需要知道分配给