⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 9.13.5.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 HTM
字号:
🔍 
<html>
<head>
<title>9.5的解答</title>
</head>
<body background="../images/background.gif">
解：采用字节地址，两个字节作为一个机器字。<br>
（1）程序的四元式中间代码如下：<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>1</sub>:   read N&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 置初值 */<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      i := 2<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>2</sub>:   if i > N goto B<sub>4</sub>&nbsp;&nbsp;&nbsp; /* 第一个for语句 */<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>3</sub>:   T<sub>1</sub> := i<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>2</sub> := addr(A)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* 数组A的基地址 */<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>1</sub> := 2 * T<sub>1</sub><br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>2</sub>[T<sub>1</sub>] := true<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      i := i + 1<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      goto B<sub>2</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>4</sub>:   i := 2<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>3</sub> := N ** 0.5<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>3</sub> := [T<sub>3</sub>] + 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* [T<sub>3</sub>]是对T<sub>3</sub>的值取整 */<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>5</sub>:   if i > T<sub>3</sub> goto B<sub>12</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>6</sub>:   T<sub>4</sub> := i<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>5</sub> := addr(A)<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>4</sub>:= 2 * T<sub>4</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
   if T<sub>5</sub>[T<sub>4</sub>] goto B<sub>8</sub><br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 B<sub>7</sub>:     goto B<sub>11</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>8</sub>:   j := 2 * i<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>9</sub>:   if j > N goto B<sub>11</sub>&nbsp;&nbsp; /* 第三个for语句 */<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>10</sub>:  T<sub>6</sub> := j<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;
      T<sub>7</sub> := addr(A)<br>
      &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      T<sub>6</sub> := 2 * T<sub>6</sub><br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;
      T<sub>7</sub>[T<sub>6</sub>] = false<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;
      j := j + i<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;
      goto B<sub>9</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>11</sub>:  i := i + 1<br>
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;
      goto B<sub>5</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
B<sub>12</sub>:
<p>（2）根据四元式的中间代码，可划分成基本块B<sub>1</sub>，B<sub>2</sub>，B<sub>3</sub>，B<sub>4</sub>，B<sub>5</sub>，B<sub>6</sub>，B<sub>7</sub>，B<sub>8</sub>，B<sub>9</sub>，B<sub>10</sub>，B<sub>11。</sub>其程序流图如下：

   <p align = "center"><img src="images/e9.5a.gif"></p>
   
   考察上面的程序流图：<br>
   &nbsp;&nbsp;&nbsp;
   D(B<sub>3</sub>)  = { B<sub>1</sub>, B<sub>2</sub>, B<sub>3</sub> } 又有 B<sub>3</sub> -> B<sub>2</sub>，因此 B<sub>3</sub> -> B<sub>2</sub> 是一条回边。根据它找到的循环 L<sub>1</sub> = { B<sub>2</sub>, B<sub>3</sub> }。<br>
   &nbsp;&nbsp;&nbsp;
   D(B<sub>10</sub>) = { B<sub>1</sub>, B<sub>2</sub>, B<sub>4</sub>, B<sub>5</sub>, B<sub>6</sub>, B<sub>9</sub>, B<sub>10</sub> }，又有 B<sub>10</sub> -> B<sub>9</sub>，所以 B<sub>10</sub> -> B<sub>9</sub> 是一条回边。根据这条回边找到循环 L<sub>2</sub> = { B<sub>9</sub>, B<sub>10</sub> }。<br>
   &nbsp;&nbsp;&nbsp;
   D(B<sub>11</sub>) = { B<sub>1</sub>, B<sub>2</sub>, B<sub>4</sub>, B<sub>5</sub>, B<sub>6</sub>,  B<sub>9</sub>, B<sub>11</sub> }，又有 B<sub>11</sub> -> B<sub>5</sub>，因此 B<sub>11</sub> -> B<sub>5</sub> 是一条回边。根据这条回边找到循环 L<sub>3</sub> = { B<sub>11</sub>, B<sub>9</sub>, B<sub>10</sub>, B<sub>8</sub>, B<sub>7</sub>, B<sub>6</sub>, B<sub>5</sub> }<br>
   
   （3）进行代码外提<br>
&nbsp &nbsp 把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和删除无用赋值。结果程序流图如下：
      <p align = "center"><img src="images/e9.5b.gif"></p>
   （4）进行强度削弱和删除归纳变量后，其程序流图如下：
      <p align = "center"><img src="images/e9.5c.gif"></p>


</body></html><br>
</p>
<html><script language="JavaScript">

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -