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 42void 43#ifdef __USE_PROTOS 44zzlink(AST **_root, AST **_sibling, AST **_tail) 45#else 46zzlink(_root, _sibling, _tail) 47AST **_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 57AST * 58#ifdef __USE_PROTOS 59zzastnew(void) 60#else 61zzastnew() 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 */ 70void 71#ifdef __USE_PROTOS 72zzsubchild(AST **_root, AST **_sibling, AST **_tail) 73#else 74zzsubchild(_root, _sibling, _tail) 75AST **_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 */ 101void 102#ifdef __USE_PROTOS 103zzsubroot(AST **_root, AST **_sibling, AST **_tail) 104#else 105zzsubroot(_root, _sibling, _tail) 106AST **_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 */ 141void 142#ifdef __USE_PROTOS 143zzpre_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 149zzpre_ast(tree, func, before, after) 150AST *tree; 151void (*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 202void 203#ifdef __USE_PROTOS 204zzfree_ast(AST *tree) 205#else 206zzfree_ast(tree) 207AST *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 251AST *zztmake(AST *rt, ...) 252#else 253AST *zztmake(va_alist) 254va_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 */ 286AST * 287#ifdef __USE_PROTOS 288zzdup_ast(AST *t) 289#else 290zzdup_ast(t) 291AST *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 312void 313#ifdef __USE_PROTOS 314zztfree(AST *t) 315#else 316zztfree(t) 317AST *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 */ 331void 332#ifdef __USE_PROTOS 333zzdouble_link(AST *t, AST *left, AST *up) 334#else 335zzdouble_link(t, left, up) 336AST *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 346