📄 9.6.2b.htm.bak
字号:
<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.6.2ab.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.2bb.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.6.2 可用表达式（二）</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
可以用类似于计算到达_定值集合的方式寻找可用表达式。假定U是程序中出现在语句右部的所有表达式集合。对每个基本块B，令e_in[B]是在B开始点的可用表达式集合，令e_out[B]是在B结束点的可用表达式集合，定义e-gen[B]是B生成的可用表达式集合，定义e-kill[B]是U中被B注销的表达式集合。e_in，e_out，e-gen，e-kill可以用位向量表示。下列方程把未知的e_in和e_out同已知的e-gen和e-kill联系起来。
</p>
<font color="#FF0000">         e_out[B]=e_in[B]－e-kill[B]∪e-gen[B] <br>
         e_in[B]=∩e_out[P] (B不是开始块) <br>
<font size="2">                   P是B的前驱 </font><br>
         e_in[B1]=Ф (B1不是开始块)           (方程9.10)
</font> <br>
<p>
方程（9.10）看起来和方程<a href="9.6.2b_1.htm">（9.9）</a>的到达_定值方程几乎一样。第一个区别是开始块的in处理为特殊情况。这是基于程序从开始块刚开始执行时，没有任何东西可用，即使某些表达式沿着从程序的其他地方到达开始结点的所有路径都可用。因为，若不强置in[B1]为空，可能会错误地推断出某些表达式在程序启动前可用。
</p>
<p>
第二个也是更重要的区别是，合流算符是交而不是并。应该是这样，因为一个表达式在块的开始点可用，只有当它在该块的所有前驱块的结束点可用。与此相反，一个定值到达块的开始点，只要它能到达该块的某个前驱的结束点。
</p>
<p>
对可用表达式，如果它对x或y赋值（或可能赋值），并且随后没有重新计算x+y，我们就说基本块注销表达式x+y。
</p>
<p>
∩而不是∪的使用使方程（9.10）的行为和（9.9）有区别。虽然两种方程的解都不唯一，但对（9.9），求的是对应于到达_定值的最小解，为得到这个解，由假设没有任何东西到达任何地方开始，并逐步增大到这个解。按这种方式，我们决不会让定值d到达点p，除非真能找到路径把d传播到p。相反，对方程（9.10），我们想要得是最大可能解，所以从足够大的近似开始，并逐步减小。
</p>
<p>
我们从假定任何东西，即集合U，在任何地方都可用开始，并且仅删掉那些表达式，对于它们，我们可以找到一条路径，在这条路径上它们不可用，最后到达真正的可用表达式集合。在可用表达式情况下，得到精确的可用表达式集合的子集是稳妥的办法，我们用方程（9.10）所能得的正是这样的子集。子集之所以稳妥的原因是：我们利用这些信息是为了把先前计算的值代替可用表达式的计算，不知道一个表达式可用仅仅禁止了我们进行这种代换。
</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='9.6.2ab.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.2bb.htm'" ></img></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -