home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / h / ast.c < prev    next >
C/C++ Source or Header  |  1994-03-31  |  7KB  |  284 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.20
  24.  * Terence Parr
  25.  * Purdue University
  26.  * with AHPCRC, U of MN
  27.  * 1989-1994
  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
  284.