1
$\begingroup$

I'm trying to build a complexity analysis tool and I need an algorithm for constructing the control flow graph (to get cyclomatic and eventually essential complexity). I couldn't find any pseudocode online so I just got down to writing it. Using recursion seems to have been a bad way to go; my code handles most simple cases but with deeper nesting of control structures errors arise.

Is there somewhere I can find pseudocode for constructing the CFG?

(For the curious I'm doing this for VHDL.)

$\endgroup$
3
  • $\begingroup$ Standard compiler textbooks should describe how to build a CFG. Which ones have you looked at so far? $\endgroup$
    – D.W.
    Commented Jun 5, 2017 at 22:40
  • $\begingroup$ Compilers, dragon book is my favorite. I have never heard about tools generating CFGs. As for parsers from CFGs, then GNU Bison and friends. $\endgroup$
    – fade2black
    Commented Jun 5, 2017 at 22:52
  • $\begingroup$ @fade2black This question is about control flow graphs, not context-free grammars. $\endgroup$ Commented Jun 6, 2017 at 1:50

1 Answer 1

1
$\begingroup$

To create a CFG you begin with an Abstract Syntax Tree (AST). So I assume you have an AST available. The first step is to collect the nodes in the tree into basic blocks. This step is optional but reduces the number of nodes in the CFG which improves performance. So if you have the source code:

if a:
    x = x + 1
    print(b)
else:
    while c:
        print(d)
    y = y + 1

you get a tree structure of basic blocks (here denoted BB):

[(BB(if a:), [
    [(BB(x = x + 1, print(b)), [])]
    [(BB(while c:), [
        (BB(print(d)), [])
    ]), (BB(y = y + 1), [])]
])]

Note that the if-statement has two children lists and the while-statement has one. Note also that every successor of a block is either the first element in a children list or "follows" the block. Thus,

succ(BB(while c:)) = [BB(print(d)), BB(y = y + 1)]

cause the first block is the body of the loop and the second block the block reached after exiting the loop.

Given the tree above, we can create a recursive algorithm that computes the successors of every block:

def connect(tree, parent):
    tails = [parent] if parent else []
    for bb, children in tree:
        for t in tails:
            succ[t].append(bb)
        if type(bb) == if-block:
            if_tails = connect(children[0], bb)
            else_tails = connect(children[1], bb)
            tails = if_tails + else_tails
        elif type(bb) == while-block:
            tails = connect(children[0], bb)
            for t in tails:
                succ[t].append(bb)
            tails = [bb]
        else:
            tails = [bb]
    return tails

The "tails" are the predecessors of the next block to operate on. The algorithm becomes a bit hairier when you involve other kinds of control flow like continue, break, and exceptions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.