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