home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / h / astx.C < prev    next >
C/C++ Source or Header  |  1994-03-31  |  5KB  |  179 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, University of Minnesota
  27.  * 1989-1994
  28.  */
  29. #include <stdio.h>
  30. #include <stdarg.h>
  31. #include "astx.h"
  32.  
  33. /* ensure that tree manipulation variables are current after a rule
  34.  * reference
  35.  */
  36. void
  37. ASTBase::link(ASTBase **_root, ASTBase **_sibling, ASTBase **_tail)
  38. {
  39.     if ( *_sibling == NULL ) return;
  40.     if ( *_root == NULL ) *_root = *_sibling;
  41.     else if ( *_root != *_sibling ) (*_root)->_down = *_sibling;
  42.     if ( *_tail==NULL ) *_tail = *_sibling;
  43.     while ( (*_tail)->_right != NULL ) *_tail = (*_tail)->_right;
  44. }
  45.  
  46. /* add a child node to the current sibling list */
  47. void
  48. ASTBase::subchild(ASTBase **_root, ASTBase **_sibling, ASTBase **_tail)
  49. {
  50.     if ( *_tail != NULL ) (*_tail)->_right = this;
  51.     else {
  52.         *_sibling = this;
  53.         if ( *_root != NULL ) (*_root)->_down = *_sibling;
  54.     }
  55.     *_tail = this;
  56.     if ( *_root == NULL ) *_root = *_sibling;
  57. }
  58.  
  59. /* make a new AST node.  Make the newly-created
  60.  * node the root for the current sibling list.  If a root node already
  61.  * exists, make the newly-created node the root of the current root.
  62.  */
  63. void
  64. ASTBase::subroot(ASTBase **_root, ASTBase **_sibling, ASTBase **_tail)
  65. {
  66.     if ( *_root != NULL )
  67.         if ( (*_root)->_down == *_sibling ) *_sibling = *_tail = *_root;
  68.     *_root = this;
  69.     (*_root)->_down = *_sibling;
  70. }
  71.  
  72. /* Apply preorder_action(), etc.. to root then each sibling */
  73. void
  74. ASTBase::preorder()
  75. {
  76.     ASTBase *tree = this;
  77.  
  78.     while ( tree!= NULL )
  79.     {
  80.         if ( tree->_down != NULL ) preorder_before_action();
  81.         tree->preorder_action();
  82.         tree->_down->preorder();
  83.         if ( tree->_down != NULL ) preorder_after_action();
  84.         tree = tree->_right;
  85.     }
  86. }
  87.  
  88. /* free all AST nodes in tree; apply func to each before freeing */
  89. void
  90. ASTBase::destroy()
  91. {
  92.     ASTBase *tree = this;
  93.  
  94.     tree->_down->destroy();
  95.     tree->_right->destroy();
  96.     delete tree;
  97. }
  98.  
  99. /* build a tree (root child1 child2 ... NULL)
  100.  * If root is NULL, simply make the children siblings and return ptr
  101.  * to 1st sibling (child1).  If root is not single node, return NULL.
  102.  *
  103.  * Siblings that are actually siblins lists themselves are handled
  104.  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
  105.  * in the tree ( NULL A B C D ).
  106.  *
  107.  * Requires at least two parameters with the last one being NULL.  If
  108.  * both are NULL, return NULL.
  109.  */
  110. ASTBase *
  111. ASTBase::tmake(ASTBase *root, ...)
  112. {
  113.     va_list ap;
  114.     register ASTBase *child, *sibling=NULL, *tail, *w;
  115.  
  116.     va_start(ap, root);
  117.  
  118.     if ( root != NULL )
  119.         if ( root->_down != NULL ) return NULL;
  120.     child = va_arg(ap, ASTBase *);
  121.     while ( child != NULL )
  122.     {
  123.         for (w=child; w->_right!=NULL; w=w->_right) {;} /* find end of child */
  124.         if ( sibling == NULL ) {sibling = child; tail = w;}
  125.         else {tail->_right = child; tail = w;}
  126.         child = va_arg(ap, ASTBase *);
  127.     }
  128.     if ( root==NULL ) root = sibling;
  129.     else root->_down = sibling;
  130.     va_end(ap);
  131.     return root;
  132. }
  133.  
  134. /* tree duplicate */
  135. ASTBase *
  136. ASTBase::dup()
  137. {
  138.     ASTBase *u, *t=this;
  139.     
  140.     u = new ASTBase;
  141.     *u = *t;
  142.     u->_right = t->_right->dup();
  143.     u->_down = t->_down->dup();
  144.     return u;
  145. }
  146.  
  147. /* tree duplicate */
  148. ASTDoublyLinkedBase *
  149. ASTDoublyLinkedBase::dup()
  150. {
  151.     ASTDoublyLinkedBase *u, *t=this;
  152.     
  153.     if ( t == NULL ) return NULL;
  154.     u = new ASTDoublyLinkedBase;
  155.     *u = *t;
  156.     u->_up = NULL;        /* set by calling invocation */
  157.     u->_left = NULL;
  158.     u->_right = t->_right->dup();
  159.     u->_down = t->_down->dup();
  160.     if ( u->_right!=NULL ) ((ASTDoublyLinkedBase *)u->_right)->_left = u;
  161.     if ( u->_down!=NULL ) ((ASTDoublyLinkedBase *)u->_down)->_up = u;
  162.     return u;
  163. }
  164.  
  165. /*
  166.  * Set the 'up', and 'left' pointers of all nodes in 't'.
  167.  * Initial call is double_link(your_tree, NULL, NULL).
  168.  */
  169. void
  170. ASTDoublyLinkedBase::double_link(ASTBase *left, ASTBase *up)
  171. {
  172.     ASTDoublyLinkedBase *t = this;
  173.  
  174.     t->_left = (ASTDoublyLinkedBase *) left;
  175.     t->_up = (ASTDoublyLinkedBase *) up;
  176.     ((ASTDoublyLinkedBase *)t->_down)->double_link(NULL, t);
  177.     ((ASTDoublyLinkedBase *)t->_right)->double_link(t, up);
  178. }
  179.