生成程序片段(程序依赖图PDG)

生成程序片段
标准方法是：
基于依赖性分析的切片。
使用程序依赖图表示依赖。
从中生成切片。
我们将专注于这种方法。但是，还有其他选择。

程序依赖图 The Program Dependence Graph (PDG)
表示数据和控制依赖项：一些元素已经从数据流测试中看到。
它可以作为构建切片的基础。PDG 可能构成其他分析的基础
注意：这是程序内的，如果我们需要扩展它处理多个过程或方法（获取系统依赖关系图）。 我们不会看这个。

PDG 是一个有向图，其中：顶点代表语句（例如赋值和
控制谓词）, 有一个唯一的起始节点, 边代表控制和数据依赖
注意：我们假设我们只处理“结构化”语言，我们不会考虑指针。

PDG的控制依赖
每个控制依赖边都有标签 true 或 false。
控制依赖边 n1 -> n2 表示：
如果 n1 被执行并取边上的值（真或假），则 n2 必须在稍后的某个时间被执行。
如果 n1 被执行并且没有取边上的值，n2 可能永远不会执行。

假设我们有一个 if 语句，其谓词 p 由节点 n1 表示。
假设其 then 和 else 部分分别对应节点 n2 和 n3。
从 n1 到 n2 有一个控制边，标签为 true。
从 n1 到 n3 有一条控制边，标签为 false。

假设我们有一个 while 循环，其谓词 p 由节点 n1 表示。
从 节点1到节点3存在控制依赖性（标签为true）。

数据依赖Data Dependence
有两种类型的数据依赖边：
流依赖边
无序依赖边def-order dependence edges
对于切片，我们不需要 def-order 边，也不会包括他们。

流依赖边Flow Dependence Edges
如果满足以下条件，则存在从 n1 到 n2 的流依赖边：
n1 表示对变量 x 的一些赋值； n2 引用 x 的值； 对于 x，从 n1 到 n2 有一个明确的路径定义。
注意：如果它们在循环中，定义清晰的路径可能从一个顶点到一个“较早”的顶点。


语句3和语句1之间存在依赖关系，语句3和语句2之间也存在依赖关系。

语句 3 对语句 1 的依赖性是因为变量 x 的值在语句 3 中被修改 (x = x - 1)，并且该修改后的值被用于语句 1 中 while 循环的条件表达式中 (while (x > 0)). 语句 3 中 x 的更新会影响语句 1 中的循环条件。
同样，语句 3 与语句 2 之间存在依赖关系。语句 3 中 x 的更新值 (x = x - 1) 用于计算语句 2 中的 y (y = y + x)。

examples:

second example:

third example:

让我们分析具有给定初始值的代码片段：
x = 2, y = 5

1. 输入语句取x和y的初始值。

2. while 循环检查 x 是否大于 0 (x > 0)。 在这种情况下，因为 x 是 2，所以条件为真，程序继续执行下一条语句。

3. if 语句比较 x 和 y。 这里，x 为 2，y 为 5。由于 x 不大于 y，程序执行 else 块。

4. 在 else 块中，y 减 1 (y = y - 1)。 因为 y 最初是 5，所以 y 变成了 4。

5. if-else 块执行后，x 减 1 (x = x - 1)。 x 最初为 2，因此 x 变为 1。

6. 程序回到 while 循环并检查 x 是否大于 0。由于 x 仍然大于 0 (x = 1)，循环继续。

7. 再次执行if语句，比较x和y。 在这种情况下，x (1) 不大于 y (4)，因此执行 else 块。

8. 在 else 块中，y 减 1 (y = y - 1)。 因为 y 是 4，所以 y 变成了 3。

9. x 减 1 (x = x - 1)。 x 为 1，所以 x 变为 0。

10. 程序回到 while 循环。 这次，x 不大于 0 (x = 0)，因此循环终止。

11. 最后执行输出语句，输出y的值。 在这种情况下，y 为 3。

因此，对于给定的初始值 x = 2 和 y = 5，代码片段的输出将为 3。