📄 6.4.3_2b.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_2.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.4.3_3.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<P>
假设嵌套深度为n<sub>p</sub>的过程p引用一个嵌套深度为n<sub>a</sub>≤n<sub>p</sub>的非局部名字a,a的存储位置可按下面的步骤找到：
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
1．当控制在p中时,p的活动记录在栈顶。沿着从栈顶活动记录出发的n<sub>p</sub>-n<sub>a</sub>个存取链前进。n<sub>p</sub>-n<sub>a</sub>的值可在编译时刻预先计算出来。如果一个活动记录中的存取链指向另一个活动记录中的存取链，那么可以通过执行一个间接操作来跟踪这条链。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
2．沿着n<sub>p</sub>-n<sub>a</sub>个链前进后，我们到达a所在的过程的活动记录。如上一节所讨论的，它的位置是由活动记录中相对于某个位置的一个固定偏移量来表示的。特别说来，偏移量也可以是相对于存取链的。因此在过程p中非局部名字a的地址由下面的二元组给出，它的值是在编译时刻计算的，并存放在符号表中:
<br>
（n<sub>p</sub>-n<sub>a</sub>，在包含a的活动记录之内的偏移量) <br>
其中第一个成分给出了将要经过的存取链的个数。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
例如，图6.18中的(15)-(16)行上，过程partion的嵌套深度为3，它分别引用嵌套深度为1 的非局部名字a和嵌套深度为2的非局部名字v。分别包含这两个局部名字存储单元的活动记录可以分别从partition的活动记录出发沿着存取链前进3-1=2步和3-2=1步而达到。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
而建立存取链的代码是调用序列的一部分。我们假设嵌套深度为n<sub>p</sub>的过程p调用嵌套深度为n<sub>x</sub>的过程x。在被调用过程的活动记录中建立存取链的代码依赖于被调用过程是否嵌套在调用过程中。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
1.n<sub>p</sub>＜n<sub>x</sub>的情况。由于被调用过程x的嵌套深度比过程p的嵌套深度大，因而它必须在p中说明，否则p就不能访问它。如图6.19(a)中的sort调用quicksort以及图6.19(c)中的quicksort调用partition时都发生这种情况。在这种情况下，被调用过程的活动记录的存取链必须指向栈中刚好在其前面的（地址码较低的）调用过程的活动记录的存取链。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
2.n<sub>p</sub>≥n<sub>x</sub>的情况。从作用域规则可知，调用过程和被调用过程的嵌套深度1,2…,n<sub>x</sub>-1的外围过程必定是相同的。如图6.19(b)中的quicksort（嵌套深度为2）调用它自己，即n<sub>p</sub>=n<sub>x</sub>=2 ，n<sub>x</sub>-1=1。嵌套深度为1的sort是调用者兼被调用者quicksort的外围过程。又如图6.19(d)中的partition调用exchange，此时n<sub>p</sub>=3,n<sub>x</sub>=2，即n<sub>x</sub>-1=1。这说明嵌套深度为l的sort既是partition也是exchange的外围过程。如果从调用过程的活动记录沿存取链前进n<sub>p</sub>-n<sub>x</sub>+1步，可以到达包围着调用过程和被调用过程并离它们最近的过程的当前的活动记录。这时到达的存取链位置就是被调用过程的存取链所要指向的。例如在图6.19(b)中，可从quicksort(1,9)的活动记录中的存取链前进n<sub>p</sub>-n<sub>x</sub>+1=2-2＋1＝1步而到达sort的活动记录的存取链位置，这正是quicksort(1,3)的活动记录的存取链所要指向的位置。又如在图6.19(d)中，可从partition(1,3)的活动记录中的存取链前进n<sub>p</sub>-n<sub>x</sub>+1=3-2+1=2步而到达sort的活动记录，同样这也正是exchange(1,3)的活动记录的存取链所要指向的。再者，n<sub>p</sub>-n<sub>x</sub>＋1也可以在编译时刻计算。
</p>
</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_2.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.4.3_3.htm'"></img></td>
</tr>
</table>
</BODY>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -