运行时存储空间组织概述

编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院第七章第七章 运行时存储空间组织运行时存储空间组织vv本章讨论目标程序运行时的活动和运行时本章讨论目标程序运行时的活动和运行时的存储组织与管理的存储组织与管理vv本章要点：本章要点：过程的活动与参数传递过程的活动与参数传递静态存储分配静态存储分配 简单的栈式存储分配简单的栈式存储分配 嵌套过程语言的栈式实现嵌套过程语言的栈式实现 堆式动态存储分配堆式动态存储分配 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院过程的活动与参数传递过程的活动与参数传递 定定义义和和调调用用过过程程（函函数数）是是程程序序语语言言的的主主要要特特征征之之一一。过过程程是是模模块块程程序序设设计计的的主主要要手手段段，同同时时也也是是节节省省程程序序代代码码和和扩扩充充语言能力的主要途径。语言能力的主要途径。一一个个过过程程一一旦旦定定义义后后，就就可可以以在在别别的的地地方方调调用用它它。调调用用与与被被调调用用(过过程程)两两者者之之间的信息往来通过全局量或参数传递。间的信息往来通过全局量或参数传递。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例如，下面的例如，下面的例如，下面的例如，下面的C C语言程序：语言程序：语言程序：语言程序：#include“stdio.h”#include“stdio.h”void showme(int a,int b,int c)void showme(int a,int b,int c)printf printf(“a=%d,(“a=%d,b=%d,b=%d,c=%dn”,c=%dn”,a,a,b,b,c);c);main()main()int x=10,y=20,z=30;int x=10,y=20,z=30;showme(z,y,x);showme(z,y,x);编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院其中其中a、b、c称为形式参数称为形式参数(简称形参简称形参)函数调用语句：函数调用语句：showme(z,y,x)中中的的z、y、x则则称称为为实实在在参参数数(简简称称实实参参)。实实参参甚甚至至也也可可以以是是一一个个较较复复杂杂的的表表达达式式而而不不仅仅仅仅只只是是一一个个变变量量。实实参参和和对对应应的的形形参参在在性性质质上上应应相相容容不悖。不悖。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院过程的活动过程的活动vv一个过程的活动是指该过程的一次执行。一个过程的活动是指该过程的一次执行。vv过程的生存期是指从执行该过程体第一步操过程的生存期是指从执行该过程体第一步操作到最后一步操作之间的操作程序，包括执作到最后一步操作之间的操作程序，包括执行该过程时调用其他过程花费的时间。行该过程时调用其他过程花费的时间。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 形形式式参参数数提提供供了了参参数数替替换换的的手手段段，在在过过程程调调用用时时可可以以使使用用不不同同的的数数据据作作为为实实在在参参数数来来替替换换形形式式参参数数，从从而而实实现现了了同同一一个个过过程程可可以以对对不不同同的的实实在在参参数数进进行行相相同同操操作作的的功功能能。那那么么，如如何何把把实实在在参参数数传传递递给给相相应应的的形形式式参参数数呢呢？程程序序语语言言中中参参数数传传递递的的方方式式主主要要有有传传值值(call by value)、传传地地址址(call by reference)和和传名传名(call by name)三种。三种。参数的传递参数的传递 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院1传值传值 传传值值是是最最简简单单的的参参数数传传递递方方法法。所所谓谓传传值值，就就是是计计算算出出实实在在参参数数的的值值然然后后把把它它传传给给被被调调用用过过程程相相对对应应的的形形式式参参数数，具体过程如下：具体过程如下：(1)把把形形式式参参数数当当作作过过程程的的局局部部变变量量处处理理，即即在在被被调调用用过过程程中中开开辟辟形形式式参参数数的存储空间的存储空间(即形式单元即形式单元)。(2)调调用用过过程程计计算算出出实实在在参参数数的的值值，并将该值放入为形式单元开辟的空间中。并将该值放入为形式单元开辟的空间中。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 (3)被被调调用用过过程程执执行行时时就就像像使使用用局局部部变量一样使用这些形式单元。变量一样使用这些形式单元。传传值值的的一一个个重重要要特特点点是是对对形形式式参参数数的的任任何何运运算算都都不不影影响响调调用用过过程程实实在在参参数数的的值值，即即参参数数传传递递后后实实在在参参数数与与对对应应的的形形式参数不再发生联系了。式参数不再发生联系了。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院2传地址传地址 所谓传地址，是指把实在参数的地所谓传地址，是指把实在参数的地址传递给相应的形式参数所对应的形式单址传递给相应的形式参数所对应的形式单元。如果实在参数是一个变量，则直接将元。如果实在参数是一个变量，则直接将该变量的地址传给相应的形式单元；如果该变量的地址传给相应的形式单元；如果实在参数是常数或表达式，则先计算其值实在参数是常数或表达式，则先计算其值并存放在某一临时单元中，然后将这个临并存放在某一临时单元中，然后将这个临时单元的地址传给相应的形式单元。时单元的地址传给相应的形式单元。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 被调用过程执行时，对形式参数的被调用过程执行时，对形式参数的任何引用或赋值都被处理成对形式单元任何引用或赋值都被处理成对形式单元的间接访问，即按形式单元中存放的地的间接访问，即按形式单元中存放的地址转到调用过程中去访问实在参数。址转到调用过程中去访问实在参数。对对形形式式参参数数的的任任何何运运算算实实际际上上都都是是对对实实在在参参数数的的运运算算，而而形形式式参参数数只只不不过过起起到到辅辅助助查查找找到到实实在在参参数数的的指指针针的的作作用用。因因此此，当当被被调调用用过过程程工工作作完完毕毕返返回回时时，形形式式单单元元所所指指的的实实在在参参数数单单元元就就保保留留了了运算的结果。运算的结果。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院3传名传名 传传名名是是高高级级语语言言ALGOL 60所所定定义义的的一一种种特特殊殊的的参参数数传传递递方方式式，其其传传递递参参数数的方法如下：的方法如下：(1)过过程程调调用用的的作作用用相相当当于于把把被被调调用用过过程程的的过过程程体体复复制制到到调调用用处处(替替换换调调用用语语句句)，并并将将过过程程体体中中所所有有出出现现的的形形式式参参数数在在文文字字上上替替换换成成相相应应的的实实在在参参数数。这这种种文文 字字 上上 的的 替替 换换 称称 为为 宏宏 扩扩 展展(Marcro Expansion)。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 (2)(2)被被被被调调调调用用用用过过过过程程程程中中中中的的的的局局局局部部部部名名名名如如如如果果果果与与与与过过过过程程程程调调调调用用用用的的的的实实实实在在在在参参参参数数数数名名名名发发发发生生生生冲冲冲冲突突突突，则则则则在在在在宏宏宏宏扩扩扩扩展展展展前前前前对对对对被被被被调调调调用用用用过过过过程程程程中中中中的的的的这这这这些些些些局局局局部部部部名名名名重重重重新新新新命命命命名名名名以以以以避避避避免免免免重重重重名名名名冲冲冲冲突。突。突。突。(3)(3)为为为为表表表表现现现现实实实实在在在在参参参参数数数数的的的的整整整整体体体体性性性性，必必必必要要要要时时时时在在在在替替替替换前把实在参数用括号括起来。换前把实在参数用括号括起来。换前把实在参数用括号括起来。换前把实在参数用括号括起来。传传传传名名名名这这这这种种种种参参参参数数数数传传传传递递递递方方方方法法法法因因因因其其其其操操操操作作作作过过过过于于于于复复复复杂杂杂杂现现现现在已很少采用。在已很少采用。在已很少采用。在已很少采用。不同的参数传递方法得到的结果不同，因此，不同的参数传递方法得到的结果不同，因此，不同的参数传递方法得到的结果不同，因此，不同的参数传递方法得到的结果不同，因此，如何选择参数传递的方法将影响语言的语义，如何选择参数传递的方法将影响语言的语义，如何选择参数传递的方法将影响语言的语义，如何选择参数传递的方法将影响语言的语义，这是编译程序在处理参数传递时应引起重视的这是编译程序在处理参数传递时应引起重视的这是编译程序在处理参数传递时应引起重视的这是编译程序在处理参数传递时应引起重视的问题。问题。问题。问题。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院运行时存储器的划分运行时存储器的划分目标代码目标代码目标代码目标代码静态数据静态数据静态数据静态数据栈栈栈栈堆堆堆堆管理过程的活动，过程调管理过程的活动，过程调用时相关信息存入栈中用时相关信息存入栈中存放动态数据存放动态数据图图7-17-1 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院静态存储分配静态存储分配 如如果果在在编编译译时时就就能能够够确确定定一一个个程程序序在在运运行行时时所所需需的的存存储储空空间间大大小小，则则在在编编译译时时就就能能够够安安排排好好目目标标程程序序运运行行时时的的全全部部数数据据空空间间，并并能能确确定定每每个个数数据据项项的的单单元元地地址址，存储空间的这种分配方法叫做静态分配。存储空间的这种分配方法叫做静态分配。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vvFORTRAN语言的特点：语言的特点：不允许过程有递归性；不允许过程有递归性；每每个个数数据据名名所所需需的的存存储储空空间间大大小小都都是是常常量量(即即不不允允许许含含可可变变体体积积的的数数据据，如如可可变变数数组组)；所所有有数数据据名名的的性性质质是是完完全全确确定定的的(不不允允许许出出现现在在运运行行时时再再动动态态确确定定其其性性质质的的名名字字)。这这些些特特点点确确保保整整个个程程序序所所需需数数据据空空间间的的总总量量在在编编译译时时是是完完全全确确定定的的，从从而而每每个个数数据据名的地址就可静态地进行分配。名的地址就可静态地进行分配。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv静静态态存存储储分分配配是是一一种种最最简简单单的的存存储储管管理理。一一般般而而言言，适适于于静静态态存存储储分分配配的的语语言言必必须满足以下条件：须满足以下条件：(1)数组的上下界必须是常数；数组的上下界必须是常数；(2)过程调用不允许递归；过程调用不允许递归；(3)不不允允许许采采用用动动态态的的数数据据结结构构(即即在在程程序序运行过程中申请和释放的数据结构运行过程中申请和释放的数据结构)。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 在在在在编编编编译译译译过过过过程程程程中中中中，给给给给程程程程序序序序中中中中的的的的变变变变量量量量或或或或数数数数组组组组分分分分配配配配存存存存储储储储单单单单元元元元的的的的一一一一般般般般做做做做法法法法是是是是：为为为为每每每每一一一一个个个个变变变变量量量量(或或或或数数数数组组组组)确确确确定定定定一一一一个个个个有有有有序序序序的的的的整整整整数数数数对对对对；其其其其中中中中，第第第第一一一一个个个个整整整整数数数数用用用用来来来来指指指指示示示示数数数数据据据据区区区区(局局局局部部部部数数数数据据据据区区区区或或或或公公公公用用用用区区区区)的的的的编编编编号号号号，第第第第二二二二个个个个整整整整数数数数则则则则用用用用来来来来指指指指明明明明该该该该变变变变量量量量(或或或或数数数数组组组组)所所所所对对对对应应应应的的的的存存存存储储储储起起起起始始始始单单单单元元元元相相相相对对对对于于于于其其其其所所所所在在在在数数数数据据据据区区区区起起起起点点点点的的的的位位位位移移移移(即即即即相相相相对对对对于于于于数数数数据据据据区区区区起起起起点点点点的的的的地地地地址址址址)；并并并并将将将将这这这这一一一一对对对对整整整整数数数数填填填填入入入入符符符符号号号号表表表表相相相相应应应应登登登登记记记记项项项项的的的的信信信信息息息息栏栏栏栏中中中中。至至至至于于于于各各各各数数数数据据据据区区区区的的的的起起起起始始始始地地地地址址址址在在在在编编编编译译译译时时时时可可可可暂暂暂暂不不不不确确确确定定定定，待待待待各各各各程程程程序序序序段段段段全全全全部部部部编编编编译译译译完完完完成成成成之之之之后后后后，再再再再由由由由连连连连接接接接装装装装配配配配程程程程序序序序最最最最终终终终确确确确定定定定，并并并并将将将将各各各各程程程程序序序序段段段段的的的的目目目目标标标标代代代代码组装成一个完整的目标程序。码组装成一个完整的目标程序。码组装成一个完整的目标程序。码组装成一个完整的目标程序。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 一一个个FORTRAN程程序序段段的的局局部部数数据据区区可可由由图图7-2所所示示的的项项目目组组成成。其其中中，隐隐参参数数是是指指过过程程调调用用时时的的连连接接信信息息(不不在在源源程程序序中中明明显显出出现现)，如如调调用用时时的的返返回回地地址址、调调用用时时寄寄存存器器的的保保护护等等；形形式式单单元元用用来来存存放放过过程程调调用用时时形形参参与与实实参参结结合合的的实实参参地址或值。地址或值。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院一个一个FORTRAN程序段的局部数据区程序段的局部数据区保存调用此程序段保存调用此程序段时的返回地址时的返回地址保存调用段留在寄保存调用段留在寄存器中的相关信息存器中的相关信息存放实参的存放实参的地址或值地址或值图图7-27-2 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院简单的栈式存储分配简单的栈式存储分配 我我们们首首先先考考虑虑一一种种简简单单程程序序语语言言的的实实现现，这这种种语语言言没没有有分分程程序序结结构构，过过程程定定义义不不允允许许嵌嵌套套，但但允允许许过过程程的的递递归归调调用用，允允许许过过程程含含有有可可变变数数组组。例例如如，C语语言言除除不不允允许许含含有有可可变变数数组组外外，就就是是这这样样一一种种语语言言。C语语言言的的程程序结构如下：序结构如下：编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院全局数据说明全局数据说明全局数据说明全局数据说明main()main()mainmain中的数据说明中的数据说明中的数据说明中的数据说明 void R()void R()R R中的数据说明中的数据说明中的数据说明中的数据说明 void Q()void Q()QQ中的数据说明中的数据说明中的数据说明中的数据说明 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv例例如如，下下面面计计算算n！的的C语语言言程程序序就就是是一一个个递递归归调调用用的的程程序序，它它的的执执行行过过程程可可以以用栈来实现。用栈来实现。#include“stdio.h”long factorial(int n)if(n1)if(n1)return(n*factorial(n1);return(n*factorial(n1);elseelsereturn(1);return(1);编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院main()main()int num;int num;dodoscanf(“%d”,&num);scanf(“%d”,&num);if(num=0&num=0&num=0);while(num=0);编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 使使用用栈栈式式存存储储分分配配法法意意味味着着程程序序运运行行时时，每每当当进进入入一一个个过过程程(或或函函数数)就就有有一一个个相相应应的的活活动动记记录录累累筑筑于于栈栈顶顶，此此记记录录含含有有连连接接数数据据、形形式式单单元元、局局部部变变量量、局局部部数数组组的的内内情情向向量量和和临临时时工工作作单单元元等等；在在进进入入过过程程和和执执行行过过程程的的可可执执行行语语句句之之前前，再再把把局局部部数数组组所所需需空空间间累累筑筑于于栈栈顶顶，从而形成过程工作时的完整数据区。从而形成过程工作时的完整数据区。栈式存储分配与活动记录栈式存储分配与活动记录 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 注注意意，每每个个过过程程的的活活动动记记录录的的体体积积在在编编译译时时可可以以静静态态地地确确定定。但但由由于于允允许许含含有有可可变变数数组组，所所以以数数组组的的大大小小只只有有在在运运行行时时才才能能知知道道。因因数数组组区区的的大大小小不不能能预预先先获获知知，为为了了扩扩充充方方便便，所所以以只只能能将将数数组组区区累累筑筑于于活活动动记记录录之之上上的的当当前前栈栈顶顶。当当一一个个过过程程工工作作完完毕毕返返回回时时，它它在在栈栈顶顶的的数数据据区区(包包括括活活动动记记录录和和数数组组区区)也也随随即不复存在。即不复存在。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 对对C语言来说，由于其不含可变数语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部组，因而它的活动记录本身包含了局部数组的空间。图数组的空间。图73和图和图74分别给出了分别给出了C语言和含可变数组的某简单语言程序运语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序行时的数据空间结构，即显示了主程序在调用了过程在调用了过程Q，Q又调用了过程又调用了过程R，且，且在在R投入运行后的存储结构。投入运行后的存储结构。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 图73 C语言程序的存储组织 SPSP指示器总是指向执指示器总是指向执指示器总是指向执指示器总是指向执行过程活动记录的起行过程活动记录的起行过程活动记录的起行过程活动记录的起点，而点，而点，而点，而TOPTOP指示器则指示器则指示器则指示器则始终指向始终指向始终指向始终指向(已占用已占用已占用已占用)栈栈栈栈顶单元。当进入一个顶单元。当进入一个顶单元。当进入一个顶单元。当进入一个过程时，过程时，过程时，过程时，TOPTOP指向为指向为指向为指向为此过程创建的活动记此过程创建的活动记此过程创建的活动记此过程创建的活动记录的顶端；在分配数录的顶端；在分配数录的顶端；在分配数录的顶端；在分配数组区之后组区之后组区之后组区之后(如果有的话如果有的话如果有的话如果有的话)，TOPTOP又改为指向数又改为指向数又改为指向数又改为指向数组区组区组区组区(从而是该过程整从而是该过程整从而是该过程整从而是该过程整个数据区个数据区个数据区个数据区)的顶端。的顶端。的顶端。的顶端。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 图74 含可变数组程序的存储组织 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vvC的的活活动动记记录录含含有有以以下下几几个个区区段段(如如图图75所示所示)：(1)连连接接数数据据(两两项项)：老老SP值值(即即前前一活动记录的起始地址一活动记录的起始地址)和返回地址；和返回地址；(2)参数个数；参数个数；(3)形形式式单单元元(存存放放实实在在参参数数的的值值或或地地址址)；(4)过过程程的的局局部部变变量量(简简单单变变量量)、数数组的内情向量和临时工作单元。组的内情向量和临时工作单元。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图75 C过程的活动记录 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv C C语语语语言言言言不不不不允允允允许许许许过过过过程程程程(函函函函数数数数)嵌嵌嵌嵌套套套套，也也也也即即即即不不不不允允允允许许许许一一一一个个个个过过过过程程程程的的的的定定定定义义义义出出出出现现现现在在在在另另另另一一一一个个个个过过过过程程程程的的的的定定定定义义义义之之之之内内内内。因因因因此此此此，C C语语语语言言言言的的的的非非非非局局局局部部部部变变变变量量量量仅仅仅仅能能能能出出出出现现现现在在在在源源源源程程程程序序序序头头头头，非非非非局局局局部部部部变变变变量量量量可可可可采采采采用用用用静静静静态态态态存存存存储储储储分分分分配配配配并并并并在在在在编编编编译时确定它们的地址。译时确定它们的地址。译时确定它们的地址。译时确定它们的地址。vv 由由由由图图图图7575可可可可知知知知，过过过过程程程程的的的的每每每每一一一一局局局局部部部部变变变变量量量量或或或或形形形形参参参参在在在在活活活活动动动动记记记记录录录录中中中中的的的的位位位位置置置置都都都都是是是是确确确确定定定定的的的的；也也也也就就就就是是是是说说说说，这这这这些些些些变变变变量量量量或或或或形形形形参参参参所所所所分分分分配配配配的的的的存存存存储储储储单单单单元元元元其其其其地地地地址址址址都都都都是是是是相相相相对对对对于于于于活活活活动动动动记记记记录录录录的的的的基基基基址址址址SPSP的的的的。因因因因此此此此，变变变变量量量量和和和和形形形形参运行时在栈上的绝对地址是：参运行时在栈上的绝对地址是：参运行时在栈上的绝对地址是：参运行时在栈上的绝对地址是：绝对地址绝对地址绝对地址绝对地址=活动记录基址活动记录基址活动记录基址活动记录基址(SP)+(SP)+相对地址相对地址相对地址相对地址 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 对对当当前前正正在在执执行行(即即活活动动)的的过过程程，其其任任何何局局部部变变量量或或形形参参X的的引引用用均均可可表表示示为为变变址址访访问问XSP。此此处处X代代表表X相相对对于于活活动动记记录录基基址址的的偏偏移移量量，这这个个偏偏移移量量(即即相相对对数数)在在编编译译时时可可完完全全确确定定下下来来。过过程程的的局局部部数数组组的的内内情情向向量量的的相相对对地地址址在在编编译译时时也也同同样样可可完完全全确确定定下下来来，一一旦旦数数据据空空间间在在过过程程里里获获得得分分配配后后，对对数数组组元元素素的引用也就容易用变址的方式进行访问。的引用也就容易用变址的方式进行访问。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv过程的执行过程的执行1过程调用过程调用 过程调用的中间代码序列为：过程调用的中间代码序列为：par T1 par T2 par Tn call P,n 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 由由于于此此时时TOP是是指指向向被被调调用用过过程程P之之前前的的栈栈顶顶，而而P的的形形式式单单元元和和活活动动记记录录起起点点之之间间的的距距离离是是确确定定的的(等等于于3，参参见见图图75)，因因而而由由调调用用过过程程给给将将要要调调用用的的过过程程P的的活活动动记记录录(正正在在形形成成中中)的的形形式式单单元元传传递递实实参参 值值 或或 实实 参参 地地 址址，即即 每每 个个 par Ti(i=1,2,n)可直接翻译成如下指令：可直接翻译成如下指令：(i+3)TOP=Ti /*传递参数值传递参数值*/或或 (i+3)TOP=addrTi /*传传递递参参数数地地址址*/编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 而四元式而四元式call P,n则翻译成：则翻译成：1TOP=SP /*保保护护现现行行SP*/3TOP=n /*传传递递参参数数个数个数*/JSR P /*转转子子指指令令，转向转向P过程的第一条指令过程的第一条指令*/过过程程P调调用用之之前前，先先构构造造出出P的的活活动动记记录录部部分内容，见图分内容，见图76所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图76 过程P调用前先构造P的活动记录部分内容 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院2过程进入过程进入 转转入入过过程程P后后，首首先先要要做做的的工工作作是是定定义义新新活活动动记记录录的的SP，保保护护返返回回地地址址和和定定义义新新活动记录的活动记录的TOP值，即执行下述指令：值，即执行下述指令：SP=TOP+1 /*定义新定义新SP*/1SP=返回地址返回地址 /*保护返回地址保护返回地址*/TOP=TOP+L /*定义新定义新TOP*/其其中中，L是是过过程程P的的活活动动记记录录所所需需的的单单元数，这个数在编译时可静态地计算出来。元数，这个数在编译时可静态地计算出来。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 对对含含可可变变数数组组(非非C语语言言)的的情情况况来来说说，因因为为过过程程可可含含可可变变数数组组且且所所有有数数组组都都分分配配在在活活动动记记录录的的顶顶上上，所所以以紧紧接接上上述述指指令令之之后后应应是是对对数数组组进进行行存存储储分分配配的的指指令令(如如果果含含有有局局部部数数组组)，这这些些指指令令是是在在翻翻译译数数组组说说明明时时产产生生的的。对对每每个个数数组组说说明明，相相应应的的目目标标指指令令组组将做以下几件工作：将做以下几件工作：(1)计算各维的上、下限；计算各维的上、下限；(2)调调用用数数组组空空间间分分配配子子程程序序，其其参参数数是是各维的上、下限和内情向量单元首地址。各维的上、下限和内情向量单元首地址。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 数数组组空空间间分分配配子子程程序序计计算算并并填填好好内内情情向向量量的的所所有有信信息息，然然后后在在TOP所所指指的的位位置置之之上上留留出出数数组组所所需需的的空空间间，并并将将TOP调调整整为为指指向向数数组组区区的的顶顶端端。进进入入过过程程P后所做的工作如图后所做的工作如图77所示。所示。此此后后，在在过过程程段段执执行行语语句句的的工工作作过过程程中中，凡凡引引用用形形式式参参数数、局局部部变变量量或或数数组组元素都将以元素都将以SP为基址进行相对访问。为基址进行相对访问。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图77 进入过程P后所做的工作示意 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院3过程返回过程返回 C语言以及其它一些相似的语言含有语言以及其它一些相似的语言含有return(E)形式的返回语句，其中形式的返回语句，其中E为表达为表达式。假定式。假定E值已计算出来并存放在某临时值已计算出来并存放在某临时单元单元T中，则此时即可将中，则此时即可将T值传送到某个特值传送到某个特定的寄存器中定的寄存器中(调用过程将从这个特定的调用过程将从这个特定的寄存器中获得被调用过程寄存器中获得被调用过程P的结果的结果)。剩下。剩下的工作就是恢复的工作就是恢复SP和和TOP为进入过程为进入过程P之之前的原值前的原值(即指向调用过程的活动记录及即指向调用过程的活动记录及工作空间工作空间)，并按返回地址实行无条件转，并按返回地址实行无条件转移，即执行下述指令序列：移，即执行下述指令序列：编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 TOP=SP1 /*恢恢复复调调用用过过程程的的TOP值值*/SP=0SP /*恢恢复复调调用用过过程程的的SP值值*/X=2TOP /*将将返返回回地地址址送送X*/UJ 0X /*无无条条件件转转移移，即按即按X的地址返回到调用过程的地址返回到调用过程*/过程过程P的返回示意如图的返回示意如图78所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 图78 过程P的返回示意 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院嵌套过程语言的栈式实现嵌套过程语言的栈式实现 在在简简单单程程序序语语言言实实现现中中是是允允许许过过程程的的递递归归调调用用的的，并并且且过过程程中中可可含含有有可可变变数数组组。现现在在，我我们们再再加加上上一一种种功功能能，即即允允许许过过程程的嵌套性。的嵌套性。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 在在讨讨论论中中，常常常常要要用用到到过过程程定定义义的的“嵌嵌套套层层次次”(简简称称层层数数)这这个个概概念念。我我们们始始终终假假定定主主程程序序的的层层数数为为0，因因此此主主程程序序称称为为第第0层层过过程程。如如果果过过程程Q是是在在层层数数为为i的的过过程程P内内定定义义的的，并并且且P是是包包围围Q的的最最小小过过程程，则则Q的的层层数数就就为为i+1。当当编编译译程程序序处处理理过过程程说说明明时时，过过程程的的层层数数将将作作为为过程名的一个重要属性登记在符号表中。过程名的一个重要属性登记在符号表中。嵌套层次显示表嵌套层次显示表(DISPLAY)和活动记录和活动记录 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 由由于于过过程程定定义义是是嵌嵌套套的的，因因而而一一个个过过程程可可以以引引用用包包围围它它的的任任一一外外层层过过程程所所定定义义的的变变量量或或数数组组。也也就就是是说说，运运行行时时，一一个个过过程程Q可可能能引引用用它它的的任任一一外外层层过过程程P的的最最新新活活动动记记录录中中的的某某些些数数据据。因因此此，过过程程Q运运行行时时必必须须知知道道它它的的所所有有外外层层的的最最新新活活动动记记录录的的地地址址。由由于于允允许许递递归归和和可可变变数数组组的的存存在在，过过程程的的活活动动记记录录位位置置(即即使使是是相相对对位位置置)也也往往往往是是变变迁迁的的，因因而而必必须须设设法法跟跟踪踪每每个个外外层层过过程程的的最最新新活活动记录的位置。动记录的位置。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv采用嵌套层次显示表采用嵌套层次显示表DISPLAY，其优点是，其优点是访问非局部量的速度较快。访问非局部量的速度较快。每进入一个过程后，在建立它的活动记录每进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表区的同时建立一张嵌套层次显示表DISPLAY。假定现在进入的过程层数为假定现在进入的过程层数为i，则它的，则它的DISPLAY表含有表含有i+1个单元。此表本身是一个个单元。此表本身是一个小栈，自顶而下每个单元依次存放着现行层、小栈，自顶而下每个单元依次存放着现行层、直接外层直接外层直至最外层直至最外层(第第0层，即主程序层层，即主程序层)的每一层的最新活动记录的起始地址。例如，的每一层的最新活动记录的起始地址。例如，令过程令过程R的外层为的外层为Q，Q的外层为主程序的外层为主程序P，则，则过程过程R运行时的运行时的DISPLAY表内容如表表内容如表7-1所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院表7-1 DISPLAY表2R的现行活动记录的始址的现行活动记录的始址(SP的现行值的现行值)1Q的最新活动记录的始址的最新活动记录的始址0P的活动记录的始址的活动记录的始址 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 由于过程的层数可静态确定，因此由于过程的层数可静态确定，因此每个过程的每个过程的DISPLAY表的体积在编译时表的体积在编译时即可知道。为了便于组织存储区和简化即可知道。为了便于组织存储区和简化处理手续，我们把处理手续，我们把DISPLAY作为活动记作为活动记录的一部分置于形式单元的上端，如图录的一部分置于形式单元的上端，如图79所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 由由于于每每个个过过程程的的形形式式单单元元数数目目在在编编译译时时是是知知道道的的，因因此此DISPLAY的的相相对对地地址址d(相相对对于于活活动动记记录录的的起起点点)在在编编译译时时也也是是完完全全确确定定的的。被被调调用用过过程程为为了了建建立立自自己己的的DISPLAY，就就必必须须知知道道它它的的直直接接外外层层过过程程的的DISPLAY，这这意意味味着着必必须须把把直直接接外外层层的的DISPLAY地地址址作作为为连连接接数数据据之之一一(称称为为“全全局局DISPLAY地地址址”)传传送送给给被被调调用用过过程程。于于是是，此此时时的的连连接接数数 据据 包包 含含 老老 SP值值、返返 回回 地地 址址 和和 全全 局局DISPLAY地地址址这这三三项项内内容容。整整个个活活动动记记录录的的结构如图结构如图79所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图79 活动记录结构 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv存取链存取链(也称静态链也称静态链)方法。方法。存取链方法引入一个称为存取链的指存取链方法引入一个称为存取链的指针，该指针作为活动记录的一项指向直接针，该指针作为活动记录的一项指向直接外层的最新活动记录的地址，这就意味着外层的最新活动记录的地址，这就意味着在运行时栈中的每个数据区在运行时栈中的每个数据区(活动记录活动记录)之之间又拉出一条链，这个链称为存取链。注间又拉出一条链，这个链称为存取链。注意，运行时栈中数据区之间原先就存在一意，运行时栈中数据区之间原先就存在一条链，即每个活动记录中所保存的老条链，即每个活动记录中所保存的老SP值这一项，它是指向调用该过程值这一项，它是指向调用该过程(子过程子过程)的那个过程的那个过程(父过程父过程)的最新活动记录的起的最新活动记录的起点，由此向前形成了一条点，由此向前形成了一条SP链。链。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv为了区别于存取链，称为了区别于存取链，称为了区别于存取链，称为了区别于存取链，称SPSP链为控制链链为控制链链为控制链链为控制链(也称动态也称动态也称动态也称动态链链链链)，它记录了在运行中过程之间相互调用的关，它记录了在运行中过程之间相互调用的关，它记录了在运行中过程之间相互调用的关，它记录了在运行中过程之间相互调用的关系。注意，控制链是动态的，而存取链是静态的。系。注意，控制链是动态的，而存取链是静态的。系。注意，控制链是动态的，而存取链是静态的。系。注意，控制链是动态的，而存取链是静态的。控制链记录了当前时刻程序中各过程相互控制链记录了当前时刻程序中各过程相互控制链记录了当前时刻程序中各过程相互控制链记录了当前时刻程序中各过程相互调用调用调用调用的的的的情况；而存取链则始终记录着程序静态定义时该情况；而存取链则始终记录着程序静态定义时该情况；而存取链则始终记录着程序静态定义时该情况；而存取链则始终记录着程序静态定义时该过程所有的直接外层过程所有的直接外层过程所有的直接外层过程所有的直接外层(嵌套过程规定，内层过程嵌套过程规定，内层过程嵌套过程规定，内层过程嵌套过程规定，内层过程只允许调用其静态定义时的外层过程说明的变量只允许调用其静态定义时的外层过程说明的变量只允许调用其静态定义时的外层过程说明的变量只允许调用其静态定义时的外层过程说明的变量和数组和数组和数组和数组)；因此，存取链指出了一个过程的当前；因此，存取链指出了一个过程的当前；因此，存取链指出了一个过程的当前；因此，存取链指出了一个过程的当前活动记录指向其活动记录指向其活动记录指向其活动记录指向其直接定义的外层直接定义的外层直接定义的外层直接定义的外层过程直至最外层过程直至最外层过程直至最外层过程直至最外层的最新活动记录的起点。具有存取链的活动记录的最新活动记录的起点。具有存取链的活动记录的最新活动记录的起点。具有存取链的活动记录的最新活动记录的起点。具有存取链的活动记录结构如图结构如图结构如图结构如图710710所示。所示。所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图710 具有存取链的活动记录结构 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院假定过程的嵌套关系：假定过程的嵌套关系：编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv 程序中每个过程的静态结构程序中每个过程的静态结构(嵌套嵌套层次层次)是确定的，如嵌套深度为是确定的，如嵌套深度为2的过程的过程R引用了非局部量引用了非局部量a和和b，其嵌套深度分别，其嵌套深度分别为为0和和1。从。从R的活动记录开始，分别沿着的活动记录开始，分别沿着20=2和和21=1个存取链向前查找，则个存取链向前查找，则可找到包含这两个非局部量的活动记录。可找到包含这两个非局部量的活动记录。vv 上上述述过过程程P调调用用S以以及及S调调用用Q运运行行时栈的变化过程如图时栈的变化过程如图711(a)、(b)所示。所示。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院vv 由由图图711可可以以看看出出，指指针针SP总总是是指指向向当当前前正正在在执执行行过过程程的的活活动动记记录录起起点点，控控制制链链(老老SP)则则指指向向调调用用运运行行过过程程的的父父过过程程的的活活动动记记录录起起点点。因因此此，当当运运行行过过程程调调用用结结束束返返回回时时，利利用用控控制制链链老老SP值值可可以以得得到到调调用用前前原原父父过过程程活活动动记记录录的的起起点点。从从程程序序的的静静态态结结构构来来看看，P是是S和和Q的的静静态态直直接接外外层层，所所以以，S和和Q活活动动记记录录中中的的存存取取链链均均指指向向其其直直接接外外层层P的的活活动动记记录起点。录起点。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图711 过程调用时运行栈的变化 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院例例1:某某程程序序的的结结构构如如图图712所所示示，其其中中A、B、C为为 过过 程程名名，请请分分别别画画出出过过程程C调调用用A前前后后的的栈栈顶顶活动记录。活动记录。图712 例中的程序结构示意 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院解解：过过程程C调调用用A前前后后的的栈栈顶顶活活动动记记录录示示意意如如图图713所所示示。由由图图713可可知知，当当过过程程C执执行行时时，它它可可使使用用主主程程序序、A、B和和C过过程程所所说说明明的的变变量量，且且其其外外层层嵌嵌套套的的过过程程活活动动记记录录始始址址由由DISPLAY表表指指出出。当当C调调用用A而而使使过过程程A执执行行时时，我我们们看看到到此此时时的的DISPLAY表表已已变变为为两两项项，即即主主程程序序和和A过过程程自自身身；也也即即此此时时A只只可可使使用用主主程程序和序和A过程所说明的变量。过程所说明的变量。编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院图713 例1的运行栈与活动记录示意 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 例例2：在在下下面面的的PASCAL程程序序中中，已已经经第第二二次次(递递归归地地)进进入入了了f，请请给给出出第第三三次次进进入入f后的运行栈及后的运行栈及DISPLAY的示意图的示意图 PROGRAM test(input,output);VAR K:integer;FUNCTION f(n:integer):integer;BEGIN IF n=0 THEN f:=1 编译原理编译原理编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院解：解：第三次进入第三次进入f后的运行栈及后的运行栈及DISPLAY的的示意图如图示意图如图714所示。由于静态嵌套层所示。由于静态嵌套层次只有两层，故每一次递归调用产生的次只有两层，故每一次递归调用产生的DISPLAY表只有两项，一项是表只有两项，一项是test的的S