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) 06/05/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 } 171