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 *
newlist(new)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 *
addlist(vroot,new)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 *
fixlist(vroot)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 *
setupvar(var,init)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 *
setuptyrec(line,fldlist)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 *
setupfield(field,other)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