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