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

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>
<td class="content">
<P><font class="definition2">对于dag的一种启发式排序</font></P>
<P>上述重排序改进了代码的原因在于对t<SPAN class=down>4</SPAN>的求值正好紧跟在对t<SPAN 
class=down>1</SPAN>（树中t<SPAN class=down>4</SPAN>的左运算分量）的求值之后。很显然，为了t<SPAN 
class=down>4</SPAN>的有效计算，应使左运算分量在一个寄存器中，而t1的求值在t4之前就保证了将是这种情形。</P>
<P>在选择一个dag的结点顺序时，唯一的约束是必须保证dag中保持的边的关系。回忆8.6节，这些边或者表示算符-运算对象关系，或者表示由于过程调用、数组赋值或指针赋值而带来的隐含约束。我们给出下面的启发式排序算法，它尽可能地使一个结点的求值紧接在它的最左变元的求值之后。图8.15的算法产生的是反向顺序。</P>
<P>（l）<font color="#0000FF">while</font> 存在未列入表的内部结点 <font color="#0000FF"> do</font> <BR>
&nbsp;&nbsp;&nbsp; （2）<font color="#0000FF">begin</font> 选取一个未列入表的但其全部父结点均已列入表的<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;结点 n; <BR>
&nbsp;&nbsp;&nbsp; （3） &nbsp;&nbsp;&nbsp;&nbsp;将 n 列入表中； <BR>
&nbsp;&nbsp;&nbsp; （4） &nbsp;&nbsp;&nbsp;&nbsp;while &nbsp;n的最左子结点m不是叶结点并且其所有父结点<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;均已列入表中&nbsp;<font color="#0000FF">do</font> <BR>
&nbsp;&nbsp;&nbsp; （5） &nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">begin</font>&nbsp;将m列入表中； <BR>
&nbsp;&nbsp;&nbsp; （6） &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n：＝m<BR>
&nbsp;&nbsp;&nbsp;    （7） &nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">end</font><BR>
&nbsp;&nbsp;&nbsp; （8）<font color="#0000FF">end</font><br>  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;    
图8.15&nbsp;&nbsp;  启发式排序算法</P><br>

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

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

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