2.9BSD - /usr/src/ucb/pascal/pxp/yytree.c

   1: #
   2: /*
   3:  * pxp - Pascal execution profiler
   4:  *
   5:  * Bill Joy UCB
   6:  * Version 1.2 January 1979
   7:  */
   8: 
   9: #include "0.h"
  10: #include "tree.h"
  11: 
  12: extern  int *spacep;
  13: 
  14: /*
  15:  * LIST MANIPULATION ROUTINES
  16:  *
  17:  * The grammar for Pascal is written left recursively.
  18:  * Because of this, the portions of parse trees which are to resemble
  19:  * lists are in the somewhat inconvenient position of having
  20:  * the nodes built from left to right, while we want to eventually
  21:  * have as semantic value the leftmost node.
  22:  * We could carry the leftmost node as semantic value, but this
  23:  * would be inefficient as to add a new node to the list we would
  24:  * have to chase down to the end.  Other solutions involving a head
  25:  * and tail pointer waste space.
  26:  *
  27:  * The simple solution to this apparent dilemma is to carry along
  28:  * a pointer to the leftmost node in a list in the rightmost node
  29:  * which is the current semantic value of the list.
  30:  * When we have completed building the list, we can retrieve this
  31:  * left end pointer very easily; neither adding new elements to the list
  32:  * nor finding the left end is thus expensive.  As the bottommost node
  33:  * has an unused next pointer in it, no space is wasted either.
  34:  *
  35:  * The nodes referred to here are of the T_LISTPP type and have
  36:  * the form:
  37:  *
  38:  *	T_LISTPP	some_pointer		next_element
  39:  *
  40:  * Here some_pointer points to the things of interest in the list,
  41:  * and next_element to the next thing in the list except for the
  42:  * rightmost node, in which case it points to the leftmost node.
  43:  * The next_element of the rightmost node is of course zapped to the
  44:  * NIL pointer when the list is completed.
  45:  *
  46:  * Thinking of the lists as tree we heceforth refer to the leftmost
  47:  * node as the "top", and the rightmost node as the "bottom" or as
  48:  * the "virtual root".
  49:  */
  50: 
  51: /*
  52:  * Make a new list
  53:  */
  54: newlist(new)
  55:     register int *new;
  56: {
  57: 
  58:     if (new == NIL)
  59:         return (NIL);
  60:     return (tree3(T_LISTPP, new, spacep));
  61: }
  62: 
  63: /*
  64:  * Add a new element to an existing list
  65:  */
  66: addlist(vroot, new)
  67:     register int *vroot;
  68:     int *new;
  69: {
  70:     register int *top;
  71: 
  72:     if (new == NIL)
  73:         return (vroot);
  74:     if (vroot == NIL)
  75:         return (newlist(new));
  76:     top = vroot[2];
  77:     vroot[2] = spacep;
  78:     return (tree3(T_LISTPP, new, top));
  79: }
  80: 
  81: /*
  82:  * Fix up the list which has virtual root vroot.
  83:  * We grab the top pointer and return it, zapping the spot
  84:  * where it was so that the tree is not circular.
  85:  */
  86: fixlist(vroot)
  87:     register int *vroot;
  88: {
  89:     register int *top;
  90: 
  91:     if (vroot == NIL)
  92:         return (NIL);
  93:     top = vroot[2];
  94:     vroot[2] = NIL;
  95:     return (top);
  96: }
  97: 
  98: 
  99: /*
 100:  * Set up a T_VAR node for a qualified variable.
 101:  * Init is the initial entry in the qualification,
 102:  * or NIL if there is none.
 103:  */
 104: setupvar(var, init)
 105:     char *var;
 106:     register int *init;
 107: {
 108: 
 109:     if (init != NIL)
 110:         init = newlist(init);
 111:     return (tree4(T_VAR, NOCON, var, init));
 112: }

Defined functions