📄 9.4.1.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.3.3_2.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.1_2.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.4 流图中的循环</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
在考虑循环优化之前，需要定义流图中的循环如何构成。我们使用一个结点是另一个结点的必经结点的概念来定义循环和重要的可归约流图类。
</p>
</td>
</tr>
</table>
<hr size=2 width=90% align=center color=red><br>
<font class="title2"><b>9.4.1 必经节点</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
一、什么是必经结点
</p>
<p>
<font class = "definition2">必经结点</font>：如果从初始结点起，每条到达n的路径都要经过d，我们就说流图中结点d是结点n的必经结点，写成 d dom n
</p>
<p>
根据这个定义，每个结点是它本身的必经结点；循环的入口是循环中所有结点的必经结点。
</p>
<p><p><font class = "example">例9.6</font> 考虑图9.16中的“流图”，此流图的开始结点是1。开始结点是所有结点的必经结点。结点2仅是它本身的必经结点，因为控制可以沿着1→3开始的路径到达任何其它结点。结点3是除了1和2以外的所有结点的必经结点。结点4是除了1，2和3以外的所有结点的必经结点，因为从1出发的所有路径必须由1→2→3→4或1→3→4开始。 结点5和6仅是它们自己的必经结点，因为控制流可以在5和6两个结点之间选择一个结点。结点7是7，8，9，10的必经结点。结点8是8，9，10的必经结点。结点9和10仅是它们本身的必经结点。
</p>
</td>
</tr>
</table>
<p align=center><img border="0" src="images/9_16.gif"></p>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
二、什么是必经结点树
</p>
<p>
<font class = "definition2">必经结点树</font>：用树结构表示必经结点信息，这样的树叫做必经结点树。初始结点是树根，树中每个结点仅是它后代的必经结点。例如：图9.16中右侧的图即是左边流图的必经结点树。
</p>
<p>
必经结点树的存在依据必经结点的性质。每个结点n有一个唯一的直接必经结点m，它是从初始结点到n的任何路径上n的最后一个必经结点。根据dom关系，直接必经结点有下列性质：如果d≠n和d dom n，那么 d dom m。</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='9.3.3_2.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.4.1_2.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -