1

由于stackexchange没有更多关于编译器标签的标签，所以我在这里发布这个问题。

如果同时满足以下三个条件，则称变量 x 在程序中的语句 Si 处有效：

1. There exists a statement Sj that uses x
2. There is a path from Si to Sj in the flow
   graph corresponding to the program
3. The path has no intervening assignment to x 
   including at Si and Sj

在此处输入图像描述

在上述控制流图的基本块 2 中的语句和基本块 3 中的语句中都存在的变量是

  1. p, s, 你
  2. r、s、u
  3. r，你
  4. q, v

我试图解释：

正如维基百科所说：“简单地说：如果变量具有将来可能需要的值，则该变量是活动的。”

根据所讨论的定义，如果将来在任何新分配之前使用变量，则该变量是活动的。块 2 将 'r' 和 'v' 都作为实时变量。因为它们在分配给它们的任何新值之前在块 4 中使用。请注意，变量 'u' 不在块 2 中，因为 'u' 在块 3 中使用之前在块 1 中分配了一个新值。变量 'p'、's' 和 'q' 也不存在于块中2 出于同样的原因。块 3 只有 'r' 作为实时变量，因为每个其他变量在使用前都被分配了一个新值。

另一种解释为：

只有 r。

p、s 和 u 被分配到 1 中，在此之前没有中间使用它们。因此 p、s 和 u 不在 2 和 3 中。q 被分配到 4 中，因此不在 2 和 3 中。

v 在 3 时有效，但在 2 时无效。只有 r 在 2 和 3 时都有效。

但是官方的 GATE 键同时表示 r 和 u。

4

1 回答 1

0

我看到两件事可能至少是你困惑的一部分。

首先，在实时变量的条件列表中，没有限制说明Si != Sj，所以这使得定义在我看来有点不精确。

第二个是您的断言“请注意，变量 'u' 不在块 2 中，因为 'u' 在块 3 中使用之前在块 1 中分配了一个新值。”

我看这个的方式是这样的：

  1. 进入块 2 后，在执行语句之前（想象插入一个空语句作为每个块的入口，另一个作为块的出口），那么两者和 都必须是活动的，因为存在即将到来的语句两者都使用，并且代码中有一条从条目到该语句的路径，其中不包含任何中间分配。而不是想象这些额外的空语句，使用定义的原始语义，然后我们只讨论 where 的情况，因为两者都引用v = r + uru Si == Sjv = r + u 语句 - 从语句到自身的路径通常不包含任何额外的赋值。不过，我发现使用额外的空 entry 和 exit 语句更容易考虑它。

  2. 然而，在执行之后v = r + u，在虚构的块 exit empty 语句处，现在可以安全地认为它是u不活跃的（或者，死的），因为块 4 中没有任何东西使用它，并且在块 1 中重新分配它之前再次使用它块 2 或 3。

因此，部分困惑似乎是在考虑变量是否存在于特定块中，这与定义并不真正符合 - 您需要考虑变量是否存在于特定语句的点。您可以假设变量u在块 2 中既是活动的又是死的，这取决于您是在执行单独的语句之前查看它，还是在......

于 2015-10-22T14:17:33.907 回答