1 /* Copyright (c) 1979 Regents of the University of California */ 2 3 #ifndef lint 4 static char sccsid[] = "@(#)yytree.c 2.1 02/08/84"; 5 #endif 6 7 #include "whoami.h" 8 #include "0.h" 9 #include "tree.h" 10 #include "tree_ty.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 struct tnode * 55 newlist(new) 56 register struct tnode *new; 57 { 58 59 if (new == TR_NIL) 60 return (TR_NIL); 61 return ((struct tnode *) tree3(T_LISTPP, (int) new, 62 (struct tnode *) spacep)); 63 } 64 65 /* 66 * Add a new element to an existing list 67 */ 68 struct tnode * 69 addlist(vroot, new) 70 register struct tnode *vroot; 71 struct tnode *new; 72 { 73 register struct tnode *top; 74 75 if (new == TR_NIL) 76 return (vroot); 77 if (vroot == TR_NIL) 78 return (newlist(new)); 79 top = vroot->list_node.next; 80 vroot->list_node.next = (struct tnode *) spacep; 81 return ((struct tnode *) tree3(T_LISTPP, (int) 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 struct tnode * 90 fixlist(vroot) 91 register struct tnode *vroot; 92 { 93 register struct tnode *top; 94 95 if (vroot == TR_NIL) 96 return (TR_NIL); 97 top = vroot->list_node.next; 98 vroot->list_node.next = TR_NIL; 99 return (top); 100 } 101 102 103 /* 104 * Set up a T_VAR node for a qualified variable. 105 * Init is the initial entry in the qualification, 106 * or NIL if there is none. 107 * 108 * if we are building pTrees, there has to be an extra slot for 109 * a pointer to the namelist entry of a field, if this T_VAR refers 110 * to a field name within a WITH statement. 111 * this extra field is set in lvalue, and used in VarCopy. 112 */ 113 struct tnode * 114 setupvar(var, init) 115 char *var; 116 register struct tnode *init; 117 { 118 119 if (init != TR_NIL) 120 init = newlist(init); 121 # ifndef PTREE 122 return (tree4(T_VAR, NOCON, (struct tnode *) var, init)); 123 # else 124 return tree5( T_VAR, NOCON, (struct tnode *) var, init, TR_NIL ); 125 # endif 126 } 127 128 /* 129 * set up a T_TYREC node for a record 130 * 131 * if we are building pTrees, there has to be an extra slot for 132 * a pointer to the namelist entry of the record. 133 * this extra field is filled in in gtype, and used in RecTCopy. 134 */ 135 struct tnode * 136 setuptyrec( line , fldlist ) 137 int line; 138 struct tnode *fldlist; 139 { 140 141 # ifndef PTREE 142 return tree3( T_TYREC , line , fldlist ); 143 # else 144 return tree4( T_TYREC , line , fldlst , TR_NIL ); 145 # endif 146 } 147 148 /* 149 * set up a T_FIELD node for a field. 150 * 151 * if we are building pTrees, there has to be an extra slot for 152 * a pointer to the namelist entry of the field. 153 * this extra field is set in lvalue, and used in SelCopy. 154 */ 155 struct tnode * 156 setupfield( field , other ) 157 struct tnode *field; 158 struct tnode *other; 159 { 160 161 # ifndef PTREE 162 return tree3( T_FIELD , (int) field , other ); 163 # else 164 return tree4( T_FIELD , (int) field , other , TR_NIL ); 165 # endif 166 } 167