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