📄 9.5.5ab.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.5.5.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.5b.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.5.5 in和out的计算</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
许多数据流问题可以用类似计算gen和kill的综合翻译来解决.例如,对每个语句S,我们想确定S定值的变量集合,这些信息可以由计算类似gen方程的方程得到,甚至不需要类似kill的集合。这些信息可用于确定循环的不变计算。
</p>
<p>
但是，另外一些数据流问题，如到达_定值问题，还需要计算某些继承属性。很明显，in是继承属性，out是依赖于in的综合属性。in[S]是到达S开始点的定值集合，它的计算要考虑到整个程序的控制流，包括S外面的语句或者嵌在S其中的语句。集合out[S]是类似地为S的结束点定义的。注意区别out[S]和gen[S]是很重要的，后者是不经过S外的路径到达S结束点的定值集合。
</p>
<p>
用一个简单的例子来区别:
</p>
<p>
<p><img src="images/9_25_2.gif">
</p>
<p>考虑图9.27(2)（b）的串联语句。语句d在S<sub>1</sub>中产生，因而到达S<sub>2</sub>的开始点，如果d不在kill[S<sub>2</sub>]中，d将到达S<sub>2</sub>的结束点，于是d在out[S<sub>2</sub>] 中而不在gen[S<sub>2</sub>]中。
</p>
<p>
在自底向上计算了所有语句的gen和kill后，可以从代表整个程序的语句开始计算in和out。如果S0是整个程序开始，in[S0]=φ，即没有定值到达程序的开始。对图9.27(2)的四类语句。可以假定in[S]都是已知的，用它来计算S每个子语句的in。然后自顶向下递归地计算每个子语句S<sub>1</sub>或S<sub>2</sub>的out，并用这些集合计算out[S]。
</p>
<p>
<table>
<tr>
<td class="content">
<p>
<hr size=2 width=90% align=center color=red><br>
<p><font class = "example"> 计算图9.27(2)（a）的in和out </font></p>
<p><span style="FONT-SIZE: large">
<img border="0" src="images/9_25_1_3.gif"></span></p>
<p><font size="4" color="#FF0000">out[S]=gen[S]∪(in[S]-kill[S]) </font>
</p>
<p>解析：这是一种最简单的情况，它是一个赋值语句，如果知道in[S],即可由方程<font color="#FF0000">out[S]=gen[S]∪(in[S]-kill[S])</font>计算out。</p>
</td>
</tr>
</table>
<hr size=2 width=90% align=center color=red><br>
<table>
<tr>
<td class="content">
<p>
<p><font class = "example"> 计算图9.27(2)（b）的in和out </font></p>
<p><span style="FONT-SIZE: large">
<img border="0" src="images/9_25_2.gif"></span></p>
<p><font size="4" color="#FF0000">in[S<sub>1</sub>]=in[S]</font>
</p>
解析:根据in[S<sub>1</sub>]=in[s]和out[s]=gen[s]∪(in[s]-kill[s]),先算出out(S<sub>1</sub>),它做为in(S<sub>2</sub>),再迭代一次,计算出out(S<sub>2</sub>)。
</font>
</p>
</table>
<hr size=2 width=90% align=center color=red><br>
<table>
<tr>
<td class="content">
<p>
<p><font class = "example"> 计算图9.27(2)（c）的in和out </font></p>
<p><span style="FONT-SIZE: large">
<img border="0" src="images/9_25_3.gif">
<p><font size="4" color="#FF0000">in[S<sub>1</sub>]=in[S<sub>2</sub>]=in[S]</font></b>
<p><font size="4" color="#FF0000">out[S]=out[S<sub>1</sub>]∪out[S<sub>2</sub>]</font>
</p>
<p><font size="3" >解析:根据in[s],先计算出in[S<sub>1</sub>]和in[S<sub>2</sub>],然后计算出out[S<sub>1</sub>]和out[S<sub>2</sub>],最后,根据out[s]=out[S<sub>1</sub>]∪out[S<sub>2</sub>],计算出out[s]。
</font></p>
</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.5.5.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.5b.htm'" ></img></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -