如何从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）

回答

相关问题