arti_10718.htm

编译原理

<tr>
<td>
<div v:shape="_x0000_s1047">
<div>B2</div></div></td></tr></table>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if C&lt;D goto L1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </P>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E:=A*A</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; F:=F+1</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E:=E+F&nbsp;&nbsp;&nbsp;&nbsp; B2</div>
<P>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div v:shape="_x0000_s1052">
<div>B5</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div v:shape="_x0000_s1051">
<div>B4</div></div></td></tr></table>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Write E&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </P>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Halt</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp; L1:E:=B*B</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; F:=F+2</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E:=E+F&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; B3</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Write E</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if E&gt;100 goto L2</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; halt&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; B4</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp; L2: F:=F-1</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Goto L1&nbsp;&nbsp;&nbsp; B5</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </div>
<div>3.试对以下基本块B1和B2：</div>
<div>&nbsp;B1:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; B2:</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A:=B*C&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; B:=3</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; D:=B/C&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; D:=A+C</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E:=A+D&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; E:=A*C</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; F:=2*E&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; F:=D+E</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; G:=B*C&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; G:=B*F</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; H:=G*G&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; H:=A+C</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; F:=H*G&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; I:=A*C</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L:=F&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; J:=H+I</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; M:=L&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; K:=B*5</div>
<div>L:=K+J</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; M:=L</div>
<div>分别应用DAG对他们进行优化，并就以下两种情况分别写出优化后的四元式序列：</div>
<div>（1）假设只有G，L，M在基本块后面还要被引用；</div>
<div>（2）假设只有L在基本块后面还要被引用。</div>
<div>解答：</div>
<div>&nbsp; 基本块B1的DAG图为：</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<P>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n1</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>B0</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n2 </SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>C0</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n3</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>*</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n 4</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>/</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>A,G</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>D</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n5</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>+</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>E</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n6</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>2</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n7</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>*</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n8</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>*</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>H</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>F</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n9</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>*</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>F,L,M</div></div></td></tr></table>&nbsp;</P>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div><br clear=all>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </div>
<div>假设只有G，L，M在基本块后面还要被引用，B1优化后的中间代码为：</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;G:=B+C&nbsp;&nbsp; </div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;H:=G*G</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;L:=H*G</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;M:=L</div>
<div>假设只有L在基本块后面还要被引用，则B1优化后的中间代码为：</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; G:=B+C&nbsp;&nbsp; </div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; H:=G*G</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L:=H*G</div>
<div>基本块B2的DAG图为：</div>
<div>&nbsp;</div>
<P>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n1</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>3</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>B</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n2</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>A0</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>A</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div><SUP>n3</SUP></div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>C0</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>
<div>
<div>B</div></div></td></tr></table>
<table cellSpacing=0 cellPadding=0 width="100%">

<tr>
<td>