Re: Tree analysis for C programs.

Anne Trotin <atrotin@aigle.saclay.cea.fr> writes:
> I need to make a tree of (big) C-ANSI programs for some further
> formal controls such as invariant properties in loops for instance.
> I'd like that tree to be built according to a C parser, and I'd also
> like to achieve semantic analyses in order to generate nodes for
> 'cast' when necessary. Such things must have been done somewhere for
> compilers... I've had a look at GCC, but it seems to be much too
> complex for what I want to do. Furthermore, many optimizations are
> achieved, the tree built during parsing is only done
> statement-by-statement and then freed, and, more important, it is not
> built for control structures such as loops or conditional expressions
> (if...).
>
> If somebody can give me pointers to simple C-analyzers, or perhaps to
> very old compilers (without any kind of optimization), or even only
> advice... I would greatly appreciate it.


If it is essential to keep the entire syntax tree of a program in memory,
then one thing that has worked for me might work for you, too. Let us look
at the C grammar in the yacc format. The following piece of yacc rules
with associated actions show how the syntax trees are built.


%%
translation_unit_start : translation_unit
{ int i;
traverse($1);
}
;


translation_unit : external_declaration
{ $$=gl(gi(translation_unit1),$1,NIL); }
| translation_unit external_declaration
{ $$=gl(gi(translation_unit2),$1,$2,NIL); }
;


external_declaration : function_definition
{ $$=gl(gi(external_declaration1),$1,NIL); }
| declaration
{ $$=gl(gi(external_declaration2),$1,NIL); }
;


function_definition : declarator compound_statement
{ $$=gl(gi(function_definition1),$1,$2,NIL); }
| declarator declaration_list compound_statement
{ $$=gl(gi(function_definition2),$1,$2,$3,NIL); }
| declaration_specifiers declarator
compound_statement
{ $$=gl(gi(function_definition3),$1,$2,$3,NIL); }
| declaration_specifiers declarator
declaration_list compound_statement
{ $$=gl(gi(function_definition4),$1,$2,$3,$4,NIL);
}
;




Each node is provided with a unique tag. Function gl is pretty much
similar to Lisp's list function. Functions gi generates an atom (which is
the tag). Function traverse does whatever you want to do with the tree. I
used this approach for implementing language transformation and automatic
program generation. It seems appropriate for optimization, too. This
approach gives a full freedom in handling trees. Some subtrees can be
deallocated, transformed, stored, etc.


Regards,
Alex Sakharov
--

Return to the comp.compilers page.
Search the comp.compilers archives again.