📄 8.7.0d.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.0c.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='8.8.0.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>  </td>
<td class="content">
<P><B><font class="example"><img border="0" src="images/dingyi.gif" width="32" height="31">例8.9
</font></B>将图8.15的算法应用于图8.12的树所产生的顺序可以用来生成图8.14的代码。作为一个更全面例子，我们考虑图8.16的dag。</P>
<center><IMG height=398 src="8.16.gif" width=424></center>
<center>图8.16 一个dag</center>
<P>初始没有未列入表的父结点的唯一结点是1，因此我们在第（2）行置n＝1，并在第（3）行将1列入表中。现在，1的左子结点2的父结点已经全部列入表中，因此，我们将2列入表中并在第（6）行置n＝2。现在，在第（4）行我们找到2的最左子结点6，它有一个未列入表的父结点5。因此，我们在第（2）行选取一个新的n，结点3为唯一的候选者。我们将3列入表中并且沿着其左链往下走，依次将4，5，6结点列入表中。现在内部结点中仅剩下结点8，我们把它列入表中。结果表为1234568。从而我们建议求值的顺序为8654321。这个顺序对应如下三地址语句序列：</P>
<P>
t<Sub>8</sub>：＝d＋e <BR>
t<Sub>6</sub>：=
a＋b <BR>
t<Sub>5</sub>：＝t<Sub>6</sub>－c <BR>
t<Sub>4</sub>：＝t<Sub>5</sub>*t<Sub>8</sub>
<BR>
t<Sub>3</sub>：＝t<Sub>4</sub>－e <BR>
t<Sub>2</sub>：＝t<Sub>6</sub>+t<Sub>4</sub>
<BR>
t<Sub>1</sub>：＝t<Sub>2</sub>*t<Sub>3</sub></P>
如果我们应用8.5节的简单代码生成算法，将产生此dag的优化代码。要注意的是，用在这个例子上的排序启发在第（2）步中从未遇有任何可做的选择，但一般说来它可以有多种选择。</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.0c.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='8.8.0.htm'"></img></td>
</tr>
</table>
</body>
</html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -