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

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

Defined functions