Tools/CodeTools/TianoTools/Pccts/h/ast.c

   1 /* Abstract syntax tree manipulation functions
   2  *
   3  * SOFTWARE RIGHTS
   4  *
   5  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
   6  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
   7  * company may do whatever they wish with source code distributed with
   8  * PCCTS or the code generated by PCCTS, including the incorporation of
   9  * PCCTS, or its output, into commerical software.
  10  *
  11  * We encourage users to develop software with PCCTS.  However, we do ask
  12  * that credit is given to us for developing PCCTS.  By "credit",
  13  * we mean that if you incorporate our source code into one of your
  14  * programs (commercial product, research project, or otherwise) that you
  15  * acknowledge this fact somewhere in the documentation, research report,
  16  * etc...  If you like PCCTS and have developed a nice tool with the
  17  * output, please mention that you developed it using PCCTS.  In
  18  * addition, we ask that this header remain intact in our source code.
  19  * As long as these guidelines are kept, we expect to continue enhancing
  20  * this system and expect to make other tools available as they are
  21  * completed.
  22  *
  23  * ANTLR 1.33
  24  * Terence Parr
  25  * Parr Research Corporation
  26  * with Purdue University and AHPCRC, University of Minnesota
  27  * 1989-2000
  28  */
  29
  30 #include "pcctscfg.h"
  31
  32 #ifdef PCCTS_USE_STDARG
  33 #include "pccts_stdarg.h"
  34 #else
  35 #include <varargs.h>
  36 #endif
  37
  38 /* ensure that tree manipulation variables are current after a rule
  39  * reference
  40  */
  41
  42 void
  43 #ifdef __USE_PROTOS
  44 zzlink(AST **_root, AST **_sibling, AST **_tail)
  45 #else
  46 zzlink(_root, _sibling, _tail)
  47 AST **_root, **_sibling, **_tail;
  48 #endif
  49 {
  50         if ( *_sibling == NULL ) return;
  51         if ( *_root == NULL ) *_root = *_sibling;
  52         else if ( *_root != *_sibling ) (*_root)->down = *_sibling;
  53         if ( *_tail==NULL ) *_tail = *_sibling;
  54         while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right;
  55 }
  56
  57 AST *
  58 #ifdef __USE_PROTOS
  59 zzastnew(void)
  60 #else
  61 zzastnew()
  62 #endif
  63 {
  64         AST *p = (AST *) calloc(1, sizeof(AST));
  65         if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);
  66         return p;
  67 }
  68
  69 /* add a child node to the current sibling list */
  70 void
  71 #ifdef __USE_PROTOS
  72 zzsubchild(AST **_root, AST **_sibling, AST **_tail)
  73 #else
  74 zzsubchild(_root, _sibling, _tail)
  75 AST **_root, **_sibling, **_tail;
  76 #endif
  77 {
  78         AST *n;
  79         zzNON_GUESS_MODE {
  80         n = zzastnew();
  81 #ifdef DEMAND_LOOK
  82         zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
  83 #else
  84         zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
  85 #endif
  86         zzastPush( n );
  87         if ( *_tail != NULL ) (*_tail)->right = n;
  88         else {
  89                 *_sibling = n;
  90                 if ( *_root != NULL ) (*_root)->down = *_sibling;
  91         }
  92         *_tail = n;
  93         if ( *_root == NULL ) *_root = *_sibling;
  94         }
  95 }
  96
  97 /* make a new AST node.  Make the newly-created
  98  * node the root for the current sibling list.  If a root node already
  99  * exists, make the newly-created node the root of the current root.
 100  */
 101 void
 102 #ifdef __USE_PROTOS
 103 zzsubroot(AST **_root, AST **_sibling, AST **_tail)
 104 #else
 105 zzsubroot(_root, _sibling, _tail)
 106 AST **_root, **_sibling, **_tail;
 107 #endif
 108 {
 109         AST *n;
 110         zzNON_GUESS_MODE {
 111         n = zzastnew();
 112 #ifdef DEMAND_LOOK
 113         zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
 114 #else
 115         zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
 116 #endif
 117         zzastPush( n );
 118         if ( *_root != NULL )
 119                 if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root;
 120         *_root = n;
 121         (*_root)->down = *_sibling;
 122         }
 123 }
 124
 125 /* Apply function to root then each sibling
 126  * example: print tree in child-sibling LISP-format (AST has token field)
 127  *
 128  *      void show(tree)
 129  *      AST *tree;
 130  *      {
 131  *              if ( tree == NULL ) return;
 132  *              printf(" %s", zztokens[tree->token]);
 133  *      }
 134  *
 135  *      void before() { printf(" ("); }
 136  *      void after()  { printf(" )"); }
 137  *
 138  *      LISPdump() { zzpre_ast(tree, show, before, after); }
 139  *
 140  */
 141 void
 142 #ifdef __USE_PROTOS
 143 zzpre_ast(
 144           AST *tree,
 145           void (*func)(AST *),   /* apply this to each tree node */
 146           void (*before)(AST *), /* apply this to root of subtree before preordering it */
 147           void (*after)(AST *))  /* apply this to root of subtree after preordering it */
 148 #else
 149 zzpre_ast(tree, func, before, after)
 150 AST *tree;
 151 void (*func)(),   /* apply this to each tree node */
 152          (*before)(), /* apply this to root of subtree before preordering it */
 153          (*after)();  /* apply this to root of subtree after preordering it */
 154 #endif
 155 {
 156         while ( tree!= NULL )
 157         {
 158                 if ( tree->down != NULL ) (*before)(tree);
 159                 (*func)(tree);
 160                 zzpre_ast(tree->down, func, before, after);
 161                 if ( tree->down != NULL ) (*after)(tree);
 162                 tree = tree->right;
 163         }
 164 }
 165
 166 /* free all AST nodes in tree; apply func to each before freeing */
 167
 168 #if 0
 169 ////void
 170 ////#ifdef __USE_PROTOS
 171 ////zzfree_ast(AST *tree)
 172 ////#else
 173 ////zzfree_ast(tree)
 174 ////AST *tree;
 175 ////#endif
 176 ////{
 177 ////    if ( tree == NULL ) return;
 178 ////    zzfree_ast( tree->down );
 179 ////    zzfree_ast( tree->right );
 180 ////    zztfree( tree );
 181 ////}
 182 #endif
 183
 184 /*
 185    MR19 Optimize freeing of the following structure to limit recursion
 186    SAKAI Kiyotaka (ksakai@isr.co.jp)
 187 */
 188
 189 /*
 190          NULL o
 191              / \
 192            NULL o
 193                / \
 194             NULL NULL
 195 */
 196
 197 /*
 198    MR21 Another refinement to replace recursion with iteration
 199    NAKAJIMA Mutsuki (muc@isr.co.jp).
 200 */
 201
 202 void
 203 #ifdef __USE_PROTOS
 204 zzfree_ast(AST *tree)
 205 #else
 206 zzfree_ast(tree)
 207 AST *tree;
 208 #endif
 209 {
 210
 211     AST *otree;
 212
 213     if (tree == NULL) return;
 214
 215     while (tree->down == NULL || tree->right == NULL) {
 216
 217         if (tree->down == NULL && tree->right == NULL) {
 218             zztfree(tree);
 219             return;
 220         }
 221
 222         otree = tree;
 223         if (tree->down == NULL) {
 224             tree = tree->right;
 225         } else {
 226             tree = tree->down;
 227         }
 228         zztfree( otree );
 229     }
 230
 231     while (tree != NULL) {
 232         zzfree_ast(tree->down);
 233         otree = tree;
 234         tree = otree->right;
 235         zztfree(otree);
 236     }
 237 }
 238
 239 /* build a tree (root child1 child2 ... NULL)
 240  * If root is NULL, simply make the children siblings and return ptr
 241  * to 1st sibling (child1).  If root is not single node, return NULL.
 242  *
 243  * Siblings that are actually siblins lists themselves are handled
 244  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
 245  * in the tree ( NULL A B C D ).
 246  *
 247  * Requires at least two parameters with the last one being NULL.  If
 248  * both are NULL, return NULL.
 249  */
 250 #ifdef PCCTS_USE_STDARG
 251 AST *zztmake(AST *rt, ...)
 252 #else
 253 AST *zztmake(va_alist)
 254 va_dcl
 255 #endif
 256 {
 257         va_list ap;
 258         register AST *child, *sibling=NULL, *tail=NULL /* MR20 */, *w;
 259         AST *root;
 260
 261 #ifdef PCCTS_USE_STDARG
 262         va_start(ap, rt);
 263         root = rt;
 264 #else
 265         va_start(ap);
 266         root = va_arg(ap, AST *);
 267 #endif
 268
 269         if ( root != NULL )
 270                 if ( root->down != NULL ) return NULL;
 271         child = va_arg(ap, AST *);
 272         while ( child != NULL )
 273         {
 274                 for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
 275                 if ( sibling == NULL ) {sibling = child; tail = w;}
 276                 else {tail->right = child; tail = w;}
 277                 child = va_arg(ap, AST *);
 278         }
 279         if ( root==NULL ) root = sibling;
 280         else root->down = sibling;
 281         va_end(ap);
 282         return root;
 283 }
 284
 285 /* tree duplicate */
 286 AST *
 287 #ifdef __USE_PROTOS
 288 zzdup_ast(AST *t)
 289 #else
 290 zzdup_ast(t)
 291 AST *t;
 292 #endif
 293 {
 294         AST *u;
 295
 296         if ( t == NULL ) return NULL;
 297         u = zzastnew();
 298         *u = *t;
 299 #ifdef zzAST_DOUBLE
 300         u->up = NULL;           /* set by calling invocation */
 301         u->left = NULL;
 302 #endif
 303         u->right = zzdup_ast(t->right);
 304         u->down = zzdup_ast(t->down);
 305 #ifdef zzAST_DOUBLE
 306         if ( u->right!=NULL ) u->right->left = u;
 307         if ( u->down!=NULL ) u->down->up = u;
 308 #endif
 309         return u;
 310 }
 311
 312 void
 313 #ifdef __USE_PROTOS
 314 zztfree(AST *t)
 315 #else
 316 zztfree(t)
 317 AST *t;
 318 #endif
 319 {
 320 #ifdef zzd_ast
 321         zzd_ast( t );
 322 #endif
 323         free( t );
 324 }
 325
 326 #ifdef zzAST_DOUBLE
 327 /*
 328  * Set the 'up', and 'left' pointers of all nodes in 't'.
 329  * Initial call is double_link(your_tree, NULL, NULL).
 330  */
 331 void
 332 #ifdef __USE_PROTOS
 333 zzdouble_link(AST *t, AST *left, AST *up)
 334 #else
 335 zzdouble_link(t, left, up)
 336 AST *t, *left, *up;
 337 #endif
 338 {
 339         if ( t==NULL ) return;
 340         t->left = left;
 341         t->up = up;
 342         zzdouble_link(t->down, NULL, t);
 343         zzdouble_link(t->right, t, up);
 344 }
 345 #endif