如何從JSON對象（AST）構建控制流圖（CFG）

我想從JSON格式的AST中構建控制流圖（CFG）。所以這個AST是在TouchDevelop中針對每個腳本自動創建的。由於TouchDevelop不是面向對象的編程，我仍然可以使用Visitor模式嗎？任何有用的指針，將不勝感激。如何從JSON對象（AST）構建控制流圖（CFG）

更新1：我的問題是，我不明白從哪裏開始。從互聯網上，我應該使用訪問者模式來瀏覽AST訪問每個節點並收集信息。從那裏，我可以建立一個CFG，然後進行數據流分析。但有兩個問題：

1）AFAIK，我需要面向對象的編程模型來使用訪問者模式，（我可能是錯的），哪個TouchDevelop不是。

2）下面給出的AST不是AST格式，因爲我在互聯網上找到。它採用JSON格式。我想我可以解析JSON以將其轉換爲期望的AST結構，但我不太確定。示例腳本

meta version "v2.2,nothing"; 
meta name "DivideByZero"; 
// 
meta platform "current"; 

action main() { 
    (5/0)→post_to_wall; 
}

得到的AST（JSON格式）的

的源代碼下面給出：

{ 
    "type":"app", 
    "version":"v2.2,nothing", 
    "name":"DivideByZero", 
    "icon":null, 
    "color":null, 
    "comment":"", 
    "things":[ 
     { 
      "type":"action", 
      "name":"main", 
      "isEvent":false, 
      "outParameters":[ 
      ], 
      "inParameters":[ 
      ], 
      "body":[ 
       { 
        "type":"exprStmt", 
        "tokens":[ 
         { 
          "type":"operator", 
          "data":"(" 
         }, 
         { 
          "type":"operator", 
          "data":"5" 
         }, 
         { 
          "type":"operator", 
          "data":"/" 
         }, 
         { 
          "type":"operator", 
          "data":"0" 
         }, 
         { 
          "type":"operator", 
          "data":")" 
         }, 
         { 
          "type":"propertyRef", 
          "data":"post to wall" 
         } 
        ] 
       } 
      ], 
      "isPrivate":false 
     } 
    ] 

}

來源

2013-02-24 Junaid Mohsin

我不明白，如果你的問題是從AST轉換到CFG或使用的格式（JSON）或方便使用CFG或簡單地TouchDevelop。你能否在你的問題上更具體些？ – 2013-02-24 14:01:30

我已經更新了這個問題。請看一看。 – 2013-02-24 22:43:11

我沒有找到的TouchDevelop腳本語言的參考呢。我不知道你可以用它做什麼以及你不能做什麼。

您不必使用訪客模式。訪問者模式是抽象語法樹由類層次結構中的節點實例描述時使用的方法。從AST到CFG的轉換比這更一般。抽象語法樹是一種抽象數據類型，tree的特例。像任何其他抽象數據類型一樣，它可以用多種方式表示。不管你怎麼做，但你需要做的唯一事情就是遍歷這棵樹。你所用的迭代方法取決於你使用的語言。這應該回答你的問題2：一個JSON字符串可能是一個AST的表示。 AST是abstract data type，而JSON字符串是該抽象數據類型的實現。

在JSON中，您可以擁有值，數組或一組（鍵，值）關聯。我可以假設你的AST節點將是（鍵，值）關聯集。我也假設，每個節點都有一個名爲type的密鑰，它允許您識別它是什麼類型的節點。

如果我是正確的，這就回答了一個問題：爲什麼你不需要訪問者模式。訪問者模式允許我們提取每個節點的類型。（這就是所謂的「雙派」）但是在這裏，你不需要它，因爲每個節點的類型在type字段中被編碼。

通常，從AST到CFG的轉換是通過使用一組函數完成的：AST中每種節點的一個函數。這些函數中的每一個都需要編寫與其所需節點相關的CFG部分作爲參數。它將遞歸調用子節點的轉換函數。（在OO-AST的情況下，訪問者模式會這樣做）

例如，您將有一個功能ConvertNode。該功能將讀取節點的type字段，並用節點調用相應的轉換函數。您的根節點的類型爲app。然後ConvertNode函數將調度到ConvertApp函數。ConvertApp將讀取一些字段，如name，並將遍歷things數組，併爲這些節點中的每個節點調用ConvertNode。然後ConvertNode再次將呼叫分派給適當的功能。

這些轉換函數的調用方式完全遵循AST結構。在遍歷樹時如何創建CFG取決於輸入語言。每個轉換函數都可以返回CFG的構造節點或轉換，以允許調用者重用它。或者調用者可以傳遞一個節點或者過渡作爲參數來允許被調用函數從那裏繼續構造。您可以自由選擇合適的方式來構建CFG並打破一般規則：可能會巧妙地簡化構造。

來源

2013-02-25 12:01:41

如何從JSON對象（AST）構建控制流圖（CFG）

回答

相關問題