China-pub.Com 第7章运行时环境 271 下载 就是QUADMEAN的活动记录结尾分配的未命名的地址。这个地址是一个在算术表达式计算中用 来储存临时变量值的“凑合的”地址。在QUADMEAN中可能需要两个运算。一个是循环中的 TEMP+A(K)A(K)的计算，另一个是当参数在调用SQRT时的TEMP/SIzE的计算。我们早己 谈过需要为参数值分配空间（尽管在对库函数的调用中实际上是有差别的）。循环计算中也需要 临时变量存储地址的原因在于每个算术运算必须在一个步骤中，所以就计算A(K)*A(K)并在 下一步中添加EMP的值。如果没有足够的寄存器来放置这个临时变量值，或如果有一个调用 要求保存这个值，那么在完成计算之前应先将值存储在活动记录中。编译程序可以总是先预测 出在执行中它是否必要，然后再为分配临时变量的地址的恰当数量（以及大小）作出安排。 7.3基于栈的运行时环境 在允许递归调用以及每一个调用中都重新分配局部变量的语言中，不能静态地分配活动记 录。相反地，必须以一个基于栈的风格来分配活动记录，即当进行一个新的过程调用（活动记 录的压入(pus)时，每个新的活动记录都分配在栈的顶部，而当调用退出时则再次解除分配 (活动记录的弹出(pop)。活动记录的栈(stack of activation record)(也指运行时栈(runtime stack) 或调用栈(call stack)就随着程序执行时发生的调用链生长或缩小。每个过程每次在调用栈上可 以有若干个不同的话动记录，每个都代表了一个不同的调用。这样的环境要求的簿记和变量访 问的技术比完全静态环境要复杂许多。特别地，活动记录中必须有额外的簿记信息，而且调用 序列还包括设置和保存这个额外信息所需的步骤。基于栈的环境的正确性和所需簿记信息的数 量在很大程度上依赖于被编译的语言的特性。在本节中为了提高难度复杂性，我们将考虑基于 栈的环境的组织，它是由所涉及到的语言特性区分的。 7.3.1没有局部过程的基于栈的环境 在一个所有过程都是全局的语言（例如C语言）中，基于栈的环境有两个要求：指向当前活 动记录的指针的维护允许访问局部变量，以及位置记录或紧前面的活动记录（调用程序的活动 记录)允许在当前调用结束时读有活动记录（日金掉当前活动）。指向当前活动的指针通常称为 框架指针(ame pointer)或(p,且通常保存在寄存器中（通常也称作p)。作为一个指向先前 动记录的指针，有关先前活动的信息一般是放在当前活动中，并被认为是控制链(control link) 或动态链(dynamic link)(之所以称之为动态的，是因为在执行时它指向调用程序的活动记录)。 有时将这个指针称为旧p(old fp),这是因为它代表了p的先前值。通常，这个指针被放在栈 中参数区域和局部变量区域之间的某处，并且指向先前活动记录控制链。此外，还有一个栈 指针((stack pointer)或sp,它通常指向调用栈上的最后位置（它有时称作栈顶部((top of stack)指针， 或tos)。 现在考虑几个例子。 例7.2利用Euclid3算法的简单递归实现，计算两个非负整数的最大公约数，它的代码(C语言) 在程序清单7-2中。 程序清单7-2例7-2的C代码 sinclude <stdio.h> int x,y:
就是Q U A D M E A N的活动记录结尾分配的未命名的地址。这个地址是一个在算术表达式计算中用 来储存临时变量值的“凑合的”地址。在 Q U A D M E A N中可能需要两个运算。一个是循环中的 T E M P + A ( K ) * A ( K )的计算，另一个是当参数在调用 S Q R T时的T E M P / S I Z E的计算。我们早已 谈过需要为参数值分配空间 (尽管在对库函数的调用中实际上是有差别的 )。循环计算中也需要 临时变量存储地址的原因在于每个算术运算必须在一个步骤中，所以就计算 A ( K ) * A ( K )并在 下一步中添加T E M P的值。如果没有足够的寄存器来放置这个临时变量值，或如果有一个调用 要求保存这个值，那么在完成计算之前应先将值存储在活动记录中。编译程序可以总是先预测 出在执行中它是否必要，然后再为分配临时变量的地址的恰当数量 (以及大小)作出安排。 7.3 基于栈的运行时环境 在允许递归调用以及每一个调用中都重新分配局部变量的语言中，不能静态地分配活动记 录。相反地，必须以一个基于栈的风格来分配活动记录，即当进行一个新的过程调用 (活动记 录的压入( p u s h ) )时，每个新的活动记录都分配在栈的顶部，而当调用退出时则再次解除分配 (活动记录的弹出( p o p ) )。活动记录的栈(stack of activation record)(也指运行时栈(runtime stack) 或调用栈(call stack))就随着程序执行时发生的调用链生长或缩小。每个过程每次在调用栈上可 以有若干个不同的活动记录，每个都代表了一个不同的调用。这样的环境要求的簿记和变量访 问的技术比完全静态环境要复杂许多。特别地，活动记录中必须有额外的簿记信息，而且调用 序列还包括设置和保存这个额外信息所需的步骤。基于栈的环境的正确性和所需簿记信息的数 量在很大程度上依赖于被编译的语言的特性。在本节中为了提高难度复杂性，我们将考虑基于 栈的环境的组织，它是由所涉及到的语言特性区分的。 7.3.1 没有局部过程的基于栈的环境 在一个所有过程都是全局的语言 (例如C语言)中，基于栈的环境有两个要求：指向当前活 动记录的指针的维护允许访问局部变量，以及位置记录或紧前面的活动记录 (调用程序的活动 记录)允许在当前调用结束时恢复活动记录 (且舍掉当前活动 )。指向当前活动的指针通常称为 框架指针(frame pointer) 或( f p )，且通常保存在寄存器中(通常也称作f p )。作为一个指向先前活 动记录的指针，有关先前活动的信息一般是放在当前活动中，并被认为是控制链 (control link) 或动态链(dynamic link) (之所以称之为动态的，是因为在执行时它指向调用程序的活动记录 )。 有时将这个指针称为旧 f p (old fp)，这是因为它代表了 f p的先前值。通常，这个指针被放在栈 中参数区域和局部变量区域之间的某处，并且指向先前活动记录控制链。此外，还有一个栈 指针(stack pointer)或s p，它通常指向调用栈上的最后位置(它有时称作栈顶部(top of stack)指针， 或t o s )。 现在考虑几个例子。 例7.2 利用E u c l i d算法的简单递归实现，计算两个非负整数的最大公约数，它的代码 ( C语言) 在程序清单7 - 2中。 程序清单7-2 例7 - 2的C代码 第 7章 运行时环境 2 7 1 下载
272 翁译原理及实践 China-pub.com 下载 int ged(int u,int v) main() return 0: 假设用户在该程序中输入了值15和10，那么main就初始化调用gcd(15,10)。这个调用 导致了另一个递归调用gcd(10,5),(因为15%10=5)，而这又引起了第3个调用 gcd(5,0)(因为10%5=0， 它将返回值5。在第 3个调用中，运行时环境如图7-2所示。请读者 8 全局/静态区城 注意指向每个调用的gc是如何向栈的顶部添 加新的大小完全相同的活动记录，并且在每 min的话动记录 新活动记录中，控制链指向先前活动记录的控 制链。还请大家注意，指向当前活动记录的 控制链，因此在下一个调用中当前的印就会变 成下一个活动记录的控制链了。 调用最后 个gcd的之后，将按顺序从栈中 控制链 鲜济用 别去每个活动，这样当在main中执行printf 返回地址 语句时，只在环境中保留了main和全局/静态区 域的活动记录（我们已将main的记录显示为空 在实际中，它应包含将控制传回到操作系统的 返因地计 信息)。 最后，应指出在调用gcd时调用程序不 钱生长方向 需要为自变量值安排空间（与图71中的 FORTRAN7?7环境中的常量3不同)，这是因为C 图7-2例7.2的基于栈的环境 语言使用值参数。7.5节将详细探讨这一点。 例7.3考虑程序清单7-3中的C代码。这个代码包括将用来进一步描述本节相关内容的变量， 但是它的基本操作如下所示。从main来的第1个调用是到g(2)的（这是因为x在这一点上有值 2)。在这个调用中，m变成了2，而y则变成了1。接着g调用￡(1)，而￡也相应地调用g(1)。 在这个到g的调用中，m变成了1，而y则变成了0，所以再也没有别的调用了。该点（在对g的第 二次调用期间)上的运行时环境显示在图7-3a中。 程序清单7-3例7.3的C程序 int x=21 void g(int):/*prototype *
假设用户在该程序中输入了值 1 5和1 0，那么m a i n就初始化调用g c d ( 1 5 , 1 0 )。这个调用 导致了另一个递归调用 g c d ( 1 0 , 5 )，(因为 15 % 10 = 5) ，而这又引起了第 3个调用 g c d ( 5 , 0 )(因为1 0 % 5 = 0 )，它将返回值5。在第 3个调用中，运行时环境如图 7 - 2所示。请读者 注意指向每个调用的 g c d是如何向栈的顶部添 加新的大小完全相同的活动记录，并且在每个 新活动记录中，控制链指向先前活动记录的控 制链。还请大家注意， f p指向当前活动记录的 控制链，因此在下一个调用中当前的 f p就会变 成下一个活动记录的控制链了。 调用最后一个g c d的之后，将按顺序从栈中 删去每个活动，这样当在 m a i n中执行p r i n t f 语句时，只在环境中保留了m a i n和全局/静态区 域的活动记录(我们已将m a i n的记录显示为空。 在实际中，它应包含将控制传回到操作系统的 信息)。 最后，应指出在调用 g c d 时调用程序不 需 要为自变量值安排空间（与图 7 - 1 中的 F O RT R A N 7 7环境中的常量3不同），这是因为C 语言使用值参数。7 . 5节将详细探讨这一点。 例7.3 考虑程序清单7 - 3中的C代码。这个代码包括将用来进一步描述本节相关内容的变量， 但是它的基本操作如下所示。从 m a i n来的第1个调用是到g ( 2 )的(这是因为x在这一点上有值 2 )。在这个调用中， m变成了2，而y则变成了1。接着g调用f ( 1 )，而f也相应地调用 g ( 1 )。 在这个到g的调用中，m变成了1，而y则变成了0，所以再也没有别的调用了。该点 (在对g的第 二次调用期间)上的运行时环境显示在图7-3a 中。 程序清单7-3 例7 . 3的C程序 2 7 2 编译原理及实践 下载 图7-2 例7 . 2的基于栈的环境 控制链 返回地址 栈生长方向 全局／静态区域 main 的活动记录 第一次调用 g c d 时的活动记录 第二次调用 g c d 时的活动记录 第三次调用 g c d 时的活动记录 控制链 返回地址 控制链 返回地址 自由空间
China-pub.com 第7章运行时环境 273 下载 g(n) void g(int m) gly): main() 【g(x), return 0; 现在对g和￡的调用退出(E在返回之前它的静态局部变量x减)，它们的活动记录从栈中弹 出，且控制返回到紧随在第1次对g的调用的E的调用之后的点。现在g给外部变量x减1，并进 行另一次调用g(1),将m设为2将y设为1，这样就得到了图7-3b中的运行时环境。在此之后再 也没有调用了，从栈中就会弹出剩余的活动记录，程序退出。 (from)1 全局/静态区 受在om:0 全局/静态区 main的话动记录 main的话动记录 m:2 调用g时的活动 调用g时的活动 记录 返回地址 记录 y:1 y:1 n:1 m:1 调用！时的活动 控制 记录 返国地址 返地址 动 y:0 m:1 用g时的活动 y:0 记录 自由 图7-3程序清单73中程序的运行时环境 )在第2次对g的调用时，程序清单73中程序的运行时环境 b)在第3次对g的调用时，程序清单一3中程序的运行时环境 请注意，在图7-3中，对g的第3次调用的活动记录占据着（并覆盖）E的活动记录先前占着 的存储器区域。大家还应注意到：由于￡中的静态变量x必须坚持通过所有对E的调用，所以不 可在的活动记录中分配。因此，尽管不是全局变量，也必须在全局静态区域中与外部变量x
现在对g和f的调用退出(f在返回之前它的静态局部变量 x减1 )，它们的活动记录从栈中弹 出，且控制返回到紧随在第 1次对g的调用的f的调用之后的点。现在 g给外部变量x减1，并进 行另一次调用g ( 1 )，将m设为2将y设为1，这样就得到了图7-3b 中的运行时环境。在此之后再 也没有调用了，从栈中就会弹出剩余的活动记录，程序退出。 图7-3 程序清单7 - 3中程序的运行时环境 a) 在第2次对g 的调用时，程序清单7 - 3中程序的运行时环境 b) 在第3次对g 的调用时，程序清单7 - 3中程序的运行时环境 请注意，在图7-3b 中，对g的第3次调用的活动记录占据着 (并覆盖)f的活动记录先前占着 的存储器区域。大家还应注意到：由于 f中的静态变量x必须坚持通过所有对f的调用，所以不 可在f的活动记录中分配。因此，尽管不是全局变量，也必须在全局 /静态区域中与外部变量 x 第 7章 运行时环境 2 7 3 下载 控制链 返回地址 全局／静态区 main 的活动记录 调用 g 时的活动 记录 全局／静态区 main 的活动记录 调用 g 时的活动 记录 调用 g 时的活动 记录 调用 f 时的活动 记录 调用 g时的活动 记录 控制链 返回地址 控制链 返回地址 控制链 返回地址 控制链 返回地址 y:0 自由空间 自由空间 a) b)
274翁济原理及实践 China-pub.com 下载 在一起分配。因为符号表会总能区分它与外部的x,并在程序每一个点上判定访问的正确变量， 所以它们不会有什么混淆。 活动树(activation tree)是分析程序中复杂调用 main() main() 结构的有用工具，每个活动记录（或调用）都成为该 树的一个节点，而每个节点的子孙则代表了与该节 gcd(15,10) 点相对应的调用时进行的调用。例如，程序清单7 gcd(10,5) 2中程序的活动树是线性的，在图7-4a中描述（对 goa(5,01 g(2) 于输入15和10而言)，而程序清单7-3中程序的活动 树在图7-4b中描述。请注意，图7-2和图7-3中显 a b 示的环境表示了在调用时由活动树的每个叶子代表 的调用。一般而言，在特定调用开头的活动记录栈 图7-4程序清单7-2和程序清单7-3中 与活动树的相应节点到根节点的通路有一个结构等 程序的活动树 价。 )对名称的访问在基于栈的环境中，再也不能像在完全静态环境中那样用固定的地址访 问参数和局部变量。而它们由当前框架指针的偏移量发现。在大多数的语言中，每个局部声明 的偏移量仍是可由编译程序静态地计算出来，因为过程的声明在编译时是固定的，而且为每个 声明分配的存储器大小也根据其数据类型而固定。 考虑程序清单7-3中C程序的过程g(参见图7-3中画出的运行时环境)。g的每个活动记录 的格式完全相同，而参数m和局部变量y也总是位于活动记录中完全相同的相对位置。我们 把这个距离称作moE￡set和yoffset。然后，在对g的任何调用期间，都有下面的局部环 境图： 控制鞋 mOffset. Ep 返回地址 y m和y都可根据它们从的固定偏移进行访问。例如，具体地假设运行时栈从存储器地址的 高端向低端生长，整型变量的存储要求两个字节，地址要求4个字节。若活动记录的组织如上 所画，就有moffset=+4和yoffset=-6,且对m和y的引用写成机器代码（假设是标准的汇 编器约定)为4(Ep)和-6(EP)。 局部数组和结构与简单变量相比分配和计算地址并不更加困难，如以下示例所示。 例7.4考虑C过程 double yi 对￡调用的活动记录显示为：
在一起分配。因为符号表会总能区分它与外部的 x，并在程序每一个点上判定访问的正确变量， 所以它们不会有什么混淆。 活动树(activation tree) 是分析程序中复杂调用 结构的有用工具，每个活动记录 (或调用)都成为该 树的一个节点，而每个节点的子孙则代表了与该节 点相对应的调用时进行的调用。例如，程序清单 7 - 2中程序的活动树是线性的，在图 7-4a 中描述(对 于输入1 5和1 0而言)，而程序清单7 - 3中程序的活动 树在图7-4b 中描述。请注意，图 7 - 2和图7 - 3中显 示的环境表示了在调用时由活动树的每个叶子代表 的调用。一般而言，在特定调用开头的活动记录栈 与活动树的相应节点到根节点的通路有一个结构等 价。 1) 对名称的访问 在基于栈的环境中，再也不能像在完全静态环境中那样用固定的地址访 问参数和局部变量。而它们由当前框架指针的偏移量发现。在大多数的语言中，每个局部声明 的偏移量仍是可由编译程序静态地计算出来，因为过程的声明在编译时是固定的，而且为每个 声明分配的存储器大小也根据其数据类型而固定。 考虑程序清单 7 - 3中C程序的过程 g (参见图7 - 3中画出的运行时环境 )。g的每个活动记录 的格式完全相同，而参数 m和局部变量 y也总是位于活动记录中完全相同的相对位置。我们 把这个距离称作 m O f f s e t和y O f f s e t。然后，在对 g的任何调用期间，都有下面的局部环 境图： m和y都可根据它们从f p的固定偏移进行访问。例如，具体地假设运行时栈从存储器地址的 高端向低端生长，整型变量的存储要求两个字节，地址要求 4个字节。若活动记录的组织如上 所画，就有m O f f s e t = +4和y O f f s e t = -6，且对m和y的引用写成机器代码(假设是标准的汇 编器约定)为4 ( f p )和- 6 ( f p )。 局部数组和结构与简单变量相比分配和计算地址并不更加困难，如以下示例所示。 例7.4 考虑C过程 void f(int x, char c) { int a[10]; double y; . . . } 对f调用的活动记录显示为： 2 7 4 编译原理及实践 下载 图7-4 程序清单7 - 2和程序清单7 - 3中 程序的活动树 m y 控制链 返回地址 a) b)
China-pub.com 第7章运行时环境 275 下载 T偏移量 偏移量 控制链 返同地址 a[9] 偏移 a11 a[o] y 而且假设整型是两个字节、地址4个字节、字符1个字节、双精度浮点数8个字节，那么就 有以下的偏移值（再次假设栈的生成为负方向），这些值在编译时都是可计算的： 名称 偏移量 X U +《 -32 现在对a【1】一个访问将要求计算地址 （-24+2*i)(Ep) (这里在产生式2*i中的因子是比例因子(scale factor),它是从假设整型值占有两个字节得来的)： 这样的存储器访问依赖于1的地址以及体系结构，可能只需要一条指令。 对于这个环境中的非局部的和静态名字而言，不能用同局部名字一样的方法访问它们。实 际上，我们此处所考虑的情况一一不带有过程的语言一一所有的非局部的名字都是全局的，因 此也就是静态的。所以在图73中，外部的（全局的）C变量x具有一个固定的静态地址，因此也 就可以被直接访问（或是通过某个基指针的偏移而不是p)。对来自￡的静态局部变量x的访问也 使用完全相同的风格。请注意，正如前一章所描述的，这个机制实现静态（或词法的）作用域。 如果需要动态作用域，那么就要使用一个更为复杂的访问机制（本节后面将要提到）。 2)调用序列谓用序列大致由以下的步骤组成©。当周用一个讨时程时， ①计算自变量并将其存放在过程的新活动记录中的正确位置（将其妥当地压入到运行时栈 中就可做到这一点)。 ②将印作为控制链存放（压入）到新的活动记录中 ③改变p以使其指向新的活动记录的开始（如已有了一个s即，则将该s即复制到该点上的p中， 也可以做到这一点)。 日这个描述忽略了必须发生的奇存晷的任何保存。它还忽略了将返回值放在一个可用的地址的需要
而且假设整型是两个字节、地址 4个字节、字符1个字节、双精度浮点数 8个字节，那么就 有以下的偏移值(再次假设栈的生成为负方向)，这些值在编译时都是可计算的： 名 称 偏 移 量 X + 5 C + 4 A -2 4 Y -3 2 现在对a [ i ]一个访问将要求计算地址 ( - 2 4 + 2 * i ) ( f p ) (这里在产生式2 * i中的因子是比例因子(scale factor)，它是从假设整型值占有两个字节得来的)。 这样的存储器访问依赖于i的地址以及体系结构，可能只需要一条指令。 对于这个环境中的非局部的和静态名字而言，不能用同局部名字一样的方法访问它们。实 际上，我们此处所考虑的情况——不带有过程的语言——所有的非局部的名字都是全局的，因 此也就是静态的。所以在图 7 - 3中，外部的(全局的) C变量x具有一个固定的静态地址，因此也 就可以被直接访问(或是通过某个基指针的偏移而不是 f p )。对来自f的静态局部变量x的访问也 使用完全相同的风格。请注意，正如前一章所描述的，这个机制实现静态 (或词法的)作用域。 如果需要动态作用域，那么就要使用一个更为复杂的访问机制 (本节后面将要提到)。 2) 调用序列 调用序列大致由以下的步骤组成 。当调用一个过程时， ① 计算自变量并将其存放在过程的新活动记录中的正确位置 (将其妥当地压入到运行时栈 中就可做到这一点)。 ② 将f p作为控制链存放(压入)到新的活动记录中。 ③ 改变f p以使其指向新的活动记录的开始(如已有了一个s p，则将该s p复制到该点上的f p中， 也可以做到这一点)。 第 7章 运行时环境 2 7 5 下载 控制链 返回地址 x 偏移量 c 偏移量 a 偏移量 y 偏移量 这个描述忽略了必须发生的寄存器的任何保存。它还忽略了将返回值放在一个可用的地址的需要