正式构建控制流图

Question

我正在为大学项目编写编译器，并希望将我的抽象语法树转换为控制流图(CFG)。

我认为CFG中的节点(V)应该是AST中的节点。我知道如何算法地构造边集(G=(V,E))，但我很难更正式地编写这个过程。

我已经创建了这个Scala风格的模式匹配(伪代码)：

def edges(n:Node)(nestedin_next: Node) : List[(Node,Node)] = 
    n match {
       case (c_1 :: c_2::tl) => (c1,c2) :: edges(c2::tl)(nestedin_next)++
                                   edges(c_1)(c_2)//recurse
       case c_1 :: Nil => (c_1,nestedin_next)::Nil
       case  i@ IF(_,c1,c2) => (i,c1)::(i,c2)::edges(c1)(nestedin_next)++
                                edges(c2)(nestedin_next)
       case _ => Nil
     }

这应该与 AST 结构匹配：

( IF(1,
       ASSIGN(x,1), // ia1
       ASSIGN(x,2) // ia2
     ) ::  // i1
  ASSIGN(y,2) ::  // a1
  ASSIGN(z,ADD(x,y)) :: //a2 
  IF(z, 
       RET(z), //i2r1
         assign(z,0):: // i2a1
         ret(z) // i2r2
  ) :://i2
   Nil
)

并提供一个类似于边集的东西：

{ i1 -> ia1,
   i1 -> ia2,
   ia1 -> a1,
   ia2 -> a1,
   a1 -> a2,
   a2 -> i2,
   i2 -> i2r1
   i2-> i2a1
   i2a1 -> i2r2
   i2r2 -> _|_
   i2r1 -> _|_ 
}

DotSrc

有人知道如何比scala "伪代码"更正式地完成这个任务吗？

我在想一些归纳的东西:

e[[ IF(_,b1,b2) ]] = (if -> b1) + (if -> b2) \cup e[[ b1 ]] \cup e[[ b2 ]]
e[[ b1, b2 ]] = e[[b1]] \cup e[[b2]]

(上述仅提供树形结构，而不是图形结构。例如，没有从then分支的边缘到下一个语句的边)

编辑：

我一直在阅读与Scala相关的Kiama和Dataflows，我喜欢他们使用的“succ”和“following”方法。尽管如此，我很难将其简化为更正式的描述，主要是由于巧妙的childAttr，s.next隐藏了一些在我试图正式指定时变得丑陋的细节。

编辑2：

我已经通过《龙书》、《现代编译器实现ML版》以及学习编写编译器的一些/大部分材料，但几乎没有涉及如何以任何正式方式创建CFG。

编辑3：

通过Kiama作者副教授Dr. Tony Sloane，我收到了一些其他参考书目。

据我所见，这些书中所说的“做法”更多地基于程序的“每个语句”，而不是基于AST，并且基于基本块。尽管如此，这是很好的输入！

- svrist

---

希望你不介意我在标签中添加了“scala”。 - Randall Schulz

@Randall 没有啊 :) 我差点就这么做了。 - svrist

Answer 1

Google's Closure Compiler 实现了一个 控制流分析，它将 JavaScript 的 AST 转换为控制流图。这个实现的灵感来自于论文：Java 源代码的声明性程序内部流分析。

- namin

---

啊哈！Kiama 基于 JastAdd，且这篇论文使用了 JastAdd。Kiama 的数据流示例看起来非常相关于论文中使用的方法。谢谢。 - svrist

Answer 2

如果您的意图只是创建一个看起来更正式的东西，那么您可以使用标准符号将这些匹配操作表达为推理规则。您应该用单步约简的术语来表达它，而不是递归地表达它，因为然后只需简单地应用这些规则，直到不能再应用为止。

话虽如此，这个定义本质上会与您的scala代码说出完全相同的事情。如果你真的想做任何“正式”的事情，你需要证明的属性是：

- 您的CFG转换算法总是终止。 - 您的CFG是否相对于给定的AST输入是最小的。 - 是否存在唯一的CFG可由您的算法推导出给定的AST输入(即它不是非确定性的，它产生了哪个CFG)。

我认为你的基本块方法(而不是每个语句的方法)并不一定是一个坏主意。如果你能匹配一个基本块，你可以编写一个规则，根据这个匹配的存在，对集合成员身份进行断言。你开始勾勒的归纳定义似乎可以很好地工作。

还有一些有趣的事情可以尝试(正式地)将结构化操作语义和您的CFG构造联系起来。可能已经有关于这个领域的工作，但我只进行了一个粗略的谷歌搜索，并没有找到两者之间明确的关系，但直观上看，应该存在一种关系。

- Gian

---

非常好的输入！关于操作语义（和推理规则），它们最近一直在我脑海中，所以你提到它很有趣。 - svrist