2.11BSD#431 - /usr/src/ucb/PORT/pascal/src/yytree.c

   1: /*
   2:  * Copyright (c) 1980 Regents of the University of California.
   3:  * All rights reserved.  The Berkeley software License Agreement
   4:  * specifies the terms and conditions for redistribution.
   5:  */
   6: 
   7: #ifndef lint
   8: static char sccsid[] = "@(#)yytree.c	5.1 (Berkeley) 6/5/85";
   9: #endif not lint
  10: 
  11: #include "whoami.h"
  12: #include "0.h"
  13: #include "tree.h"
  14: #include "tree_ty.h"
  15: 
  16: extern  int *spacep;
  17: 
  18: /*
  19:  * LIST MANIPULATION ROUTINES
  20:  *
  21:  * The grammar for Pascal is written left recursively.
  22:  * Because of this, the portions of parse trees which are to resemble
  23:  * lists are in the somewhat inconvenient position of having
  24:  * the nodes built from left to right, while we want to eventually
  25:  * have as semantic value the leftmost node.
  26:  * We could carry the leftmost node as semantic value, but this
  27:  * would be inefficient as to add a new node to the list we would
  28:  * have to chase down to the end.  Other solutions involving a head
  29:  * and tail pointer waste space.
  30:  *
  31:  * The simple solution to this apparent dilemma is to carry along
  32:  * a pointer to the leftmost node in a list in the rightmost node
  33:  * which is the current semantic value of the list.
  34:  * When we have completed building the list, we can retrieve this
  35:  * left end pointer very easily; neither adding new elements to the list
  36:  * nor finding the left end is thus expensive.  As the bottommost node
  37:  * has an unused next pointer in it, no space is wasted either.
  38:  *
  39:  * The nodes referred to here are of the T_LISTPP type and have
  40:  * the form:
  41:  *
  42:  *	T_LISTPP	some_pointer		next_element
  43:  *
  44:  * Here some_pointer points to the things of interest in the list,
  45:  * and next_element to the next thing in the list except for the
  46:  * rightmost node, in which case it points to the leftmost node.
  47:  * The next_element of the rightmost node is of course zapped to the
  48:  * NIL pointer when the list is completed.
  49:  *
  50:  * Thinking of the lists as tree we heceforth refer to the leftmost
  51:  * node as the "top", and the rightmost node as the "bottom" or as
  52:  * the "virtual root".
  53:  */
  54: 
  55: /*
  56:  * Make a new list
  57:  */
  58: struct tnode *
  59: newlist(new)
  60:     register struct tnode *new;
  61: {
  62: 
  63:     if (new == TR_NIL)
  64:         return (TR_NIL);
  65:     return ((struct tnode *) tree3(T_LISTPP, (int) new,
  66:                     (struct tnode *) spacep));
  67: }
  68: 
  69: /*
  70:  * Add a new element to an existing list
  71:  */
  72: struct tnode *
  73: addlist(vroot, new)
  74:     register struct tnode *vroot;
  75:     struct tnode *new;
  76: {
  77:     register struct tnode *top;
  78: 
  79:     if (new == TR_NIL)
  80:         return (vroot);
  81:     if (vroot == TR_NIL)
  82:         return (newlist(new));
  83:     top = vroot->list_node.next;
  84:     vroot->list_node.next = (struct tnode *) spacep;
  85:     return ((struct tnode *) tree3(T_LISTPP, (int) new, top));
  86: }
  87: 
  88: /*
  89:  * Fix up the list which has virtual root vroot.
  90:  * We grab the top pointer and return it, zapping the spot
  91:  * where it was so that the tree is not circular.
  92:  */
  93: struct tnode *
  94: fixlist(vroot)
  95:     register struct tnode *vroot;
  96: {
  97:     register struct tnode *top;
  98: 
  99:     if (vroot == TR_NIL)
 100:         return (TR_NIL);
 101:     top = vroot->list_node.next;
 102:     vroot->list_node.next = TR_NIL;
 103:     return (top);
 104: }
 105: 
 106: 
 107: /*
 108:  * Set up a T_VAR node for a qualified variable.
 109:  * Init is the initial entry in the qualification,
 110:  * or NIL if there is none.
 111:  *
 112:  * if we are building pTrees, there has to be an extra slot for
 113:  * a pointer to the namelist entry of a field, if this T_VAR refers
 114:  * to a field name within a WITH statement.
 115:  * this extra field is set in lvalue, and used in VarCopy.
 116:  */
 117: struct tnode *
 118: setupvar(var, init)
 119:     char *var;
 120:     register struct tnode *init;
 121: {
 122: 
 123:     if (init != TR_NIL)
 124:         init = newlist(init);
 125: #	ifndef PTREE
 126:         return (tree4(T_VAR, NOCON, (struct tnode *) var, init));
 127: #	else
 128:         return tree5( T_VAR, NOCON, (struct tnode *) var, init, TR_NIL );
 129: #	endif
 130: }
 131: 
 132:     /*
 133:      *	set up a T_TYREC node for a record
 134:      *
 135:      *	if we are building pTrees, there has to be an extra slot for
 136:      *	a pointer to the namelist entry of the record.
 137:      *	this extra field is filled in in gtype, and used in RecTCopy.
 138:      */
 139: struct tnode *
 140: setuptyrec( line , fldlist )
 141:     int line;
 142:     struct tnode *fldlist;
 143:     {
 144: 
 145: #	ifndef PTREE
 146:         return tree3( T_TYREC , line , fldlist );
 147: #	else
 148:         return tree4( T_TYREC , line , fldlst , TR_NIL );
 149: #	endif
 150:     }
 151: 
 152:     /*
 153:      *	set up a T_FIELD node for a field.
 154:      *
 155:      *	if we are building pTrees, there has to be an extra slot for
 156:      *	a pointer to the namelist entry of the field.
 157:      *	this extra field is set in lvalue, and used in SelCopy.
 158:      */
 159: struct tnode *
 160: setupfield( field , other )
 161:     struct tnode *field;
 162:     struct tnode *other;
 163:     {
 164: 
 165: #	ifndef PTREE
 166:         return tree3( T_FIELD , (int) field , other );
 167: #	else
 168:         return tree4( T_FIELD , (int) field , other , TR_NIL );
 169: #	endif
 170:     }

Defined functions

Defined variables