Формальное построение графа потока управления

Я пишу компилятор для университетского проекта, и я хотел бы преобразовать свое абстрактное синтаксическое дерево в граф потока управления (CFG).

Я думаю, что узлы ( V ) в CFG должны быть узлами из 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 и потоках данных для scala, и я как и подходы «succ» и «follow», которые они используют. Тем не менее, мне трудно свести это к более формальному описанию, в основном из-за изящных childAttr , s. next , который скрывает некоторые детали, которые становятся уродливыми, когда я пытаюсь указать это формально.

EDIT2:

Я прошел через Dragon Book и «Современную реализацию компилятора в ML», а также некоторые из другой материал из Обучение написанию компилятора и некоторые / большинство упоминают поток данных и поток управления, но никогда особо не затрагивают КАК создать CFG каким-либо формальным способом.

EDIT3:

Via Киама автор, доцент доктор Тони Слоан Я получил несколько дополнительных ссылок на книги, чтобы найти .

Насколько я могу видеть «путь к do it »согласно этим книгам, основывается на« на каждый оператор »программы больше, чем на AST, и основывается на базовых блоках. Тем не менее, отличный вклад!