如何从JSON对象(AST)构建控制流图(CFG)

Question

我想从以JSON格式给出的AST构建控制流图(CFG).所以这个AST是在TouchDevelop中针对每个脚本自动创建的.而且由于TouchDevelop不是面向对象的编程,我还可以使用访问者模式吗？任何有用的指针将不胜感激.

Update1:我的问题是我不明白从哪里开始.从互联网上,我应该使用访问者模式来浏览AST以访问每个节点并收集信息.从那里,我可以构建一个CFG,然后进行数据流分析.但有两个问题:

1)据我所知,我需要面向对象的编程模型,使用访问者模式,(我可能是错的),这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节点将是(键,值)关联的集合.我还假设这些节点中的每一个都有一个名为key的键type,允许您识别它是什么类型的节点.

如果我是正确的,这回答了这个问题:为什么你不需要访客模式.访问者模式允许我们提取每个节点的类型.(这就是所谓的"双重调度")但是在这里,你不需要它,因为每个节点的类型都在type字段中编码.

通常,从AST到CFG的转换是通过使用一组函数完成的:AST中每种类型节点的一个函数.这些函数中的每一个都需要编写与其作为参数的节点相关联的CFG部分.它将递归调用子节点的转换函数.(这是访问者模式会做的,如果是OO-AST)

例如,你将拥有一个功能ConvertNode.此函数将读取type节点的字段,并使用该节点调用相应的转换函数.您的根节点有类型app.然后该ConvertNode函数将调度到该ConvertApp函数.ConvertApp将读取一些字段name,并将迭代things数组并调用ConvertNode每个节点.然后再次ConvertNode将调用发送到适当的函数.

调用这些转换函数的方式完全遵循AST结构.迭代树时如何创建CFG取决于输入语言.每个转换函数都可以返回CFG的构造节点或转换,以允许调用者重用它.或者调用者可以将节点或转换作为参数传递,以允许被调用函数从那里继续构造.您可以自由选择合适的方式来构建CFG并打破一般规则:可以通过巧妙的方式简化构造.