9.13.6.htm

建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术

    <td width="14%" align="center" height="19"><font face="宋体">Φ</font></td>
    <td width="14%" height="19" align="center">{ I, J }</td>
    <td width="15%" height="19" align="center"><font face="宋体">Φ</font></td>
    <td width="15%" height="19" align="center">{ I, J }</td>
    <td width="15%" height="19" align="center"><font face="宋体">Φ</font></td>
    <td width="15%" height="19" align="center">{ I, J }</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>2</sub></td>
    <td width="14%" align="center" height="20">{ I, J }</td>
    <td width="14%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>3</sub></td>
    <td width="14%" align="center" height="20">{ I }</td>
    <td width="14%" height="20" align="center"><font face="宋体">Φ</font></td>
    <td width="15%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
    <td width="15%" height="20" align="center">{ I, J }</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>4</sub></td>
    <td width="14%" align="center" height="20">{  J }</td>
    <td width="14%" height="20" align="center"><font face="宋体">Φ</font></td>
    <td width="15%" height="20" align="center">{  J }</td>
    <td width="15%" height="20" align="center"><font face="宋体">Φ</font></td>
    <td width="15%" height="20" align="center">{ J }</td>
    <td width="15%" height="20" align="center"><font face="宋体">Φ</font></td>
  </tr>
</table>
<p><font face="宋体">（4）各基本块变量定值点的du链</font></p>
<p><font face="宋体">&nbsp;&nbsp;&nbsp;&nbsp; 
一个变量a在某点P定值后该定值到达a的那些引用点成为该定值点的定值-引用链（简称du链）。使用下面的方程式进行计算：</font></p>
<p><font face="宋体">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; D_IN[B]&nbsp; 
= D_USE[B] ∪ ( D_OUT[B] - D_DEF[B] )</font></p>
<p><font face="宋体">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
D_OUT[B] = ∪ D_IN[S]<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<font size="2"><sup>S∈S[B]</sup></font></font></p>
<p><font face="宋体">其中S[B]是B的后继基本块集。D_USE[B]和D_DEF[B]根据程序流图可直接求出。本题根据图9.6(1)的程序流图求出的D_USE[B]和D_DEF[B]显示在表9.6(5)中。</font></p>
<font face="宋体">表9.6(6)</font>
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="80%" id="AutoNumber5">
  <tr>
    <td width="10%" align="center">基本块</td>
    <td width="49%" align="center">D_DEF[B]</td>
    <td width="28%" align="center">D_USE[B]</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="19">B<sub>1</sub></td>
    <td width="49%">{ (d<sub>3</sub>, I), (d<sub>5</sub>, I), (d<sub>6</sub>, 
    I), (d<sub>3</sub>, J), (d<sub>8</sub>, J) }</td>
    <td width="28%">{ }</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>2</sub></td>
    <td width="49%">{ (d<sub>6</sub>, I), (d<sub>8</sub>, J) }</td>
    <td width="28%">{ (d<sub>3</sub>, I), (d<sub>3</sub>, J) }</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>3</sub></td>
    <td width="49%">{ (d<sub>3</sub>, I), (d<sub>5</sub>, I) }</td>
    <td width="28%">{ (d<sub>6</sub>, I) }</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>4</sub></td>
    <td width="49%">{ }</td>
    <td width="28%">{ (d<sub>8</sub>, J) }</td>
  </tr>
</table>
<p>变量I和J的D_IN[B]和D_OUT[B]的计算结果分别显示在表9.6(6)和表9.6(7)中。</p>
表9.6(6)
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="90%" id="AutoNumber4" height="117">
  <tr>
    <td width="10%" align="center" rowspan="2" height="37">基本块</td>
    <td width="25%" height="19" colspan="2" align="center">第一次迭代后</td>
    <td width="28%" height="19" colspan="2" align="center">第二次迭代后</td>
    <td width="28%" height="19" colspan="2" align="center">第三次迭代后</td>
  </tr>
  <tr>
    <td width="14%" align="center" height="19">D_IN[B]</td>
    <td width="14%" height="19" align="center">D_OUT[B]</td>
    <td width="15%" align="center" height="19">D_IN[B]</td>
    <td width="15%" height="19" align="center">D_OUT[B]</td>
    <td width="15%" align="center" height="19">D_IN[B]</td>
    <td width="15%" height="19" align="center">D_OUT[B]</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="19">B<sub>1</sub></td>
    <td width="14%" align="center" height="19"><font face="宋体">00000000</font></td>
    <td width="14%" height="19" align="center">00100000</td>
    <td width="15%" height="19" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="19" align="center">00100000</td>
    <td width="15%" height="19" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="19" align="center">00100000</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>2</sub></td>
    <td width="14%" align="center" height="20">00100000</td>
    <td width="14%" height="20" align="center">00000100</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00000100</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00000100</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>3</sub></td>
    <td width="14%" align="center" height="20">00000100</td>
    <td width="14%" height="20" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="20" align="center">00000100</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00000100</td>
    <td width="15%" height="20" align="center">00100000</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>4</sub></td>
    <td width="14%" align="center" height="20">00000000</td>
    <td width="14%" height="20" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="20" align="center">00000000</td>
    <td width="15%" height="20" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="20" align="center">00000000</td>
    <td width="15%" height="20" align="center"><font face="宋体">00000000</font></td>
  </tr>
</table>
<p><font face="宋体">根据表9.6(6)，D_OUT[B<sub>1</sub>] = 00100000，故I在B<sub>1</sub>中定值点d<sub>1</sub>的du链是{ 
d<sub>3</sub> }。D_OUT[B<sub>2</sub>] = 00000100，故I在B<sub>2</sub>中定值点d<sub>4</sub>的du链是{ 
d<sub>5</sub>, d<sub>6</sub> }。D_OUT[B<sub>3</sub>] = 00100000，故I在B<sub>3</sub>中定值点d<sub>6</sub>的du链是{ 
d<sub>3</sub> }。</font></p>
<font face="宋体">表9.6(7)</font>
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="90%" id="AutoNumber4" height="117">
  <tr>
    <td width="10%" align="center" rowspan="2" height="37">基本块</td>
    <td width="25%" height="19" colspan="2" align="center">第一次迭代后</td>
    <td width="28%" height="19" colspan="2" align="center">第二次迭代后</td>
    <td width="28%" height="19" colspan="2" align="center">第三次迭代后</td>
  </tr>
  <tr>
    <td width="14%" align="center" height="19">D_IN[B]</td>
    <td width="14%" height="19" align="center">D_OUT[B]</td>
    <td width="15%" align="center" height="19">D_IN[B]</td>
    <td width="15%" height="19" align="center">D_OUT[B]</td>
    <td width="15%" align="center" height="19">D_IN[B]</td>
    <td width="15%" height="19" align="center">D_OUT[B]</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="19">B<sub>1</sub></td>
    <td width="14%" align="center" height="19"><font face="宋体">00000000</font></td>
    <td width="14%" height="19" align="center">00100000</td>
    <td width="15%" height="19" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="19" align="center">00100000</td>
    <td width="15%" height="19" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="19" align="center">00100000</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>2</sub></td>
    <td width="14%" align="center" height="20">00100000</td>
    <td width="14%" height="20" align="center">00000001</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00100001</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00100001</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>3</sub></td>
    <td width="14%" align="center" height="20">00000000</td>
    <td width="14%" height="20" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00100000</td>
    <td width="15%" height="20" align="center">00100000</td>
  </tr>
  <tr>
    <td width="1%" align="center" height="20">B<sub>4</sub></td>
    <td width="14%" align="center" height="20">00000001</td>
    <td width="14%" height="20" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="20" align="center">00000001</td>
    <td width="15%" height="20" align="center"><font face="宋体">00000000</font></td>
    <td width="15%" height="20" align="center">00000001</td>
    <td width="15%" height="20" align="center"><font face="宋体">00000000</font></td>
  </tr>
</table>
<p><font face="宋体">根据表9.6(7)，D_OUT[B<sub>1</sub>] = 00100000，J在B<sub>1</sub>中定值点d<sub>2</sub>的du链是{ 
d<sub>3</sub> }。D_OUT[B<sub>2</sub>] = 00100001，故J在B<sub>2</sub>中定值点d<sub>3</sub>的du链是{ 
d<sub>3</sub>, d<sub>8</sub> }。</font></p>
</body>
</html>
<html><script language="JavaScript">