1

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

Update1：​​我的问题是我不明白从哪里开始。从互联网上，我应该使用访问者模式遍历 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
        }
    ]

}
4

1 回答 1

7

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

您不一定必须使用访问者模式。访问者模式是当您的抽象语法树由类层次结构中的节点实例描述时使用的方法。从 AST 到 CFG 的转换比这更普遍。抽象语法树是一种抽象数据类型，是树的特例。与任何其他抽象数据类型一样，它可以以多种方式表示。你如何做并不重要，但你唯一需要做的就是遍历这棵树。您使用的迭代方法取决于您使用的语言。这应该回答您的问题 2/：JSON 字符串可能是 AST 的表示。AST 是一种抽象数据类型，而 JSON 字符串是这种抽象数据类型的实现。

在 JSON 中，您可以拥有值、数组或（键、值）关联集。我可能会假设您的 AST 节点将是一组（键，值）关联。我还假设这些节点中的每一个都有一个名为的键type，可让您识别它是哪种节点。

如果我是正确的，这回答了这个问题：为什么你不需要访问者模式。访问者模式允许我们提取每个节点的类型。（这就是所谓的“双重调度”）但是在这里，您不需要它，因为每个节点的类型都在type字段中进行了编码。

通常，从 AST 到 CFG 的转换是通过使用一组函数来完成的：一个函数用于 AST 中的每种类型的节点。这些函数中的每一个都需要编写与它作为参数的节点关联的 CFG 部分。它将递归调用子节点的转换函数。（在 OO-AST 的情况下，这就是访问者模式会做的事情）

例如，您将拥有一个函数ConvertNode。该函数将读取type节点的字段，并与节点调用相应的转换函数。你的根节点有 type app。然后该ConvertNode函数将分派给该ConvertApp函数。ConvertApp将读取一些字段，例如name并将遍历things数组并调用ConvertNode每个节点。然后再次ConvertNode将调用分派给适当的函数。

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

于 2013-02-25T12:01:41.450 回答