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