How to build a Control Flow Graph (CFG) from a JSON object (AST)

Question

I want to build a control flow graph (CFG) from an AST given in JSON format. So this AST is automatically created in TouchDevelop against each script. And since TouchDevelop is not Object Oriented programming, can I still use the Visitor pattern? Any useful pointers would be appreciated.

Update1: My problem is that I don't understand where to start. From the internet, I am supposed to use Visitor Pattern to walk through AST to visit each node and collect information. And from there, I can build a CFG and then do Data Flow analysis. But there are two issues:

1) AFAIK, I need object oriented programming model to use Visitor Pattern, (I might be wrong) which TouchDevelop is NOT.

2) The AST as given below is not in AST format as I find on the internet. It's in JSON format. I think I could parse the JSON to convert it into the desired AST structure, but I am not so sure.

Source code of a sample script

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

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

Resulting AST (JSON formatted) is given below:

{
    "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
        }
    ]

}

I don't understand if your problem is related to the transformation from the AST to the CFG or to the format used (JSON) or to the convenient usage of a CFG or simply to TouchDevelop. Could you please be a bit more specific in your question ? — Valentin Perrelle, Feb 24 '13 at 14:01

score 7 · Accepted Answer · answered Feb 25 '13 at 12:01

I didn't find a reference to the TouchDevelop scripting language yet. I don't know what you can do with it and what you can't.

You don't necessarily have to use a visitor pattern. Visitor patterns is the method used when your abstract syntax tree is described by instances of nodes from a class hierarchy. The conversion from AST to CFG is more general than that. An abstract syntax tree is an abstract data type, a special case of tree. Like any other abstract data type, it can be represented in many ways. It doesn't matter how you do it, but the only thing you need to do, is to iterate over this tree. And the iteration method you have depend on the language you are using. This should answer your question 2/: a JSON string may be a representation of an AST. The AST is an abstract data type while the JSON string is an implementation of this abstract data type.

In JSON, you can have values, arrays or sets of (key,value) associations. I can probably assume that your AST nodes will be the set of (key,value) associations. I assume as well, that each of these nodes have a key named type which allow you to identify what kind of node it is.

If I am correct, this answer the question: why you don't need a visitor pattern. A visitor pattern allows us to extract the type of each node. (this is what is called "double dispatch") But here, you don't need it since the type of each node is encoded in the type field.

Typically, the conversion from AST to CFG is done by using a set of functions: one function for each type of node in the AST. Each of these functions need to write the CFG part associated with the node it takes as parameter. It will recursively call conversion functions for the children nodes. (This is what a visitor pattern would do, in case of OO-AST)

For instance, you'll have a function ConvertNode. This function will read the type field of a node, and call the according conversion function with the node. Your root node have type app. Then the ConvertNode function will dispatch to the ConvertApp function. ConvertApp will read some fields like name and will iterate over the things array and call ConvertNode for each of these nodes. Then again ConvertNode will dispatch the call to the appropriate function.

The way those conversion functions will be called follow exactly the AST structure. How the CFG is created when you iterate over the tree is dependent of the input language. Each of the conversion function may return a constructed node or transition of your CFG to allow the caller to reuse it. Or the caller might pass a node or transition as parameter to allow the called function to continue the construction from there. You are free to choose the appropriate way to build the CFG and to break the general rules: there may clever ways to simplify the construction.

How to build a Control Flow Graph (CFG) from a JSON object (AST)

1 Answers1