📄 8.6.1_2.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.6.1b.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='8.6.1_2b.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>8.6.1 dag的构造</b></font>
<table><tr><td>    </td>
<td class="content" width="865">
<P>为了构造一个基本块的dag，我们将依次处理块中的每一个语句。当我们遇到形如x：＝y＋z的语句，我们寻找分别代表y和z当前值的结点。
这些结点可能是叶结点，或者是dag的内部结点，即如果y，z已由基本块中先前的语句求得值。然后我们构造一个标记为+的结点，并且给它两个子结点，其左子结点对应y，右子结点对应z。然后在标记为＋的结点旁边附加标记x。然而，如果已经有一个结点表示同样的值y＋z，这时我们就不必在dag中增加一个新的结点，只需给予该已存在的结点一个附加标记x即可。</P>
<P>另外两点要提到的是，如果x（不是x<sub>0</sub>）已经事先附加在某个其它结点上，我们需去掉这个先前的标记x，因为x的当前值是刚刚新建立的结点的值；另外，对赋值语句x：＝y，我们不再构造新结点，而仅将标记x附加到y的当前值所在的结点上。现在我们给出构造一个基本块的dag的算法。</P>
<P><font class="example"><img border="0" src="images/dingyi.gif">算法8.2</font> 构造一个dag</P>
<P>输入：一个基本块。</P>
<P>输出：此基本块的一个dag，其中包含如下的信息：</P>
<P>1.每个结点都有一个标记。叶结点的标记是一个标识符（允许是常数），内部结点的标记是一个运算符号。</P>
<P>2.在每个结点上有一个附加的标识符表（可能为空），这里的标识符不允许是常数。</P>
<P>方法：我们假定存在一个函数node（identifier），当我们在建立dag时，它将返回最新建立的与identifier相联系的结点。</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='8.6.1b.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='8.6.1_2b.htm'"></img></td>
</tr>
</table>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -