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

Question

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

Im думает, что узлы (V) в CFG должны быть узлами из AST. Я знаю, алгоритмический, как построить множество ребер (G=(V,E)), но Im трудное время написания процесса немного более формально

Я создал этот шаблон стиля 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 
) 

и обеспечивают edgeset как:

{ i1 -> ia1, 
    i1 -> ia2, 
    ia1 -> a1, 
    ia2 -> a1, 
    a1 -> a2, 
    a2 -> i2, 
    i2 -> i2r1 
    i2-> i2a1 
    i2a1 -> i2r2 
    i2r2 -> _|_ 
    i2r1 -> _|_ 
} 

DotSrc

Кто есть какие-либо намеки на то, как сделать это немного более формально, чем Скала «псевдокод»?

Im думая что-то индуктивное, как:

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

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

EDIT :

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

EDIT2:

Я прошел через Дракона книги и «Современные Compiler внедрения в ML», а также некоторые другие вещества из Learning to write a compiler и некоторых/большинства упоминает поток данных и поток управления, но не касается многое, КАК создать CFG любым формальным способом.

EDIT3:

Via Kiama автора, Associate Professor Dr. Tony Sloane я получил некоторые additional book references to look up.

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

Answer 1

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

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

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

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

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

Answer 2

Google's Closure Compiler реализует Control-Flow Analysis, который преобразует AST для JavaScript в диаграмму потока управления. Идеи для этой реализации основаны на документе: Declarative Intraprocedural Flow Analysis of Java Source Code.