📄 6.4.3_3b.htm
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<body>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.4.3_3.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.4.4.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<P>
图6.20（a）表示的是刚好在活动quicksort(1,3)开始以前的情况。由于quicksort的嵌套深度为2，当quicksort的一次新的活动开始时，display表中元素d[2]将会受到影响，即将改变其值。quicksort(1,3)对d[2] 的影响如图6.20(b)所示，在那里，d[2]指向了新的活动记录，而旧的d[2]之值被存放在新的活动记录之中。被存放起来的值在控制返回到活动quicksort(1,9)并从而恢复display表为6.20(a)的情况时将要用到。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
当一个新的活动开始时display表要发生变化，并且当控制从新的活动返回时还必须恢复display表。Pascal语言及其它一些语言的词法作用域规则允许按下列步骤保持display表。当一个嵌套深度为i的过程的活动记录被建立时，我们作如下的工作：
<br> 1.在新的活动记录中保存d[i]的值。
<br> 2.置d[i]指向新的活动记录。
<br>恰好在一个活动结束前，d[i]被重新置成保留的值。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
让我们来考虑这些步骤。假设嵌套深度为j的过程调用嵌套深度为i的过程。有两种情况，即在源程序正文中被调用过程是否嵌套在调用过程之中，如存取链的讨论。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
1．j＜i的情况。那么，i=j+l，并且被调用过程嵌套在调用过程之中。 display表中的前j个元素不需要变化，并把d[i]置为指向新的活动记录。如图6.20(a)中的当sort调用quicksort时和图6.20(c)中的quicksort调用partition时说明这种情况。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
2．j≥i的情况。同前，被调用过程和调用过程的嵌套深度为1,2,...,i-1的外围过程必然是相同的。这里，我们把旧的d[i]之值保存在新的活动记录中，并置d[i]指向新的活动记录。display表被正确地保持下来，因为表中前i－1个元素没有改变。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
在图6.20(b)中的quicksort被递归地调用时出现i=j=2的情况。更有意义的一个例子如图6.20(d)所示，嵌套深度为3的活动partition(1,3)调用嵌套深度为2的exchange(1,3)，它们的外围过程是嵌套深度为1的sort(此程序在图6.18中)。注意，当exchane(1,3)被调用时，属于partition(1,3)的d[3]之值仍在display表中，尽管当控制在exchange中时不能访问partition。然而如果exchange调用另外一个嵌套深度为3的过程时，这个过程将存储d[3]并当返回exchange时恢复d[3]的值。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
在实现时，如果有足够的寄存器，那么display表的每一个元素占用一个寄存器，于是display表将是寄存器的一个集合。编译程序可以确定这个数组的最大长度，它就是程序中允许的最大的过程嵌套深度。另外，display表可以静态分配在内存中。也可以将display表存储在运行时刻的栈中，并在每一个过程入口建立一个新的副本。
<p>
</p>
</td></tr></table>
<table>
<tr>
<td><font class="yanshi">     观看演示 </font></td>
<td><font color=blue onmouseover="javascript:style.cursor='hand'" onclick="javascript:open('applets/test6_4/page1.htm','_blank','menu=no,toolbar=no,location=no,directories=no,status=no,scrollbars=yes,resizable=yes,copyhistory=no,left=100,top=100,width=800,height=600')">Display表的演示</font></td>
<td><img src="../images/yanshi.gif"></img></td>
</tr>
</table>
<br>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.4.3_3.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.4.4.htm'"></img></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -