📄 9.7.7.1b.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.7.7.1.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.7.1c.htm'" ></img></td>
</tr>
</table>
<br><br>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
<font class = "definition">算法9.11 寻找归纳变量</font>
</p>
<p>
输入：有到达_定值信息和循环不变信息的循环L。
</p>
<p>
输出：一组归纳变量，联系到每个归纳变量j的是三元组（i，c，d），其中i是基本归纳变量，c和d是常量，在j的定值点，j的值是c*i+d,则说j属于i族。基本归纳变量i也属于它自己的族。
</p>
<p>
方法：
</p>
<p>
(1) 扫描L的语句，找出所有基本归纳变量。在这里使用循环不变计算的信息。对应每个基本归纳变量的是三元组（i，1，0）。
</p>
<p>
(2) 寻找L中只有一个赋值的变量K，它有下面形式之一
</p>
<p align="center">     k:=j*b， k:=b*j， k:=j/b， k:=j±b， k:=b±j
</p>
<p>其中b是常数，j是归纳变量，基本的或非基本的。
<p>
如果j是基本的，那么k在j族中，k的三元组依赖于定义它的指令，例如,若k由k:=j*b定义，那么k的三元组是（j，b，0）。其余情况的三元组也可类似定义。
</p>
<p>
如果j不是基本的，它属于i族，那么附加的要求是：
</p>
<p>
（a） 在循环L中对j的唯一赋值和对k的赋值之间的路径上没有对i的赋值，且
</p>
<p>
（b） L外没有j的定值可到达k。
</p>
<p>
常见的情况是k和j属同一块中的临时变量，比较容易检查出这种情况。更一般的情况；通过分析L的流图来决定哪些块（因而哪些定值）位于对j和对k的赋值之间的路径上，到达_定值信息将提供需要的这种检查。
</p>
<p>
从j的三元组（i，c，d）和对k定值的指令来计算k的三元组。例如，定值k:=b*j使得（i，b*c，b*d）作为k 的三元组。b*c和b*d可以在这种分析时完成，因为b、c，和d都是常量。
</p>
<p>
一旦找出一族归纳变量，可以修改计算归纳变量的指令，改为用加或减而不是乘。用执行较快的指令代替执行较慢的指令叫做<font class = "definition2">强度削弱</font>。
</p>
<table>
<tr>
<td><font class="yanshi">观看演示 </font></td>
<td><font color=blue onmouseover="javascript:style.cursor='hand'" onclick="javascript:open('applet/9772/Page1.htm','_blank','menu=no,toolbar=no,location=no,directories=no,status=no,scrollbars=yes,resizable=yes,copyhistory=no,left=100,top=100,width=800,height=600')">寻找归纳变量、强度削弱</font></td>
<td><img src="../images/yanshi.gif"></img></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.7.7.1.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.7.1c.htm'" ></img></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -