正式构建控制流图

Question

我正在为大学项目编写一个编译器,我想将我的抽象语法树转换为控制流图(CFG).

我认为VCFG 中的nodes()应该是来自AST的节点.我在算法上知道如何构造边集(G=(V,E))但我很难正式地编写过程

我创建了这个scala样式模式匹配(Pseudo):

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-branch的边缘到next语句的边缘)

编辑:

我一直在阅读scala的kiama和数据流,我喜欢他们使用的"succ"和" follow "方法.然而,我很难把它煮成更正式的描述,主要是因为它很漂亮childAttr,s.next当我试图正式指定它时隐藏了一些变得丑陋的细节.

EDIT2:

我已经阅读了Dragon Book和"ML中的现代编译器实现"以及学习编写编译器和一些/大多数提及数据流和控制流的其他一些材料,但从未涉及如何创建CFG以任何正式方式.

EDIT3:

通过Kiama作者,副教授Tony Sloane博士,我收到了一些额外的书籍参考资料.

据我所知,根据这些书的"方法"是基于程序的"per语句"而不是AST,并且基于Basic Blocks.不过还有很棒的输入!

Answer 1

Google 的闭包编译器实现了控制流分析，它将 JavaScript 的 AST 转换为控制流图。此实现的想法灵感来自于论文：Java 源代码的声明式程序内流分析。

Answer 2

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

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

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

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

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