c - 在静态分析中寻找循环迭代器

Question

我们如何在静态分析中找到循环迭代器？变量成为迭代器的不同条件是什么？

在像 for(i = 0; i < n; i++); 这样的 super 简化的 for 循环中我们可以假设，lhs 的初始化表达式是迭代器。但是我们如何在 while 循环或更复杂的 for 循环中找到迭代器呢？

我准备好了以下概念:

• 达到定义
• 范围值
• 控制流程图

Answer 1

通常没有循环迭代器。例如，单个 iterator 变量可能不够用(例如，可以同时从两端遍历数组)，循环的终止可能取决于外部数据(例如，用户输入)，并且有一些有用的无限循环(迭代器无用)。

然而，一些启发式方法可用于识别迭代器 表达式。对于循环，它们经常会表达两个属性:progress 和termination。进度通常与同一变量的更新有关，其值取决于该变量，例如:

i++; // For indexed structures
p = p -> next; // For linked structures

终止通常与进度表达式与某个常量(意思是“循环的常量”)的比较有关，例如:

i <= n; // For scalar values
p == null; // For pointers

通常可以有多个进度表达式，因此可以有多个终止常量，并且可以在终止表达式中使用多个进度变量。

因此，基本策略是:

1. 从循环的退出条件收集所有变量。
2. 检查它们中的哪些在循环体中被修改并依赖于它们自己。

但请记住，有些循环没有进度表达式，有些没有终止条件，变量更新可以是间接的并且存在别名。