1、编译原理与技术编译原理与技术第第7章章 运行时环境运行时环境 编译原理与技术编译原理与技术2主要内容主要内容u程序运行的基本概念程序运行的基本概念 u参数传递机制参数传递机制 u静态运行时环境静态运行时环境u运行时存储空间的组织和管理运行时存储空间的组织和管理 u栈式运行时环境栈式运行时环境u堆式运行时环境堆式运行时环境 编译原理与技术编译原理与技术37.1 程序运行的基本概念程序运行的基本概念 u过程及其活动过程及其活动过程定义是把一个名字和若干语句联系起来过程定义是把一个名字和若干语句联系起来的一个声明。的一个声明。这个名字是过程名，而这些语句就是过程体。这个名字是过程名，而这些语句就是过
2、程体。返回值的过程通常称为函数，完整的程序也返回值的过程通常称为函数，完整的程序也可以看作一个过程。可以看作一个过程。在面向对象技术中，过程叫做方法或操作。在面向对象技术中，过程叫做方法或操作。本章把过程、函数、方法这样的程序单元统本章把过程、函数、方法这样的程序单元统称为过程。称为过程。编译原理与技术编译原理与技术47.1 程序运行的基本概念程序运行的基本概念u过程及其活动过程及其活动当过程名出现在程序中作为一个语句或表达当过程名出现在程序中作为一个语句或表达式使用时，就称这个过程在程序点被调用。式使用时，就称这个过程在程序点被调用。过程调用就是执行被调用过程的过程体。过程调用就是执行被调用
3、过程的过程体。出现在过程定义中的参数叫做形式参数（形出现在过程定义中的参数叫做形式参数（形参），在过程调用点取代形参的称为实在参参），在过程调用点取代形参的称为实在参数（实参）。数（实参）。编译原理与技术编译原理与技术57.1 程序运行的基本概念程序运行的基本概念program sort(input,output)var a:array 0.10 of integer;procedure readarray;var i:integer;begin for i:=1 to 9 do read(ai)end;function partition(y,z:integer):integervar i,
4、j,x,y:integer;begin.end;procrdure quicksort(m,n:integer);var i:integer;beginif(n m)then begin i=partition(m,n);quicksort(m,i 1);quicksort(i+1,n);end;end;begin a0:=9999;a10:=9999;readarray;quicksort(1,9);end;编译原理与技术编译原理与技术67.1 程序运行的基本概念程序运行的基本概念u过程的活动过程的活动过程的每次调用就引起过程体的一次执行，过程的每次调用就引起过程体的一次执行，称为过程的一次
5、活动。称为过程的一次活动。过程过程p的一个活动的生存期就是从过程体开始的一个活动的生存期就是从过程体开始执行到执行结束的时间，包括执行被执行到执行结束的时间，包括执行被P调用其调用其它所有过程所耗费的时间。它所有过程所耗费的时间。一般而言，术语一般而言，术语“生存期生存期”指的是程序执行指的是程序执行过程中若干步骤的一个连续序列。过程中若干步骤的一个连续序列。编译原理与技术编译原理与技术77.1 程序运行的基本概念程序运行的基本概念u过程的活动过程的活动任何两个过程的活动任何两个过程的活动p和和q只能存在下列关系：只能存在下列关系：l不重叠或者嵌套。过程的活动不重叠或者嵌套。过程的活动p和和q
6、不重叠，指的是它们的不重叠，指的是它们的执行时间（生存期）没有重叠；执行时间（生存期）没有重叠；l活动活动p嵌套在活动嵌套在活动q，指的是活动，指的是活动q的生存期包括了活动的生存期包括了活动p的的生存期。生存期。两个过程活动两个过程活动p和和q的关系表明，若程序的执行控制的关系表明，若程序的执行控制在退出在退出q之前进入了之前进入了p，则必须在退出，则必须在退出q之前退出之前退出p。如果同一个过程的两个不同活动如果同一个过程的两个不同活动p和和q重叠，即在该重叠，即在该过程的活动过程的活动p没有退出之前又重新另外一个活动没有退出之前又重新另外一个活动q，这样的过程称为递归过程。这样的过程称为
7、递归过程。同一个过程的不同调用产生不同的活动。同一个过程的不同调用产生不同的活动。编译原理与技术编译原理与技术87.1 程序运行的基本概念程序运行的基本概念u 活动记录活动记录过程的一次执行要用一块连续的存储区来管理过程的一次执行要用一块连续的存储区来管理需要的信息，这块存储区叫做活动记录或帧。需要的信息，这块存储区叫做活动记录或帧。返回值返回值实在参数实在参数（可选）控制链（可选）控制链（可选）访问链（可选）访问链机器状态机器状态局部数据局部数据临时数据临时数据返回值域：用于存放被调用过程返回给调用过程的值，根据不同的返回值域：用于存放被调用过程返回给调用过程的值，根据不同的参数传递机制，返
8、回值可以是数值或指向返回值地址的指针。参数传递机制，返回值可以是数值或指向返回值地址的指针。实参域：用于存放调用过程提供的实在参数，根据不同的形参和实参的传实参域：用于存放调用过程提供的实在参数，根据不同的形参和实参的传递机制，实参域可以是数值或指向实参地址的指针。递机制，实参域可以是数值或指向实参地址的指针。控制链域：指向调用者活动记录的指针，也称为动态链。控制链域：指向调用者活动记录的指针，也称为动态链。访问链域：对于像访问链域：对于像Pascal这样的语言，需要访问链来访问非局部数据；对这样的语言，需要访问链来访问非局部数据；对于于FROTRAN和和C则不需要，访问链又称静态链。则不需要
9、，访问链又称静态链。机器状态域：保存该过程调用前的机器状态信息，包括程序计数器（机器状态域：保存该过程调用前的机器状态信息，包括程序计数器（pc）的）的值以及控制从该过程返回时必须恢复的机器寄存器的值。值以及控制从该过程返回时必须恢复的机器寄存器的值。局部数据：存储用于该过程执行时的数据。局部数据：存储用于该过程执行时的数据。临时数据：保存该过程执行时临时的数据，如表达式的中间结果。临时数据：保存该过程执行时临时的数据，如表达式的中间结果。编译原理与技术编译原理与技术97.1 程序运行的基本概念程序运行的基本概念u调用序列和返回序列调用序列和返回序列调用序列，操作如调用序列，操作如 l活动记录
10、分配存储空间；活动记录分配存储空间；l计算并存储参数值；计算并存储参数值；l为调用分配并存储影响调用的存储器。为调用分配并存储影响调用的存储器。返回序列，操作如返回序列，操作如l把返回值放到调用者可以访问到的位置；把返回值放到调用者可以访问到的位置；l恢复机器状态；恢复机器状态；l调整寄存器；调整寄存器；l释放活动记录的存储。释放活动记录的存储。编译原理与技术编译原理与技术107.1 程序运行的基本概念程序运行的基本概念u活动树活动树 1.每个结点代表过程的一个活动记录（调用）；每个结点代表过程的一个活动记录（调用）；2.根结点代表主程序；根结点代表主程序；3.结点结点p是结点是结点q的父结点
11、，当且仅当控制流的父结点，当且仅当控制流从从p的活动进入的活动进入q的活动；的活动；4.在同一层中，结点在同一层中，结点p在结点在结点q的左边，当且的左边，当且仅当仅当p的生存期先于的生存期先于q的生存期。的生存期。编译原理与技术编译原理与技术117.1 程序运行的基本概念程序运行的基本概念例例7.1 假如执行图7.1的程序，我们可以构造出程序执行期间的所有过程的活动记录，表示整个程序运行的踪迹，如图7.3所示。树根是主程序sort的活动记录，它首先调用了readarray和quisksort(1,9)，按照程序的执行顺序，readarray在quisksort(1,9)之前，即readarr
12、ay的生存期先于在quisksort(1,9)，所以，结点ra在qs(1,9)的左边。qs(1,9)又调用了一次partition和两次quisksort，图中显示的结点分别是pt(1,9)，qs(1,3)和qs(5,9)。注意，qs(1,3)和qs(5,9)都是递归调用，它们在quisksort(1,9)结束之前结束。sortraqs(1,9)qs(1,3)pt(1,9)qs(5,9)qs(1,0)pt(1,3)qs(2,3)qs(5,5)pt(5,9)qs(7,9)qs(7,7)pt(7,9)qs(9,9)qs(2,1)pt(2,3)qs(3,3)编译原理与技术编译原理与技术127.1 程
13、序运行的基本概念程序运行的基本概念u名字的绑定和环境名字的绑定和环境 按照程序设计语言的语义，环境表示把一个名字映射到一个存按照程序设计语言的语义，环境表示把一个名字映射到一个存储位置的函数，状态表示把存储单元映射到所保存的值的函数储位置的函数，状态表示把存储单元映射到所保存的值的函数环境把名字映射到左值，状态把左值映射到右值。环境把名字映射到左值，状态把左值映射到右值。环境和状态是有区别的：赋值改变状态，但不改变环境。例如，环境和状态是有区别的：赋值改变状态，但不改变环境。例如，和假设存储单元和假设存储单元100关联的变量关联的变量pi记录的值是记录的值是0。在赋值语句。在赋值语句pi:=3
14、.14之后，同样是关联之后，同样是关联pi的存储单元的值就变成了的存储单元的值就变成了3.14。如果环境把名字如果环境把名字x映射到存储单元映射到存储单元s，就说，就说x被绑定到被绑定到s。术语存。术语存储单元是象征性的，因为如果储单元是象征性的，因为如果x不是一个基本类型，那么不是一个基本类型，那么x的存的存储单元储单元s可能是一组存储单元。可能是一组存储单元。编译原理与技术编译原理与技术137.2 参数传递机制参数传递机制u按值调用按值调用实参在调用时刻计算得到的表达式，其值就是过程执实参在调用时刻计算得到的表达式，其值就是过程执行时形参的值。可以如下实现：行时形参的值。可以如下实现：（1
15、）把形参当作所在过程的局部变量名看待，形参的存储单）把形参当作所在过程的局部变量名看待，形参的存储单元在该过程的活动记录中；元在该过程的活动记录中；（2）调用过程计算实参，并把值放入形参的存储单元中。）调用过程计算实参，并把值放入形参的存储单元中。它的最简单形式可以解释成值参数在过程的执行中作它的最简单形式可以解释成值参数在过程的执行中作为常数值，取代了过程体中所对应的形式参数。为常数值，取代了过程体中所对应的形式参数。C语语言和言和Java语言使用按值调用，它们也是语言使用按值调用，它们也是Pascal和和Ada的缺省参数传递方法。的缺省参数传递方法。编译原理与技术编译原理与技术147.2
16、参数传递机制参数传递机制u按值调用按值调用把形参当作所在过程的局部变把形参当作所在过程的局部变量名看待，形参的存储单元在量名看待，形参的存储单元在该过程的活动记录中；该过程的活动记录中；调用过程计算实参，并把值放入调用过程计算实参，并把值放入形参的存储单元中。形参的存储单元中。被调用过程的活动记录.形参1 形参2.调用序列在调用点计算实参1的值计算实参2的值把值分别送入形参图7.5 按值调用示意图按值调用的显著特征是，按值调用的显著特征是，对形参的任何运算都不会影响调用者的实参的值。对形参的任何运算都不会影响调用者的实参的值。编译原理与技术编译原理与技术157.2 参数传递机制参数传递机制u按
17、值调用按值调用下列程序下列程序inc1不会达到它期望的效果：不会达到它期望的效果：void inc1(int x)/*不正确的程序不正确的程序*/+x;return x;在在C语言中，需要传递地址来实现上述预想的效果：语言中，需要传递地址来实现上述预想的效果：void inc1(int*x)/*正确的程序正确的程序*/+(*x);return*x;当然，希望对变量当然，希望对变量y增值时，这个函数的调用形式为增值时，这个函数的调用形式为inc1(&y)，因为函数需要的是，因为函数需要的是y的地址而不是值。的地址而不是值。编译原理与技术编译原理与技术167.2 参数传递机制参数传递机制u引用调用
18、（传地址调用）引用调用（传地址调用）（1）1.如果实参是变量或具有左值的如果实参是变量或具有左值的表达式，则把该左值放入形参表达式，则把该左值放入形参的存储单元；的存储单元；2.如果实参是如果实参是3或或3a这样没有左这样没有左值的表达式，则首先把它的计算值存入到一个新的存储单元，值的表达式，则首先把它的计算值存入到一个新的存储单元，然后把这个地址传递给形参。然后把这个地址传递给形参。（2）在被调用过程的目标代码中，对形参的任何引用都是通）在被调用过程的目标代码中，对形参的任何引用都是通过形参存储的地址间接引用实参的。过形参存储的地址间接引用实参的。被调用过程的活动记录.形参1 形参2.调用序
19、列在调用点实参1的地址计算实参2的值并存入临时变量t把t的地址图7.6 引用调用示意图引用调用的显著特征是，对形参的任何运算都直接影响调用者的实参引用调用的显著特征是，对形参的任何运算都直接影响调用者的实参 编译原理与技术编译原理与技术177.2 参数传递机制参数传递机制u引用调用（传地址调用）引用调用（传地址调用）在在Pascal中，引用调用是通过在过程声明中使用关键字中，引用调用是通过在过程声明中使用关键字“var”实现的；实现的；C和和C+在过程声明中使用地址符号在过程声明中使用地址符号“&”实现参数的引用调实现参数的引用调用，例如：用，例如：void inc1(int&x)/*正确的程
20、序正确的程序*/+x;return x;这个函数可以直接调用，不必使用地址操作符：这个函数可以直接调用，不必使用地址操作符：inc1(y)就可就可以使变量以使变量y的值增加。的值增加。编译原理与技术编译原理与技术187.2 参数传递机制参数传递机制u值结果调用值结果调用(复写恢复复写恢复,复写入复写复写入复写)（1）调用过程把实参的值和实参的地址同时传给被调用过程；）调用过程把实参的值和实参的地址同时传给被调用过程；（2）被调用过程像按值调用那样使用传递给形参的值；）被调用过程像按值调用那样使用传递给形参的值；（3）把形参在被调用过程中最后的值拷贝到实参的存储单元内。）把形参在被调用过程中最后
21、的值拷贝到实参的存储单元内。被调用过程的活动记录.形参1 实参1的地址形参2调用序列在调用点计算实参1的值实参1的地址图7.7 值结果调用示意图 实参2的地址.计算实参2的值实参2的地址下列（按照C的语法格式）代码：void p(int x,int y)+x;+y;main()int a=1;p(a,a);return a;如果参数传递使用引用调用的方式，在调用p之后a的值是3；如果使用值结果调用的方式，a的值则是2。编译原理与技术编译原理与技术197.2 参数传递机制参数传递机制u换名调用换名调用实参直到在被调用的过程中作为形参实际使实参直到在被调用的过程中作为形参实际使用的时候才计算，所以
22、也叫延迟计算。用的时候才计算，所以也叫延迟计算。换名调用可以如下实现：换名调用可以如下实现：（1）在调用点，用被调用过程的体来替换调用者）在调用点，用被调用过程的体来替换调用者的调用，但是形参用对应的实参来替换。这种文的调用，但是形参用对应的实参来替换。这种文字替换方式成为宏展开或内联展开。字替换方式成为宏展开或内联展开。（2）在宏展开前，被调用过程的每个局部变量名）在宏展开前，被调用过程的每个局部变量名字被系统地重新命名可以区别的名字。字被系统地重新命名可以区别的名字。编译原理与技术编译原理与技术207.2 参数传递机制参数传递机制例如，例如，对于代码void p(int x)+x;如果出现
23、了p(ai)这样的调用，其效果就是+(ai)。所以，如果i在过程p内的变量x之前改变了值，结果将既不同于引用调用，也不同于值结果调用。编译原理与技术编译原理与技术217.2 参数传递机制参数传递机制例例7.2 考虑下列（C语法格式的）代码：int i;int a10;void p(int x)+i;+x;main()i=1;a1=1;a2=5;p(ai);采用按值调用的参数传递机制，调用过程p：尽管在过程p中改变了i的值为2，但a2的值不变；a1的值仍然为1。采用按值调用的参数传递机制，调用过程p不改变a1和a2的值。采用引用调用和值结果的参数传递机制，调用过程p的结果一样，都是把a1的值改变
24、为2，而没改变a2的值。（但是，如果采用值结果参数传递机制的另外一种实现，在复写出形参值的时候重新计算对应实参的地址，那么，调用过程p的结果把a2设置为2，保持a1的值不变。）采用换名参数传递机制，调用过程p的结果是把a2设置为6并保持a1的值不变。编译原理与技术编译原理与技术227.2 参数传递机制参数传递机制例例7.2 考虑下列（C语法格式的）代码：int i;int a10;void p(int x)+i;+x;main()i=1;a1=1;a2=5;p(ai);在这个程序中，由于i对于 p是非局部变量，无论哪种参数传递方式都在p中改变了值为2。但是，其它变量的结果随着参数传递机制的不同
25、而有差异。采用按值调用的参数传递机制，调用过程p：尽管在过程p中改变了i的值为2，但a2的值不变；语句+x的效果相当于+(a1)，调用没有把改变的值送回a1，即a1的值仍然为1。采用引用调用的参数传递机制，调用过程p时把参数a1的地址传递给p的活动记录中对应的形式单元x，执行p的结果是a1 值增加1，为2。采用值结果的参数传递机制，调用过程p：把a1的值（此时为1）传给p的活动记录中对应的形式单元x，再把a1的地址传给对应x的作为地址的形式单元addr；执行p的语句之后，x的值增加1为2，它作为x的最终值通过addr送入a1内，而a2的值保持不变。采用换名的参数传递机制，调用过程p把语句+x替
26、换成+(ai)，a2设置为6，但没改变a1的值。编译原理与技术编译原理与技术237.2 参数传递机制参数传递机制u换名调用与内联函数换名调用与内联函数l内联展开可以缩短程序的运行时间这是因为，过内联展开可以缩短程序的运行时间这是因为，过程活动的建立包括活动记录的空间分配、机器状程活动的建立包括活动记录的空间分配、机器状态的保存、调用数据的传递以及控制的转移等，态的保存、调用数据的传递以及控制的转移等，都需要占用机器的资源。若过程体较小，则过程都需要占用机器的资源。若过程体较小，则过程调用序列的代码可能会超过过程体本身的代码。调用序列的代码可能会超过过程体本身的代码。如果把过程体的代码内联展开到
27、调用者的代码中，如果把过程体的代码内联展开到调用者的代码中，即使程序的代码会稍长一些，程序的执行速度也即使程序的代码会稍长一些，程序的执行速度也会提高。会提高。l对于诸如对于诸如Java和和C#这样的面向对象语言，内联函这样的面向对象语言，内联函数还可以减少在程序运行时消息和函数体的动态数还可以减少在程序运行时消息和函数体的动态查找和联编。查找和联编。l内联函数产生了更大的代码块，使得代码优化技内联函数产生了更大的代码块，使得代码优化技术的应用更加方便。术的应用更加方便。编译原理与技术编译原理与技术247.2 参数传递机制参数传递机制u换名调用与内联函数换名调用与内联函数例如，下面的例如，下面
28、的C+函数读入一行字符串，逐个判断是函数读入一行字符串，逐个判断是否为数字字符：否为数字字符：isNumber(char ch)rerurn ch=0&ch=9?1:0;这个函数本身的代码很短，程序频繁调用该函数所花这个函数本身的代码很短，程序频繁调用该函数所花费的时间却很多，从而降低了程序的执行效率。费的时间却很多，从而降低了程序的执行效率。C+提供了内联函数的机制，把上面的函数可以改为：提供了内联函数的机制，把上面的函数可以改为：inline isNumber(char ch)这样就既保证了程序的可读性，又提高了程序的执行这样就既保证了程序的可读性，又提高了程序的执行效率。效率。编译原理与
29、技术编译原理与技术257.3 运行时存储空间的组织和管理运行时存储空间的组织和管理u局部数据的存放局部数据的存放编译对一个过程所声明的局部变量按照它们编译对一个过程所声明的局部变量按照它们的声明顺序，在活动记录的局部数据域中依的声明顺序，在活动记录的局部数据域中依次分配存储空间。次分配存储空间。这些局部数据的地址可以相对于一个特殊的这些局部数据的地址可以相对于一个特殊的位置，譬如活动记录的开始地址，用相对地位置，譬如活动记录的开始地址，用相对地址来表示。址来表示。相对地址（偏移）就是数据对象和这个基准相对地址（偏移）就是数据对象和这个基准位置的地址差。活动记录中其它域的访问也位置的地址差。活动
30、记录中其它域的访问也可以用相对于这个位置的相对地址来处理。可以用相对于这个位置的相对地址来处理。编译原理与技术编译原理与技术267.3 运行时存储空间的组织和管理运行时存储空间的组织和管理u运行时存储空间的划分代码运行时存储空间的划分代码为了使目标代码能够运行，编译程序必须从系统中申请一块存为了使目标代码能够运行，编译程序必须从系统中申请一块存储区域，分配给目标代码。储区域，分配给目标代码。典型的计算机存储包括快速运算域访问的寄存器区域和比较慢典型的计算机存储包括快速运算域访问的寄存器区域和比较慢的随机访问存储（的随机访问存储（RAM），而），而RAM又可以划分成为代码区和又可以划分成为代码区
31、和数据区。数据区。对大多数需要编译的语言，程序运行对大多数需要编译的语言，程序运行 的时候不能改变程序的存储区域，而且，的时候不能改变程序的存储区域，而且，代码区域和数据区域在概念上被认为是代码区域和数据区域在概念上被认为是 分离的。分离的。因为代码区域在运行前就已经确定，所因为代码区域在运行前就已经确定，所有的代码地址在编译时都可以计算出来。有的代码地址在编译时都可以计算出来。过程1的代码 过程2的代码 .过程n的代码 过程1的入口点 过程2的入口点 过程n的入口点 .图7.8 代码区域编译原理与技术编译原理与技术277.3 运行时存储空间的组织和管理运行时存储空间的组织和管理u运行时存储空
32、间的划分整个程序运行时存储空间的划分整个程序静态数据可以象代码一样在编译时刻分配地址。静态数据可以象代码一样在编译时刻分配地址。动态数据的典型组织包括把存储空间划分为栈式数据区域和堆动态数据的典型组织包括把存储空间划分为栈式数据区域和堆式数据区域。式数据区域。存储分配的重要单元是过程的活动记录。根据语言特性，活动存储分配的重要单元是过程的活动记录。根据语言特性，活动记录可以分配在静态区域（如记录可以分配在静态区域（如FORTRAN）、栈式数据区（）、栈式数据区（C和和Pascal）或者堆式数据区（）或者堆式数据区（Lisp语言）语言）。图7.9 运行时存储空间的划分 代码区域 全局/静态数据区
33、域 栈式数据区域 堆式数据区域编译原理与技术编译原理与技术287.3 运行时存储空间的组织和管理运行时存储空间的组织和管理u存储分配要考虑的问题存储分配要考虑的问题过程能否递归；过程能否递归；当控制从过程的活动返回时，是否需要保留局部变量当控制从过程的活动返回时，是否需要保留局部变量的值；的值；过程能否访问非局部变量，如何有效地访问；过程能否访问非局部变量，如何有效地访问；过程调用时形参和实参的传递方式；过程调用时形参和实参的传递方式；过程能否作为参数传递和结果返回；过程能否作为参数传递和结果返回；存储区域能否在程序控制下动态地分配；存储区域能否在程序控制下动态地分配；存储区域能否在程序控制下
34、显示地回收。存储区域能否在程序控制下显示地回收。编译原理与技术编译原理与技术297.3 运行时存储空间的组织和管理运行时存储空间的组织和管理3种常见的存储分配策略种常见的存储分配策略静态存储分配、栈式动态存储分配和堆式动态分配存储静态存储分配、栈式动态存储分配和堆式动态分配存储静态存储分配在程序编译的时后就把数据对象分配在固定的存储单元，且在运行时始静态存储分配在程序编译的时后就把数据对象分配在固定的存储单元，且在运行时始终保持不变。语言要求不含递归过程，不允许体积改变的数据对象和待定性质的名字。终保持不变。语言要求不含递归过程，不允许体积改变的数据对象和待定性质的名字。FORTRAN语言的编
35、译程序可以采用静态存储分配策略。语言的编译程序可以采用静态存储分配策略。栈式动态存储分配栈式动态存储分配 存储器作为一个栈来管理，每当一个过程被激活和调用，程序就存储器作为一个栈来管理，每当一个过程被激活和调用，程序就动态地为这个过程在栈的顶部分配存储区域，一旦过程执行结束，就释放所占用的存动态地为这个过程在栈的顶部分配存储区域，一旦过程执行结束，就释放所占用的存储空间。这种策略适合那些允许过程嵌套的语言，如储空间。这种策略适合那些允许过程嵌套的语言，如Pascal、Ada等。等。堆式动态存储分配则在程序运行时把存储器作为一个堆来管理，以便程序管理存储的申请和回收。对于允许递归过程的Pasca
36、l、Ada、C、C#和Java等语言，编译无法预先确定哪些递归过程在运行时被激活，也不能确定它们的递归深度，而对每个过程都需要为其活动记录分配新的存储空间。此外，程序员在程序中动态地申请和释放存储空间，存储空间申请和释放的顺序随意，并不遵守先申请先释放的队列原则或后先请后释放栈的原则。因此，这些语言还需要采用更复杂的动态堆式存储分配策略。编译原理与技术编译原理与技术307.4 静态运行时环境静态运行时环境 FORTRAN是这种分配策略的典型语言。是这种分配策略的典型语言。在这种运行时环境中，不仅全局变量、而是所有变量都可以在编译时在这种运行时环境中，不仅全局变量、而是所有变量都可以在编译时分配
37、存储。此外，每个过程只有一个活动记录，它可以在程序运行前分配存储。此外，每个过程只有一个活动记录，它可以在程序运行前静态地分配存储。所有变量，无论是全局的还是局部的，都可以通过静态地分配存储。所有变量，无论是全局的还是局部的，都可以通过固定的地址访问。固定的地址访问。主程序的代码过程1的代码.过程n的代码全局数据区域主程序的活动记录过程1的活动记录.过程n的活动记录代码区域数据区域图7.10 静态存储分配结构在这种运行时环境中，活动记录的信息簿记工作和调用序列十分简单。调用过程的时候，就计算每个实参并不它们放到被调用过程活动记录中相应的形参的位置，然后保留调用者的返回地址，生成一个到被调用过程
38、起始的跳转指令。返回时就需要一个简单的到返回地址的跳转指令。编译原理与技术编译原理与技术317.4 静态运行时环境静态运行时环境 例例7.3 图7.11是一个FORTRAN程序，它计算并打印一个表中实数的平均值。它只有一个主程序和一个子程序QUADMEAN，唯一一个全局变量是分别在主程序和QUADMEAN声明的MAXSIZE，程序还调用了库函数SORT。PROGRAM TESTCOMMON MAXSIZEINTEGER MAXSIZEREAL TABLE(10),TEMPMAXSIZE=10READ*,TABLE(1),TABLE(2),TABLE(3)CALL QUADMEAN(TABLE,
39、3,TEMP)PRINT*,TEMPEND SUBROUTIN QUADMEAN(A,SIZE,QMEAN)COMMON MAXSIZE INTEGER MAXSIZE,SIZE REAL A(SIZE),QMEAN,TEMP INTEGER K TEMP=0.0 IF(SIZE.GT.MAXSIZE).OR.(SIZE.LT.1)GOTO 99 DO 10 K=1,SIZE10TEMP=TEMP+A(K)*A(K)99 CONTINUE QMEAN=SORT(TEMP/SIZE)RETURN END编译原理与技术编译原理与技术327.4 静态运行时环境静态运行时环境u这个程序的运行时环境可以
40、如图这个程序的运行时环境可以如图7.12所示。所示。其中箭头连线表示过程其中箭头连线表示过程QUADMEAN的三的三个参数个参数A、SIZE和和QMEAN的值在调用过的值在调用过程中从主程序拷贝得到，这是由于程中从主程序拷贝得到，这是由于FORTRAN语言的参数传递是隐含的存储语言的参数传递是隐含的存储引用，所以把它们的地址赋值到被调用的引用，所以把它们的地址赋值到被调用的QUADMEAN中。中。uQUADMEAN活动记录中的临时变量用来活动记录中的临时变量用来存放计算存放计算TEMP+A(K)*A(K)或者或者TEMP/SIZE的值。如果没有足够的寄存器的值。如果没有足够的寄存器来存放临时值
41、，或者有一个调用要求保留来存放临时值，或者有一个调用要求保留这个值，那么，在完成计算之前要把该值这个值，那么，在完成计算之前要把该值存储在活动记录中。存储在活动记录中。u编译程序根据目标机器的体系结构（如寄编译程序根据目标机器的体系结构（如寄存器的个数和使用规则）可以确定运行时存器的个数和使用规则）可以确定运行时是否需要存放临时变量的存储，并安排大是否需要存放临时变量的存储，并安排大小合适的临时存储单元。小合适的临时存储单元。全局数据主程序的活动记录QUADMEAN的活动记录MAXSIZETEMP3ASIZEQMEAN返回地址TEMPK临时变量TABLE(1)TABLE(2)TABLE(10)
42、编译原理与技术编译原理与技术337.5 栈式运行时环境栈式运行时环境 如果一个语言允许过程递归调用，而且每次如果一个语言允许过程递归调用，而且每次调用都重新分配局部变量，活动记录就不可调用都重新分配局部变量，活动记录就不可能静态地分配。能静态地分配。这样，活动记录可以基于栈结构进行分配，这样，活动记录可以基于栈结构进行分配，每一个新的过程调用都需要把一个新的活动每一个新的过程调用都需要把一个新的活动记录放在栈顶，在过程执行退出以后就再回记录放在栈顶，在过程执行退出以后就再回收这个活动记录的存储单元。收这个活动记录的存储单元。活动记录栈（又叫运行栈或调用栈）在程序活动记录栈（又叫运行栈或调用栈）
43、在程序的执行过程中随着调用链增长和缩减。的执行过程中随着调用链增长和缩减。又分成无过程嵌套的栈式运行时环境又分成无过程嵌套的栈式运行时环境 和有过和有过程嵌套的栈式运行时环境。程嵌套的栈式运行时环境。编译原理与技术编译原理与技术347.5.1 无过程嵌套的栈式运行时环境无过程嵌套的栈式运行时环境在这类语言中，例如在这类语言中，例如C，过程都是全局过程，不允许，过程都是全局过程，不允许嵌套，但是允许递归调用。这样的运行时环境需要两嵌套，但是允许递归调用。这样的运行时环境需要两类信息：类信息：维护指向当前活动记录的指针以便访问局部变量维护指向当前活动记录的指针以便访问局部变量;记录直接调用者的位置
44、或大小以便当前调用结束后恢复调用记录直接调用者的位置或大小以便当前调用结束后恢复调用者的活动记录。者的活动记录。指向当前活动记录的指针通常称为帧指针指向当前活动记录的指针通常称为帧指针sp，保存在，保存在一个寄存器中（就叫一个寄存器中（就叫sp）。）。前一个活动记录通常用一个存放在当前活动记录中称前一个活动记录通常用一个存放在当前活动记录中称为控制链的指针访问。这个指针又叫动态链，因为它为控制链的指针访问。这个指针又叫动态链，因为它是在程序运行时指向调用程序的活动记录；又称为老是在程序运行时指向调用程序的活动记录；又称为老的帧指针，因为它代表的了的帧指针，因为它代表的了sp的前一个值。的前一个
45、值。编译原理与技术编译原理与技术357.5.1 无过程嵌套的栈式运行时环境无过程嵌套的栈式运行时环境例例7.3 一个计算两个非负数最大公因子的欧一个计算两个非负数最大公因子的欧几理德算法的递归程序几理德算法的递归程序gcd，代码如图，代码如图7.13(a)。假设输入了15和10，main开始调用gcd(15,10)，它的第二次调用gcd(10,5)，接着是第三次调用gcd(5,0)并且返回5。第三次调用的运行时环境如图7.13(b)所示。每次调用gcd都在栈顶新增一个大小一样的活动记录，而且在这个活动记录中都有控制链指向调用它的前一个活动记录。帧指针fp指向当前活动记录的控制链，这样，在下一次
46、调用时（比如第4次调用），这个fp就成为下一个活动记录的控制链的目的地址。每次调用gcd完成过程体的动作之后，每个gcd的活动记录都从栈顶移出。当执行main中打印语句pringf的时候，存储器中只剩下main的活动记录和全局/静态数据。#include int m,n;int gcd(int u,v)if(v=0)return u;else return gcd(v,u%v);main()scanf(“%d%d”,&m,&n);printf(“%dn”,gcd(m,n);return 编译原理与技术编译原理与技术367.5.1 无过程嵌套的栈式运行时环境无过程嵌套的栈式运行时环境 m:15
47、n:10 u:15 v:10控制链 返回地址 u:10 v:5控制链 返回地址 u:5 v:0控制链 返回地址 自由空间全局/静态区域main的活动记录第1次调用gcd时的活动记录第2次调用gcd时的活动记录第3次调用gcd时的活动记录sp假设输入了假设输入了15和和10，main开始调用开始调用gcd(15,10)，它的第二次调用，它的第二次调用gcd(10,5)，接着是第三次调用，接着是第三次调用gcd(5,0)并且返并且返回回5。第三次调用的运行时环境如图。第三次调用的运行时环境如图7.13(b)所示。每次调用所示。每次调用gcd都在栈顶新都在栈顶新增一个大小一样的活动记录，而且在这增一
48、个大小一样的活动记录，而且在这个活动记录中都有控制链指向调用它的个活动记录中都有控制链指向调用它的前一个活动记录。帧指针前一个活动记录。帧指针fp指向当前活指向当前活动记录的控制链，这样，在下一次调用动记录的控制链，这样，在下一次调用时（比如第时（比如第4次调用），这个次调用），这个fp就成为下就成为下一个活动记录的控制链的目的地址。一个活动记录的控制链的目的地址。每次调用每次调用gcd完成过程体的动作之后，每完成过程体的动作之后，每个个gcd的活动记录都从栈顶移出。的活动记录都从栈顶移出。当执行当执行main中打印语句中打印语句pringf的时候，的时候，存储器中只剩下存储器中只剩下main
49、的活动记录和全局的活动记录和全局/静态数据。静态数据。fp编译原理与技术编译原理与技术377.5.1 无过程嵌套的栈式运行时环境无过程嵌套的栈式运行时环境u名字的访问名字的访问在栈式环境中，参数和局部变量不能通过固在栈式环境中，参数和局部变量不能通过固定的地址访问，而必须依据它们和当前活动定的地址访问，而必须依据它们和当前活动记录的位差来定位。记录的位差来定位。在大多数语言中，过程声明在编译时确定并在大多数语言中，过程声明在编译时确定并且分配给每个局部声明的存储大小，按照数且分配给每个局部声明的存储大小，按照数据类型是固定的，所以，每个局部声明的位据类型是固定的，所以，每个局部声明的位差可以由
50、编译程序计算出来。差可以由编译程序计算出来。编译原理与技术编译原理与技术387.5.1 无过程嵌套的栈式运行时环境无过程嵌套的栈式运行时环境例例7.4 考虑下列C程序void f(int x,char c)int a10;double y;调用过程f的活动记录如图所示。假设整型占2个字节，地址用4个字节，字符型用1个字节，双精度浮点型占8个字节，栈向下增长，那么，就可以在编译时刻得到每个局部变量的位移值。这样，假访问ai就需要按照下列公式计算地址：(242i)(fp)。根据i的位置和机器的体系结构，这样的存储访问可能只需一条机器指令。x c 控制链 返回地址 a9 a8 .a0 y x的偏移量
