10

我为大学项目编写编译器，我想将我的抽象语法树转换为控制流图（CFG）。

我认为VCFG 中的节点（）应该是来自 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 -> _|_ 
}

CFG(点) 点Src

有人对如何比scala“伪代码”更正式地执行此操作有任何提示吗？

我在想一些归纳的东西，比如：

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

（上面只会给出一棵树而不是一个图。例如，从分支的边缘到下一条语句没有边缘）

编辑：

我一直在阅读kiama 和scala 的数据流，我喜欢他们使用的“succ”和“following”方法。然而，我很难将其归结为更正式的描述，主要是因为漂亮的childAttr，s.next它隐藏了一些当我尝试正式指定它时变得丑陋的细节。

编辑2：

我已经阅读了 Dragon Book 和“现代编译器在 ML 中的实现”以及学习编写编译器的其他一些材料，并且一些/大部分提到了数据流和控制流，但从未涉及如何创建CFG 以任何正式的方式。

编辑3：

通过Kiama的作者、副教授 Tony Sloane 博士，我收到了一些额外的参考书目来查找。

据我所见，这些书籍的“方法”是基于程序的“每个语句”而不是基于 AST，并且基于基本块。尽管如此，伟大的投入！

4

2 回答 2

5

Google 的 Closure Compiler实现了控制流分析，它将 JavaScript 的 AST 转换为控制流图。此实现的想法灵感来自论文：Java 源代码的声明性过程内流分析。

于 2010-09-04T18:37:30.503 回答
3

如果您的意图是简单地创建一些看起来更正式的东西，那么您可以使用标准表示法将这些匹配操作表示为推理规则。你应该用一个单一的减少步骤来表达它，而不是递归的，因为这样就足够了，简单地继续应用这些规则，直到不能再应用。

也就是说，这个定义本质上和你的 scala 代码完全一样。如果你真的想做任何“正式”的事情，你需要证明的属性是：

  • 您的 CFG 翻译算法总是终止
  • 对于给定的 AST 输入，您的 CFG 是否最小
  • 对于给定的 AST 输入，您的算法是否有唯一的 CFG 可导出（即，它产生的 CFG 不是不确定的）。

我也不认为您的基本块方法（而不是每个语句的方法）一定是一个坏主意。如果你可以匹配一个基本块，你可以编写一个规则，根据这个匹配的存在来断言集合成员资格，这似乎是完全合理的。您开始绘制的归纳定义似乎可以正常工作。

其他有趣的事情可能是尝试将（正式）结构化的操作语义与您的 CFG 构造联系起来。这方面可能已经有工作了，但我只是粗略地用谷歌搜索了一下，并没有发现两者之间有任何明确的关系，但直觉上似乎应该存在一个。

于 2010-09-04T15:45:29.867 回答