Re: Tree analysis for C programs. (Alexander Sakharov)
Mon, 23 May 1994 14:34:55 GMT

          From comp.compilers

Related articles
Tree analysis for C programs. (Anne Trotin) (1994-05-20)
Re: Tree analysis for C programs. (1994-05-20)
Re: Tree analysis for C programs. (1994-05-22)
Re: Tree analysis for C programs. (1994-05-23)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Alexander Sakharov)
Keywords: C, parse, analysis
Organization: MOTOROLA
References: 94-05-079
Date: Mon, 23 May 1994 14:34:55 GMT

Anne Trotin <> 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;

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
{ $$=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.

Alex Sakharov

Post a followup to this message

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