正式構建控制流程圖

Question

爲大學項目編寫編譯器，我想將我的抽象語法樹轉換爲控制流圖（CFG）。

我認爲CFG中的節點（V）應該是來自AST的節點。我知道算法如何構建邊集（G=(V,E)），但有一個很難寫的過程有點更正式林

我創造了這個斯卡拉風格模式匹配（僞）：

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

任何人有關於如何做到這一點更正式超過斯卡拉「僞」任何提示？

即時通訊思想的東西電感，如：

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 for scala，我喜歡他們使用的「succ」和「follow」方法。儘管如此，我還是很難將這些描述轉化爲更爲正式的描述，主要是因爲漂亮的childAttr,s.next，它隱藏了一些細節，當我嘗試正式地指定它時會變得很難看。

EDIT2：

我經歷過的龍書和「現代編譯器實現在ML」，以及從Learning to write a compiler一些其他的材料和一些/最提到的數據流和控制流，但從來沒有接觸如何以任何正式的方式創建CFG。

EDIT3：

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

就我所見，根據這些書的「實現方法」基於程序的「每語句」而不是AST，並基於基本塊。不過輸入很大！

Answer 1

如果您的意圖是簡單地創建看起來更正式的東西，那麼您可以使用standard notation將這些匹配操作表示爲推理規則。你應該用一個簡化的步驟來表達它，而不是遞歸地表達，因爲這樣就可以繼續應用這些規則，直到不能再應用爲止。

也就是說，這個定義基本上和你的scala代碼完全一樣。如果你真的想要做什麼「正式」你需要證明的屬性是：

• 你CFG翻譯算法總是終止
• 無論您的CFG是最小相對於給定的AST輸入
• 是否有是由您的算法爲給定的AST輸入推導的獨特的CFG（即，它不是非確定性的，它產生的CFG）。

我不認爲你的基本塊的方法（而不是每個語句的方法）也是一個壞主意。看起來完全合理的是，如果你可以匹配一個基本塊，你可以編寫一個規則，根據這個匹配的存在來作出關於設置成員資格的斷言。看起來你開始繪製草圖的歸納定義可能工作得很好。

還有一件有趣的事情可能是嘗試將（正式）structured operational semantics與您的CFG建設聯繫起來。這方面可能已經有工作了，但我只做了粗略的谷歌搜索，沒有發現兩者之間有任何明確的關係，但直覺上它似乎應該存在。

Answer 2

Google's Closure Compiler實現了一個Control-Flow Analysis，它將JavaScript的AST轉換爲控制流圖。這個實現的想法來自於這篇論文：Declarative Intraprocedural Flow Analysis of Java Source Code。