CODEWITHSUNDEEP
c++cparsingabstract-syntax-tree
Hari Krishna
Hari Krishna

Reputation: 551

How to write a C or C++ program to detect modules in another C program, using a syntax tree

I'm working on a project where I have to divide a C program into modules and find the time taken for the execution of each module. I have to use C or C++ to do this.

For example: the first module will be main() then inside you may have other modules like for, or while or if etc.

It's actually like generating a syntax tree for the program, in a textual form.

So what I'm looking for is a way to do this, or any framework which can assist me with this, or any suggestions, anything would be great!

Thanks in advance :)

EDIT:

and ok, il make it more clear, by giving the sample input and the expected output as mentioned by our institute,

Input: 

  void main() { 
       int h=2,j=5,k=1;
       while (h>j) {
          h++; 
          for (k=100;k>0;k/=2) { 
             if (i<=5) {
                d=n*10;
                p=n/10;
             } 
          }
        }
   }

Output: 

  main 
  begin
  h=2
  j=5
  k=1
  *************
  while 
  h>j 
  0.2087
  ************* 
  begin
  h++
  *************
  for 
  k=100 
  k>0 
  k/2
  0.8956
  ************* 
  begin
  if i<=5
  *************
  begin
  d=n*10
  p=n/10
  0.1153
  end
  *************
  end
  end

sorry for the output, its vertical, i think it gives every1 a clear idea ! :) –

Upvotes: 2

Views: 798

Answers (2)

persiflage
persiflage

Reputation: 1204

What you're describing is a profiler. Which one is suitable very much depends on the platform which you're using.

For Window and Visual C++ I've found LTProf to be lightweight, inexpensive and usable http://www.lw-tech.com/index.php?option=com_content&task=view&id=25&Itemid=65. Alternatively the higher end Visual Studio products include a profiler and Intel sell various profilers.

Alternatively are you trying to write your own profiler? That's quite a tricky piece of code to write and very platform dependent. You may find open source examples to use as starting points.

EDIT: NB: Using ltprof may require you to turn off compiler optimization to get reliable profiling results. Be aware that this can potentially change the results.

Upvotes: 0

Ira Baxter
Ira Baxter

Reputation: 95392

Being less than 100 lines doesn't help you much; people can write a program that uses every feature of C language (and the compiler extensions!) in a program that size. So you are saying you have to deal with the entire C language (statements, expressions, functions, structures, typedefs, macros, preprocessor conditionals, ...). If this is a school project, I think that's too hard; you will need to limit your project to a interesting subset, say, functions, assignments, while statements and function calls.

What you need to do this straightforwardly is

  • A parser for the C language
  • The ability to climb over the AST
  • The ability to patch the AST
  • The ability to emit the AST as source text

Program transformations system are nearly ideal engines to accomplish this kind of work. These allow you to additionally do pattern-directed changes to the AST, which makes this much easier to implement.

You can probably do this with TXL or Stratego; I'm sure both have C parsers that will handle the limited subset of C that you should be willing to do.

You could do with this our DMS Software Reengineering Toolkit, although this is probably not suited for student use in short period of time. (TXL and Stratego are free, but might have steep learning curves, too).

But you will find this document on instrumenting code to build test coverage tools probably an ideal introduction to what you need to do to accomplish your task with a transformation system.

EDIT: I transcribed Hari's comment with an example into his question.

I think he wants a tracer not a profiler.

He can do that using instrumentation, but he'll have a lot of instrumentation to insert because it looks like the goal is tracing every action.

In that case, it would be easier if he had an interpreter, but he needs one that keeps the code structure around so that he can report the code structure as it runs (so CINT which compiles to a pcode wouldn't be the right answer).

What he needs is full C parsing to AST with symbol tables, an interpreter that executes the ASTs, and a prettyprinter so that he can convert appropriate parts of the AST he is currently executing back into text to report as progress.

DMS is still a very good foundation for this, as it has all the machinery needed to support this task too. Parse the C text, build the symbol table (all built into DMS for C) and then run a custom interpreter. This is easily coded as an interpreter over the AST; a big case statement over the tree node types would be the interpreter core, with node-type specific cases carrying out the action implied by the AST node (including climbing up or down the tree, updating symbol table entries with new values, computing expression intermediate results, and of course reporting progress.

ANTLR might work; it has a C parser but I'm not so sure about a prettyprinter. The interpreter would work pretty much the same way.

TXL and Stratego would likely be awkward for this, as it isn't clear how you'd use their pure-transformational style to alternatate interpreting and printing trace data.

Upvotes: 1

Related Questions