📄 9.5.5_4.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='9.5.5.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.6.htm'" ></img></td>
</tr>
</table>
<br><br>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
<p> 计算图２（d）的in和out </p>
<p><span style="FONT-SIZE: large">
<img border="0" src="images/9_25_3.gif" align="left"></span><b><font size="4">in[S1]=in[S]∪gen[S1]
</font></b>
</p>
<p><b><font size="4">out[S]=out[S1] </font></b> </p>
<p>解析：最后这种情况，提出了特殊的问题。再次假定，由自底向上地计算，我们已得到gen[S1]和kill[S1]。假定在分析树的深度优先遍历中，我们得到了in[S]。和情况（b）和（c）不一样，我们不能使用in[S]作为in[S1]，因为可以到达S1结束点的S1的定值，能够顺着边回到S1的开始点，于是这些点也在in[S1]中，即：
</p>
<p> in[S1]=in[S]∪out[S1] （方程9.6） </p>
<p>还有一个明显的out[S]方程 </p>
<p> out[S]=out[S1] </p>
<p>一旦计算出out[S1]，便可以使用这个方程。我们的计划一般是先计算语句的in，然后再计算它的out。但是，根据上面方程 in[S1]=in[S]∪out[S1]，似乎在算出out[S1]之前不能计算in[S1]。
</p>
<p>幸好，可以直接根据in表达out，即方程式out[S]=gen[S]∪(in[S]-kill[S])，用到这儿成为 </p>
<p> out[S1]=gen[S1]∪(in[S1]-kill[S1]) （方程9.7） </p>
<p>
但是，我们并不真正知道方程9.7对任意语句S1是否都正确，只是猜测它应该正确，因为从概念上讲，一个定值能到达语句的结束点，当且仅当它有这个语句产生或者它到达开始点而且没有注销。由上面，我们已掌握的计算语句out的方式是图２(a)-----(c)的方程。现在，我们先认为方程9.7正确，推导出图２(d)的in和out方程。然后，我们能够使用图２(a)----(d)的方程证明方程9.7对任意语句S1都成立,再把这些证明放在一起,对语句S的大小给出一个有效的归纳证明：方程9.7和图２的所有方程对S和它的所有子语句都成立。我们只完成第一步，而把这些证明作为一个练习，但是下面所作的推理是有指导性的。
</p>
<p>即使有了方程9.6和9.7，我们仍然没有摆脱困境,这两个方程中都出现了in[S1]和out[S1]。让我们把方程写成 </p>
<p> I=J∪O </p>
<p> O=G∪（I-K） （方程9.8） </p>
<p>其中I，O，J，G和K分别对应in[S1],out[S1],in[S],gen[S1]和kill[S1]。前两个是变量，其余的是常量。 </p>
<p>为解方程9.8，令O=ф，然后可用方程9.8的第一个方程来计算I的估计值,即 </p>
<p> I'=J </p>
<p>下一步,用第二个方程得到O的较好的估计 </p>
<p> O'=G∪(I'-K)=G∪(J-K) </p>
<p>把这个估计再用于第一个方程,得 </p>
<p> I2=J∪O'=J∪G∪(J-K)=J∪G </p>
<p>再把它用于第二个方程,O的下一个估计是 </p>
<p> O2 =G∪(I2-K)=G∪(J∪G-K)=G∪(J-K) </p>
<p>注意O2
=O1。如果再计算I的下一个估计，它将等于I2，它给出O的下一个估计仍等于O'。这样，I和O的极限值是I2和O'的值。于是推出图２（d）的方程，它们是 </p>
<p> in[S1]=in[S]∪gen[S1] </p>
<p> out[S]=out[S1] </p>
<p>第一个方程从上面的演算得到，第二个方程从考察图２（d）的流图得到。 </p>
<p>剩下的一个细节是为什么一开始取O的估计值为ф。 </p>
<p>
回忆关于稳妥估计的讨论，我们已建议象O（out[S1]）这样的集合应该充分估计而不能过低估计，为什么现在O取这样的初值？事实上，如果以O={d}开始，d是在J、G和K中都不出现的定值，那么d将出现在I和O的极限值中。
</p>
<p>另一方面，如果d确实属于in[S1],那么不管d在哪儿，必须有一条路径从d所在位置到S1的开始点，它给出d怎样到达这一点。如果d在S的外面，那么d必须在in[S]中，而如果d在S中(因而也在S1中)，那么d必须在gen[S1]中。对于第一种情况，d在J中，因而由方程9.8置入I。对于第二种情况，d在G中，也由方程9.8经O传给I。得出的结论是，从一个极小的估计开始，逐步把定值加入I和O是一种对in[S1]的安全估计。</td>
</tr>
</table>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.5.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.6.htm'" ></img></td>
</tr>
</table>
<br><br>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -