1*48116Sbostic /*- 2*48116Sbostic * Copyright (c) 1980 The Regents of the University of California. 3*48116Sbostic * All rights reserved. 4*48116Sbostic * 5*48116Sbostic * %sccs.include.redist.c% 622215Sdist */ 7796Speter 814749Sthien #ifndef lint 9*48116Sbostic static char sccsid[] = "@(#)yytree.c 5.2 (Berkeley) 04/16/91"; 10*48116Sbostic #endif /* not lint */ 11796Speter 12796Speter #include "whoami.h" 13796Speter #include "0.h" 14796Speter #include "tree.h" 1514749Sthien #include "tree_ty.h" 16796Speter 17796Speter extern int *spacep; 18796Speter 19796Speter /* 20796Speter * LIST MANIPULATION ROUTINES 21796Speter * 22796Speter * The grammar for Pascal is written left recursively. 23796Speter * Because of this, the portions of parse trees which are to resemble 24796Speter * lists are in the somewhat inconvenient position of having 25796Speter * the nodes built from left to right, while we want to eventually 26796Speter * have as semantic value the leftmost node. 27796Speter * We could carry the leftmost node as semantic value, but this 28796Speter * would be inefficient as to add a new node to the list we would 29796Speter * have to chase down to the end. Other solutions involving a head 30796Speter * and tail pointer waste space. 31796Speter * 32796Speter * The simple solution to this apparent dilemma is to carry along 33796Speter * a pointer to the leftmost node in a list in the rightmost node 34796Speter * which is the current semantic value of the list. 35796Speter * When we have completed building the list, we can retrieve this 36796Speter * left end pointer very easily; neither adding new elements to the list 37796Speter * nor finding the left end is thus expensive. As the bottommost node 38796Speter * has an unused next pointer in it, no space is wasted either. 39796Speter * 40796Speter * The nodes referred to here are of the T_LISTPP type and have 41796Speter * the form: 42796Speter * 43796Speter * T_LISTPP some_pointer next_element 44796Speter * 45796Speter * Here some_pointer points to the things of interest in the list, 46796Speter * and next_element to the next thing in the list except for the 47796Speter * rightmost node, in which case it points to the leftmost node. 48796Speter * The next_element of the rightmost node is of course zapped to the 49796Speter * NIL pointer when the list is completed. 50796Speter * 51796Speter * Thinking of the lists as tree we heceforth refer to the leftmost 52796Speter * node as the "top", and the rightmost node as the "bottom" or as 53796Speter * the "virtual root". 54796Speter */ 55796Speter 56796Speter /* 57796Speter * Make a new list 58796Speter */ 5914749Sthien struct tnode * 60796Speter newlist(new) 6114749Sthien register struct tnode *new; 62796Speter { 63796Speter 6414749Sthien if (new == TR_NIL) 6514749Sthien return (TR_NIL); 6614749Sthien return ((struct tnode *) tree3(T_LISTPP, (int) new, 6714749Sthien (struct tnode *) spacep)); 68796Speter } 69796Speter 70796Speter /* 71796Speter * Add a new element to an existing list 72796Speter */ 7314749Sthien struct tnode * 74796Speter addlist(vroot, new) 7514749Sthien register struct tnode *vroot; 7614749Sthien struct tnode *new; 77796Speter { 7814749Sthien register struct tnode *top; 79796Speter 8014749Sthien if (new == TR_NIL) 81796Speter return (vroot); 8214749Sthien if (vroot == TR_NIL) 83796Speter return (newlist(new)); 8414749Sthien top = vroot->list_node.next; 8514749Sthien vroot->list_node.next = (struct tnode *) spacep; 8614749Sthien return ((struct tnode *) tree3(T_LISTPP, (int) new, top)); 87796Speter } 88796Speter 89796Speter /* 90796Speter * Fix up the list which has virtual root vroot. 91796Speter * We grab the top pointer and return it, zapping the spot 92796Speter * where it was so that the tree is not circular. 93796Speter */ 9414749Sthien struct tnode * 95796Speter fixlist(vroot) 9614749Sthien register struct tnode *vroot; 97796Speter { 9814749Sthien register struct tnode *top; 99796Speter 10014749Sthien if (vroot == TR_NIL) 10114749Sthien return (TR_NIL); 10214749Sthien top = vroot->list_node.next; 10314749Sthien vroot->list_node.next = TR_NIL; 104796Speter return (top); 105796Speter } 106796Speter 107796Speter 108796Speter /* 109796Speter * Set up a T_VAR node for a qualified variable. 110796Speter * Init is the initial entry in the qualification, 111796Speter * or NIL if there is none. 112796Speter * 113796Speter * if we are building pTrees, there has to be an extra slot for 114796Speter * a pointer to the namelist entry of a field, if this T_VAR refers 115796Speter * to a field name within a WITH statement. 116796Speter * this extra field is set in lvalue, and used in VarCopy. 117796Speter */ 11814749Sthien struct tnode * 119796Speter setupvar(var, init) 120796Speter char *var; 12114749Sthien register struct tnode *init; 122796Speter { 123796Speter 12414749Sthien if (init != TR_NIL) 125796Speter init = newlist(init); 126796Speter # ifndef PTREE 12714749Sthien return (tree4(T_VAR, NOCON, (struct tnode *) var, init)); 128796Speter # else 12914749Sthien return tree5( T_VAR, NOCON, (struct tnode *) var, init, TR_NIL ); 130796Speter # endif 131796Speter } 132796Speter 133796Speter /* 134796Speter * set up a T_TYREC node for a record 135796Speter * 136796Speter * if we are building pTrees, there has to be an extra slot for 137796Speter * a pointer to the namelist entry of the record. 138796Speter * this extra field is filled in in gtype, and used in RecTCopy. 139796Speter */ 14014749Sthien struct tnode * 14114749Sthien setuptyrec( line , fldlist ) 142796Speter int line; 14314749Sthien struct tnode *fldlist; 144796Speter { 145796Speter 146796Speter # ifndef PTREE 14714749Sthien return tree3( T_TYREC , line , fldlist ); 148796Speter # else 14914749Sthien return tree4( T_TYREC , line , fldlst , TR_NIL ); 150796Speter # endif 151796Speter } 152796Speter 153796Speter /* 154796Speter * set up a T_FIELD node for a field. 155796Speter * 156796Speter * if we are building pTrees, there has to be an extra slot for 157796Speter * a pointer to the namelist entry of the field. 158796Speter * this extra field is set in lvalue, and used in SelCopy. 159796Speter */ 16014749Sthien struct tnode * 161796Speter setupfield( field , other ) 16214749Sthien struct tnode *field; 16314749Sthien struct tnode *other; 164796Speter { 165796Speter 166796Speter # ifndef PTREE 16714749Sthien return tree3( T_FIELD , (int) field , other ); 168796Speter # else 16914749Sthien return tree4( T_FIELD , (int) field , other , TR_NIL ); 170796Speter # endif 171796Speter } 172