Building a control-flow graph from an AST with a visitor pattern using Java

I'm trying to figure out how to implement my LEParserCfgVisitor class as to build a control-flow graph from an Abstract-Syntax-Tree already generated with JavaCC. I know there are tools that already exist, but I'm trying to do it in preparation for my Compilers final.

I know I need to have a data structure that keeps the graph in memory, and I want to be able to keep attributes like IN, OUT, GEN, KILL in each node as to be able to do a control-flow analysis later on.

My main problem is that I haven't figured out how to connect the different blocks together, as to have the right edge between each blocks depending on their nature: branch, loops, etc. In other words, I haven't found an explicit algorithm that could help me build my visitor.

Here is my empty Visitor. You can see it works on basic langage expressions, like if, while and basic operations (+,-,x,^,...)

public class LEParserCfgVisitor implements LEParserVisitor { public Object visit(SimpleNode node, Object data) { return data; } public Object visit(ASTProgram node, Object data) { data = node.childrenAccept(this, data); return data; } public Object visit(ASTBlock node, Object data) { } public Object visit(ASTStmt node, Object data) { } public Object visit(ASTAssignStmt node, Object data) { } public Object visit(ASTIOStmt node, Object data) { } public Object visit(ASTIfStmt node, Object data) { } public Object visit(ASTWhileStmt node, Object data) { } public Object visit(ASTExpr node, Object data) { } public Object visit(ASTAddExpr node, Object data) { } public Object visit(ASTFactExpr node, Object data) { } public Object visit(ASTMultExpr node, Object data) { } public Object visit(ASTPowerExpr node, Object data) { } public Object visit(ASTUnaryExpr node, Object data) { } public Object visit(ASTBasicExpr node, Object data) { } public Object visit(ASTFctExpr node, Object data) { } public Object visit(ASTRealValue node, Object data) { } public Object visit(ASTIntValue node, Object data) { } public Object visit(ASTIdentifier node, Object data) { } }

Can anyone give me a hand?


-------------Problems Reply------------

To do reasoning about data flows (gen/kill/use/def) you first need a control flow graph.

To construct one, at each tree node (e.g., inside each specific node visitor), build the piece of the graph that the node represents; pass the entry point arc and the exit arc for that graph to the parent "visitor". Purely independent vistors won't work because you need to pass information to parents. [You could add entry/exit arcs slots to each node that are set by the visitor, and inspected by the parent.]

Some nodes (e.g., for "assignmentstmt") will manufacture an action node referring to the AST for the assignment (think "rectangle" in a flowchart); there aren't any subgraph arcs to worry about. Some nodes (e.g., for "if") will manufacture a conditional branch node (referencing the AST node for the condition expression), (think "diamond" in a flowchart), an flow-join node, and compose a structured (if-then-else) subgraph by combining that conditional branch node with the subgraphs for the then and else clauses (represented just by then entry and exit arcs), with the flow join-node. You then pass the entry and exit arcs to this compound subgraph to the parent.

This scheme works with structured control flow. Unstructured control flow (e.g, "GOTO x") requires some funny adjustments, e.g, first building the structured part of the graph, associating generated control flow with labels, and then going back and patcing the GOTO actions to have an arc to the associated label.

Remember to worry about exceptions; they are GOTOs too, but generally to a point higher in the structured control flow graph. These are often handled by passing the innermost exception handler node down the tree; now your visitors need to look up the tree to see that most recent exception handler.

A more sophisticated scheme that uses generated vistors is called an attribute grammar, which essentially manages all the information flows for you, by passing the values of interest (in this case, entry/exit/exception flow arcs) up and down the tree as parameters and results. You need an attribute grammar tool to do this; and you still have to specify node-building logic. We use attribute grammars and essentially the above control flow graph construction by pieces with our DMS Software Reengineering Toolkit to provide generic control flow analysis facilities for many languages.

Once you have the control flow graph, then you can implement a data flow solver of the type you describe by walking over the control flow graph. You'll need to re-visit the ASTs that the CF nodes point-to to collect the raw use/raw def information.

If your langauge has only structured control flow, then you can use the ASTs nodes to represent the control flow nodes, and compute the data flow directly.

More details on the general process can be found here.

Category:java Views:2 Time:2010-12-19

Related post

  • Building a Control-flow Graph using results from Objdump 2010-11-25

    I'm attempting to build a control-flow graph of the assembly results that are returned via a call to objdump -d . Currently the best method I've come up with is to put each line of the result into a linked list, and separate out the memory address, o

  • How could I generate Java CFG(Control Flow Graph) using antlr? 2012-04-03

    I am trying to analyse Java code sturcture. So, I generated a Java parser and lexer by using ANTLRv3 and java grammar code... but I don't know how could I generate Context Flow Graph using the generated parser and lexer. I tried to learn how to do th

  • Need help to draw control-flow graph with GLEE and C# 2009-11-08

    I am trying to draw a control-flow graph(CFG) from source code using the GLEE graph library and C# language. Problem is, I am new to GLEE. I need a tutorial or sample programs/projects to help me get started quickly with GLEE. The source for which I

  • Antlr - Control Flow Graph 2011-06-14

    Is it possible to build a control flow graph for a Java program using Antlr? Are there any resources out there that provide guidelines on doing so? Is there a better approach than using Antlr or are there any kind of eclipse tools that might help? --

  • Java code for converting C program to Control Flow Graph 2010-06-20

    I require a java code for converting a C program into a control flow graph. Can any one please help me out with it? --------------Solutions------------- July 12th is going to be a tough deadline to meet, but you can do it. Here is the general strateg

  • Are there any static Call-Graph and/or Control-Flow-Graph API for JavaScript? 2011-03-22

    Are there any Call-Graph and/or Control-Flow-Graph generators for JavaScript? Call Graph - Control Flow Graph - EDIT: I am looking specifically for a static tool

  • Get Control flow graph from Abstract Syntax Tree 2008-09-18

    I have an AST derived from the ANTLR Parser Generator for Java. What I want to do is somehow construct a control flow graph of the source code, where each statement or expression is a unique Node. I understand there must be some recursiveness to this

  • Formally constructing Control Flow Graph 2010-09-01

    Im writing a compiler for university project, and I would like to transform my Abstract Syntax Tree into a Control Flow Graph(CFG). Im thinking that the nodes(V) in the CFG should be nodes from the AST. I know algorithmically how to construct the edg

  • Java Control Flow Graphs Library 2011-11-14

    I need to manipulate control flow graphs for Java code in a project. What might be a good java library to generate control flow graphs in Java. So far I have found a couple eclipse plugins (heavily dependent on eclipse APIs) and standalone tools (can

  • Annotatable Control Flow Graph with Boost? 2009-07-23

    I have a control flow graph representing a single procedure of my intermediate language code. Nodes and Edges are annotated via vertex/edge properties and contain instructions resp branch information. Now I want to perform data flow analysis on this

  • how to generate control flow graph for a c program by gcc version 3.4.5? 2010-08-20

    Hi to every one I couldn't generate a control flow graph for a c program by gcc3.4.5. if it is possible help me to generate cfg. I use the following commands but I couldn't find the cfg file. $ gcc -o -dv prog.c -o prog result: unrecognized command l

  • control flow graph generator for c# code 2010-11-17

    i need a tool that takes c# code and generate the control flow graph of the code if there's something like this in visual studio ............ do please point it out to me thanks --------------Solutions------------- right-click, Generate Sequence Diag

  • Can we generate Control flow graph of the c program by Turbo C compiler? 2011-02-17

    Can we generate Control flow graph of the c program by Turbo C compiler? I want to know that there is something given by the compiler to generate a CFG of a C program. --------------Solutions------------- Don't think Turbo C has this feature. Though,

  • control flow graph of a c program to find worst possible path 2011-04-15

    Are there any tools, libraries, or frameworks to get the control flow graph of a C program, and find the worst possible path a program can take? When I read the other questions related to control flow graphs, I came across a few tools which can gener

  • What is the easiest way to generate a Control Flow-Graph for a method in Python? 2011-06-01

    I am writing a program that tries to compare two methods. I would like to generate Control flow graphs (CFG) for all matched methods and use either a topological sort to compare the two graphs. --------------Solutions------------- PyPy offers a way o

  • Search In paths of the control flow graph 2011-06-14

    Many times I'm having a problem with printing in function foo, and I want to look for all occurences of Print in code which is reachable in the Control Flow Graph from function foo. Or in all code in the paths between foo and bar (as I verified an as

  • open source code for extracting API call sequences and control flow graphs from assembly code 2012-04-08

    Is there any open source code for extracting API call sequences and control flow graphs from assembly code? I use a disassembler to come up with the assembly code of a PE file first. And now I need to extract the API call sequences and of course the

  • Constructing an object graph from a flat DTO using visitor pattern 2011-06-02

    I've written myself a nice simple little domain model, with an object graph that looks like this: -- Customer -- Name : Name -- Account : CustomerAccount -- HomeAddress : PostalAddress -- InvoiceAddress : PostalAddress -- HomePhoneNumber : TelephoneN

  • Control flow graph of a program 2011-04-07

    I'm taking a compiler class right now and we're at the point where we have to build a CFG in order to implement optimizations. One thing I can't figure out is how many CFGs are there for a program? Every example I ever see seems to be the CGF of a si

Copyright (C), All Rights Reserved.

processed in 0.066 (s). 11 q(s)