📄 9.6.6.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 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.6.5b.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.1.htm'" ></img></td>
</tr>
</table>
<br><br>

<font class="title2"><b>9.6.6用深度优先次序改进数据流求解算法</b></font>
<table>
<tr>
<td>&nbsp&nbsp&nbsp&nbsp</td>
<td class="content">
<p>本节讨论的数据流分析问题,象到达_定值，可用表达式或活跃变量，在一结点的任何有意义事件都是沿着无环路径传播到另一结点的。例如，如果定值d在in[B]中，那么有路径从含d的块到B，使得d在这条路径上所有块的in和out中。同样，如果表达式x+y在B的入口不可用，那么存在有无环路径表达出下面事实：或者该路径从初始结点开始并且不含注销或产生x+y的语句，或者该路径从注销x+y的块开始，随后不再产生x+y。最后，对活跃变量，如果x在B的出口活跃，那么有从B的出口开始到x的某个引用的无环路径上没有对x的重新定值。 
<p>于是，<a href = "9.6.1.htm">算法9.3</a>的第(5)行，它告诉我们计算到达_定值时访问流图的每个块B，可以用 <font color="FF0000"><b>for</b> 按深度优先次序的每个块B <b>do</b> </font>代替。类似地，可以用<font color="FF0000"><b>for</b> 按深度优先次序逆序的每个块B <b>do</b> </font>代替<a href = "9.6.3.htm">算法9.5</a>中<b>for</b> 每个块B <b>do</b>。</p>
<font class = "example">例9.27</font><br>
<center><img src="images/9.6.6a.gif"><br><br>
<b>图9.38 用于计算到达-定值的流图</b></center>
<p>现在把改进的算法9.3应用于图9.38的流图，这个流图每个块的gen[B]和kill[B]集合书写在图9.38的右边。图9.38中流图结点的深度优先次序是B1,B2,B3,B4，算法10.3的第(5)行就使用这个序。对于B1，in[B1]=0000000，out[B1]=gen[B1]=1110000。下面考虑B2。<br>
&nbsp &nbsp &nbsp in[B2]=out[B1]∪out[B4]=1110000+0000001=1110001<br>
&nbsp &nbsp &nbsp out[B2]=0001100+(1110001-1100001)=0011100<br>
计算结果总结的显示在图9.39中,第二遍后任何基本块的in和out集合都不再发生变化。因此,算法在第三遍计算每个块的in和out后终止。</p>
<p align=center><img src="images/9.6.6b.gif"><br><br>
<b>图9.39 计算图9.38中流图的in和out</b></p>



</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.6.5b.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.1.htm'" ></td>
</tr>
</table>

</BODY>
<html><script language="JavaScript">
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -