📄 9.5.6.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.5.5bb.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.7.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.5.6 集合的表示</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
定值集合，如gen[S]和kill[S]，可以紧凑的用位向量表示。把流图中每个有关的定值编号，表示定值集合的位向量的第i位置1，当且仅当编号为i的定值在这个集合中。
</p>
<p>
位向量的使用还可以使集合运算快速实现。两个集合的并和交分别由逻辑or和逻辑and实现，它们是系统程序设计语言的基本运算。集合A和B的差A-B可以由取B的补，再和A做逻辑and计算。
<p>
<font class = "example">例9.23</font> 图9.28中的程序有7个定值，由放在定值左边注解中的d1到d7表示,其gen和kill集合的位向量在图9.27中语法树各结点的左边。这些集合本身的计算是把<a href="9.5.3_1.htm">图9.27(2)的数据流方程</a>作用于语法树结点代表的语句。
</p>
</td>
</tr>
</table>
<p align=center><img border="0" src="images/9_28.gif"></p>
<p align=center><img border="0" src="images/9.29a.gif"><br><br>
<font size=3><b>    图9.29    图9.28程序的语法树结点的gen和kill集合</b></font></p>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
考虑图9.29右下角的结点d7，gen集合{d7}由000 0001表示，kill集合{d1，d4}由100 1000表示，即d7注销它的变量i的其它定值。
</p>
<p>
if结点的第二和第三个后代分别表示then和else部分。if结点的gen集合000 0011是第二和第三子结点的集合000 0010和000 0001的并。kill集合是空，因为它是对then和else部分的集合求交集。串联语句的数据流方程用于if结点的父结点。这个结点的kill集合由
</p>
<p>
<font color="#FF0000">       000 0000 ∪ (110 0001—000 0011)=110 0000
</font>
</p>
<p>
下面讨论若干in和out的计算，从分析树的顶开始。假定分析树根的in集合为空，那么根的左子树的out集合是那个结点的gen，即111 0000。这也是do结点的in集合的值。从图9.27(2)和do产生式有关的数据流方程可知，do循环中语句的in集合可由do结点的in集合111 0000和这个语句的gen集合000 1111相并得到，结果是111 1111，即所有的定值都可以到达循环体的开始点。但是，在定值d5前那一点的in集合是011 1110，因为定值d4注销d1和d7。
</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.5.5bb.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.7.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -