CODEWITHSUNDEEP
python-3.xgrammarcontrol-flow-graphlark-parser
Ben Claude
Ben Claude

Reputation: 21

How to get a control flow graph of a program?

I want to get a control flow graph of a code/program (be it any programming language and given its grammar). I have tried using lark library in python to parse a basic C sample program [I provided the grammar for basic c syntax to lark]. As a result, it gave me an object of parse tree or similar sort of stuff, now I am wondering where to proceed.

Having said that, any kind of new approach is highly appreciated. The prime goal is to get the control flow graph of a code/program, given the grammar of the language in which it is written.

Upvotes: 2

Views: 2008

Answers (1)

sepp2k
sepp2k

Reputation: 370425

As a result, it gave me an object of parse tree or similar sort of stuff, now I am wondering where to proceed.

A common approach is to

  1. walk the tree to generate an intermediate representation in which all looping and conditional constructs are replaced with jumps,
  2. divide the instructions of the IR into basic blocks by starting a new block before each jump label and after each jump and then
  3. construct a control flow graph where the basic blocks are the nodes, each block that doesn't end with a jump has an edge to the block that comes after it, and each block that does end with a jump has an edge to the possible jump targets (where the jump targets for a traditional conditional jump instruction would include the following block).

The prime goal is to get the control flow graph of a code/program, given the grammar of the language in which it is written.

You can't get the CFG of a program if all you know about the language is its grammar. You'll need some understanding of the semantics of the language to be able to construct a CFG.

Upvotes: 3

Related Questions