language-agnostic - 正式构建控制流程图

我正在为大学项目编写编译器，我想将我的抽象语法树转换为控制流图(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]]

(尽管上面仅给出了树，但没有给出图。例如，从那么分支的边缘到下一条语句没有边缘)

编辑:

我一直在阅读kiama and dataflows中的scala，我喜欢他们使用的“succ”和“following”方法。但是，我很难把它简化成更正式的描述，主要是因为漂亮的childAttr，s.next隐藏了当我尝试正式指定它时会变得丑陋的一些细节。

编辑2:

我已经看过《 Dragon Book》和“ML中的现代编译器实现”，以及Learning to write a compiler的其他一些 Material ，并且某些/最常提及的是数据流和控制流，但是从没有以任何形式接触过如何创建CFG的内容。办法。

编辑3:

通过Kiama作者Associate Professor Dr. Tony Sloane，我收到了一些additional book references to look up。

据我所知，这些书中的“执行方法”是基于程序的“每个语句”，而不是基于AST，并且基于基本块。尽管如此，输入还是很棒的!

最佳答案

如果您只是想创建看起来更正式的内容，则可以使用standard notation将这些匹配操作表示为推理规则。您应该以简化的单个步骤来表达它，而不是以递归的方式表达它，因为这样一来，只需继续应用这些规则，直到无法应用更多的内容就足够了。

就是说，这个定义实际上将与您的Scala代码说的完全一样。如果您真的想做任何“正式”的事情，那么您需要证明的属性是:

您的CFG转换算法始终会终止

对于给定的AST输入，您的CFG是否最小

对于给定的AST输入，您的算法是否有唯一的CFG派生(即，它不确定生成哪个CFG)。

我也不认为您的基本街区方法(而不是按陈述的方法)也不是一个坏主意。如果可以匹配基本块，则可以编写一个规则，该规则基于此匹配的存在来声明有关集合成员身份，这似乎是完全合理的。您开始绘制的归纳定义似乎可以正常工作。

其他有趣的事情可能是尝试(正式地)将structured operational semantics与您的CFG构造相关联。在这方面可能已经有工作了，但是我只是在谷歌上进行了一次粗略的搜索，没有发现两者之间有任何明确说明的关系，但直觉上似乎应该存在一个。

关于language-agnostic - 正式构建控制流程图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3616950/