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

Question

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

Я думаю, что узлы (V) в CFG должныбыть узлами из АСТ.Я алгоритмически знаю, как построить набор ребер (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]]

(приведенное выше даст толькодерево, а не график. Нет ребра от края тогдашней ветви до следующего оператора, например)

РЕДАКТИРОВАТЬ:

Я читал о Киама и потоки данных для scala, и мне нравится «succ» и «следующий» подход, который они используют.Тем не менее, мне тяжело свести это к более формальному описанию, в основном из-за изящных childAttr, s.next, которые скрывают некоторые детали, которые становятся некрасивыми, когда я пытаюсь определить это формально.

EDIT2:

Я прошел через Книгу Дракона и "Реализацию современного компилятора в ML", а также некоторые другие материалы из Учимся писать компилятор и некоторые /большинство упоминает поток данных и поток управления, но никогда особо не касается того, КАК создавать CFG каким-либо формальным способом.

EDIT3:

Через Kiama автор, Доцент д-р Тони Слоун Я получил дополнительных ссылок на книги для поиска .

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

Answer 1

Компилятор Google Closure реализует Анализ потока управления , который преобразует AST для JavaScript в график потока управления. Идеи этой реализации основаны на статье: Декларативный внутрипроцедурный анализ потока исходного кода Java .

Answer 2

Если вы намереваетесь просто создать что-то, что выглядит немного более формальным, то вы можете выразить эти операции сопоставления как правила вывода, используя стандартную запись .Вы должны выразить это в виде одного шага сокращения, а не рекурсивно, потому что тогда достаточно просто продолжать применять эти правила до тех пор, пока не будет применено больше.

Тем не менее, это определение, по сути, будетсказать точно так же, как ваш код Scala.Если вы действительно хотите сделать что-то «формальное», вам необходимо доказать следующие свойства:

• Ваш алгоритм перевода CFG всегда завершается
• Минимален ли ваш CFG по отношению к данному ASTinput
• Имеется ли уникальный CFG, выводимый вашим алгоритмом для заданного ввода AST (т. е. не является недетерминированным, какой CFG он производит).

Я не думаю, что вашПодход с использованием базовых блоков (а не подход с утверждением) также является плохой идеей.Кажется совершенно разумным, что если вы можете сопоставить базовый блок, вы можете написать правило, которое делает утверждения о членстве в наборе на основе наличия этого совпадения.Кажется, что индуктивное определение, которое вы начали рисовать, может работать просто отлично.

Что-то еще интересное может быть попыткой связать (формально) структурированную операционную семантику и вашу конструкцию CFG.Возможно, уже есть работа в этой области, но я только сделал краткий поиск в Google и не нашел четко заявленных отношений между ними, но интуитивно кажется, что он должен существовать.