pd.if.org Git - pccts/blob - 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-1995
  28  */
  29 #ifdef __STDC__
  30 #include <stdarg.h>
  31 #else
  32 #include <varargs.h>
  33 #endif
  34
  35 /* ensure that tree manipulation variables are current after a rule
  36  * reference
  37  */
  38 void
  39 #ifdef __STDC__
  40 zzlink(AST **_root, AST **_sibling, AST **_tail)
  41 #else
  42 zzlink(_root, _sibling, _tail)
  43 AST **_root, **_sibling, **_tail;
  44 #endif
  45 {
  46         if ( *_sibling == NULL ) return;
  47         if ( *_root == NULL ) *_root = *_sibling;
  48         else if ( *_root != *_sibling ) (*_root)->down = *_sibling;
  49         if ( *_tail==NULL ) *_tail = *_sibling;
  50         while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right;
  51 }
  52
  53 AST *
  54 #ifdef __STDC__
  55 zzastnew(void)
  56 #else
  57 zzastnew()
  58 #endif
  59 {
  60         AST *p = (AST *) calloc(1, sizeof(AST));
  61         if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);
  62         return p;
  63 }
  64
  65 /* add a child node to the current sibling list */
  66 void
  67 #ifdef __STDC__
  68 zzsubchild(AST **_root, AST **_sibling, AST **_tail)
  69 #else
  70 zzsubchild(_root, _sibling, _tail)
  71 AST **_root, **_sibling, **_tail;
  72 #endif
  73 {
  74         AST *n;
  75         zzNON_GUESS_MODE {
  76         n = zzastnew();
  77 #ifdef DEMAND_LOOK
  78         zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
  79 #else
  80         zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
  81 #endif
  82         zzastPush( n );
  83         if ( *_tail != NULL ) (*_tail)->right = n;
  84         else {
  85                 *_sibling = n;
  86                 if ( *_root != NULL ) (*_root)->down = *_sibling;
  87         }
  88         *_tail = n;
  89         if ( *_root == NULL ) *_root = *_sibling;
  90         }
  91 }
  92
  93 /* make a new AST node.  Make the newly-created
  94  * node the root for the current sibling list.  If a root node already
  95  * exists, make the newly-created node the root of the current root.
  96  */
  97 void
  98 #ifdef __STDC__
  99 zzsubroot(AST **_root, AST **_sibling, AST **_tail)
 100 #else
 101 zzsubroot(_root, _sibling, _tail)
 102 AST **_root, **_sibling, **_tail;
 103 #endif
 104 {
 105         AST *n;
 106         zzNON_GUESS_MODE {
 107         n = zzastnew();
 108 #ifdef DEMAND_LOOK
 109         zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
 110 #else
 111         zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
 112 #endif
 113         zzastPush( n );
 114         if ( *_root != NULL )
 115                 if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root;
 116         *_root = n;
 117         (*_root)->down = *_sibling;
 118         }
 119 }
 120
 121 /* Apply function to root then each sibling
 122  * example: print tree in child-sibling LISP-format (AST has token field)
 123  *
 124  *      void show(tree)
 125  *      AST *tree;
 126  *      {
 127  *              if ( tree == NULL ) return;
 128  *              printf(" %s", zztokens[tree->token]);
 129  *      }
 130  *
 131  *      void before() { printf(" ("); }
 132  *      void after()  { printf(" )"); }
 133  *
 134  *      LISPdump() { zzpre_ast(tree, show, before, after); }
 135  *
 136  */
 137 void
 138 #ifdef __STDC__
 139 zzpre_ast(
 140           AST *tree,
 141           void (*func)(AST *),   /* apply this to each tree node */
 142           void (*before)(AST *), /* apply this to root of subtree before preordering it */
 143           void (*after)(AST *))  /* apply this to root of subtree after preordering it */
 144 #else
 145 zzpre_ast(tree, func, before, after)
 146 AST *tree;
 147 void (*func)(),   /* apply this to each tree node */
 148          (*before)(), /* apply this to root of subtree before preordering it */
 149          (*after)();  /* apply this to root of subtree after preordering it */
 150 #endif
 151 {
 152         while ( tree!= NULL )
 153         {
 154                 if ( tree->down != NULL ) (*before)(tree);
 155                 (*func)(tree);
 156                 zzpre_ast(tree->down, func, before, after);
 157                 if ( tree->down != NULL ) (*after)(tree);
 158                 tree = tree->right;
 159         }
 160 }
 161
 162 /* free all AST nodes in tree; apply func to each before freeing */
 163 void
 164 #ifdef __STDC__
 165 zzfree_ast(AST *tree)
 166 #else
 167 zzfree_ast(tree)
 168 AST *tree;
 169 #endif
 170 {
 171         if ( tree == NULL ) return;
 172         zzfree_ast( tree->down );
 173         zzfree_ast( tree->right );
 174         zztfree( tree );
 175 }
 176
 177 /* build a tree (root child1 child2 ... NULL)
 178  * If root is NULL, simply make the children siblings and return ptr
 179  * to 1st sibling (child1).  If root is not single node, return NULL.
 180  *
 181  * Siblings that are actually siblins lists themselves are handled
 182  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
 183  * in the tree ( NULL A B C D ).
 184  *
 185  * Requires at least two parameters with the last one being NULL.  If
 186  * both are NULL, return NULL.
 187  */
 188 #ifdef __STDC__
 189 AST *zztmake(AST *rt, ...)
 190 #else
 191 AST *zztmake(va_alist)
 192 va_dcl
 193 #endif
 194 {
 195         va_list ap;
 196         register AST *child, *sibling=NULL, *tail, *w;
 197         AST *root;
 198
 199 #ifdef __STDC__
 200         va_start(ap, rt);
 201         root = rt;
 202 #else
 203         va_start(ap);
 204         root = va_arg(ap, AST *);
 205 #endif
 206
 207         if ( root != NULL )
 208                 if ( root->down != NULL ) return NULL;
 209         child = va_arg(ap, AST *);
 210         while ( child != NULL )
 211         {
 212                 for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
 213                 if ( sibling == NULL ) {sibling = child; tail = w;}
 214                 else {tail->right = child; tail = w;}
 215                 child = va_arg(ap, AST *);
 216         }
 217         if ( root==NULL ) root = sibling;
 218         else root->down = sibling;
 219         va_end(ap);
 220         return root;
 221 }
 222
 223 /* tree duplicate */
 224 AST *
 225 #ifdef __STDC__
 226 zzdup_ast(AST *t)
 227 #else
 228 zzdup_ast(t)
 229 AST *t;
 230 #endif
 231 {
 232         AST *u;
 233
 234         if ( t == NULL ) return NULL;
 235         u = zzastnew();
 236         *u = *t;
 237 #ifdef zzAST_DOUBLE
 238         u->up = NULL;           /* set by calling invocation */
 239         u->left = NULL;
 240 #endif
 241         u->right = zzdup_ast(t->right);
 242         u->down = zzdup_ast(t->down);
 243 #ifdef zzAST_DOUBLE
 244         if ( u->right!=NULL ) u->right->left = u;
 245         if ( u->down!=NULL ) u->down->up = u;
 246 #endif
 247         return u;
 248 }
 249
 250 void
 251 #ifdef __STDC__
 252 zztfree(AST *t)
 253 #else
 254 zztfree(t)
 255 AST *t;
 256 #endif
 257 {
 258 #ifdef zzd_ast
 259         zzd_ast( t );
 260 #endif
 261         free( t );
 262 }
 263
 264 #ifdef zzAST_DOUBLE
 265 /*
 266  * Set the 'up', and 'left' pointers of all nodes in 't'.
 267  * Initial call is double_link(your_tree, NULL, NULL).
 268  */
 269 void
 270 #ifdef __STDC__
 271 zzdouble_link(AST *t, AST *left, AST *up)
 272 #else
 273 zzdouble_link(t, left, up)
 274 AST *t, *left, *up;
 275 #endif
 276 {
 277         if ( t==NULL ) return;
 278         t->left = left;
 279         t->up = up;
 280         zzdouble_link(t->down, NULL, t);
 281         zzdouble_link(t->right, t, up);
 282 }
 283 #endif