静态分析-如何从JSON对象(AST)构建控制流图(CFG)

Question

我想从JSON格式的AST构建一个控制流图（CFG）。因此，这个AST是在TouchDevelop中针对每个脚本自动创建的。既然TouchDevelop不是面向对象编程，我还能使用Visitor模式吗？任何有用的指示都将不胜感激。

Update1:我的问题是不知道从哪里开始。在互联网上，我应该使用Visitor Pattern遍历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
        }
    ]
}

Answer 1

我还没有找到对TouchDevelop脚本语言的引用。我不知道你能用它做什么，不能做什么。

您不一定要使用访问者模式。访问者模式是当抽象语法树由类层次结构中的节点实例描述时使用的方法。从AST到CFG的转换比这更通用。抽象语法树是一种抽象的数据类型，是树的一种特殊情况。与任何其他抽象数据类型一样，它可以用多种方式表示。你怎么做并不重要，但你唯一需要做的就是在这个树上迭代。迭代方法取决于您使用的语言。这应该可以回答您的问题2/：JSON字符串可能是AST的表示。AST是一种抽象数据类型，而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并打破一般规则：可能有一些巧妙的方法可以简化构建。