]>
Commit | Line | Data |
---|---|---|
30fdf114 LG |
1 | /* Abstract syntax tree manipulation functions\r |
2 | *\r | |
3 | * SOFTWARE RIGHTS\r | |
4 | *\r | |
5 | * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r | |
6 | * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r | |
7 | * company may do whatever they wish with source code distributed with\r | |
8 | * PCCTS or the code generated by PCCTS, including the incorporation of\r | |
9 | * PCCTS, or its output, into commerical software.\r | |
10 | *\r | |
11 | * We encourage users to develop software with PCCTS. However, we do ask\r | |
12 | * that credit is given to us for developing PCCTS. By "credit",\r | |
13 | * we mean that if you incorporate our source code into one of your\r | |
14 | * programs (commercial product, research project, or otherwise) that you\r | |
15 | * acknowledge this fact somewhere in the documentation, research report,\r | |
16 | * etc... If you like PCCTS and have developed a nice tool with the\r | |
17 | * output, please mention that you developed it using PCCTS. In\r | |
18 | * addition, we ask that this header remain intact in our source code.\r | |
19 | * As long as these guidelines are kept, we expect to continue enhancing\r | |
20 | * this system and expect to make other tools available as they are\r | |
21 | * completed. \r | |
22 | *\r | |
23 | * ANTLR 1.33\r | |
24 | * Terence Parr\r | |
25 | * Parr Research Corporation\r | |
26 | * with Purdue University and AHPCRC, University of Minnesota\r | |
27 | * 1989-2000\r | |
28 | */\r | |
29 | \r | |
30 | #include "pcctscfg.h"\r | |
31 | \r | |
32 | #ifdef PCCTS_USE_STDARG\r | |
33 | #include "pccts_stdarg.h"\r | |
34 | #else\r | |
35 | #include <varargs.h>\r | |
36 | #endif\r | |
37 | \r | |
38 | /* ensure that tree manipulation variables are current after a rule\r | |
39 | * reference\r | |
40 | */\r | |
41 | \r | |
42 | void\r | |
43 | #ifdef __USE_PROTOS\r | |
44 | zzlink(AST **_root, AST **_sibling, AST **_tail)\r | |
45 | #else\r | |
46 | zzlink(_root, _sibling, _tail)\r | |
47 | AST **_root, **_sibling, **_tail;\r | |
48 | #endif\r | |
49 | {\r | |
50 | if ( *_sibling == NULL ) return;\r | |
51 | if ( *_root == NULL ) *_root = *_sibling;\r | |
52 | else if ( *_root != *_sibling ) (*_root)->down = *_sibling;\r | |
53 | if ( *_tail==NULL ) *_tail = *_sibling;\r | |
54 | while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right;\r | |
55 | }\r | |
56 | \r | |
57 | AST *\r | |
58 | #ifdef __USE_PROTOS\r | |
59 | zzastnew(void)\r | |
60 | #else\r | |
61 | zzastnew()\r | |
62 | #endif\r | |
63 | {\r | |
64 | AST *p = (AST *) calloc(1, sizeof(AST));\r | |
65 | if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);\r | |
66 | return p;\r | |
67 | }\r | |
68 | \r | |
69 | /* add a child node to the current sibling list */\r | |
70 | void\r | |
71 | #ifdef __USE_PROTOS\r | |
72 | zzsubchild(AST **_root, AST **_sibling, AST **_tail)\r | |
73 | #else\r | |
74 | zzsubchild(_root, _sibling, _tail)\r | |
75 | AST **_root, **_sibling, **_tail;\r | |
76 | #endif\r | |
77 | {\r | |
78 | AST *n;\r | |
79 | zzNON_GUESS_MODE {\r | |
80 | n = zzastnew();\r | |
81 | #ifdef DEMAND_LOOK\r | |
82 | zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));\r | |
83 | #else\r | |
84 | zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));\r | |
85 | #endif\r | |
86 | zzastPush( n );\r | |
87 | if ( *_tail != NULL ) (*_tail)->right = n;\r | |
88 | else {\r | |
89 | *_sibling = n;\r | |
90 | if ( *_root != NULL ) (*_root)->down = *_sibling;\r | |
91 | }\r | |
92 | *_tail = n;\r | |
93 | if ( *_root == NULL ) *_root = *_sibling;\r | |
94 | }\r | |
95 | }\r | |
96 | \r | |
97 | /* make a new AST node. Make the newly-created\r | |
98 | * node the root for the current sibling list. If a root node already\r | |
99 | * exists, make the newly-created node the root of the current root.\r | |
100 | */\r | |
101 | void\r | |
102 | #ifdef __USE_PROTOS\r | |
103 | zzsubroot(AST **_root, AST **_sibling, AST **_tail)\r | |
104 | #else\r | |
105 | zzsubroot(_root, _sibling, _tail)\r | |
106 | AST **_root, **_sibling, **_tail;\r | |
107 | #endif\r | |
108 | {\r | |
109 | AST *n;\r | |
110 | zzNON_GUESS_MODE {\r | |
111 | n = zzastnew();\r | |
112 | #ifdef DEMAND_LOOK\r | |
113 | zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));\r | |
114 | #else\r | |
115 | zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));\r | |
116 | #endif\r | |
117 | zzastPush( n );\r | |
118 | if ( *_root != NULL )\r | |
119 | if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root;\r | |
120 | *_root = n;\r | |
121 | (*_root)->down = *_sibling;\r | |
122 | }\r | |
123 | }\r | |
124 | \r | |
125 | /* Apply function to root then each sibling\r | |
126 | * example: print tree in child-sibling LISP-format (AST has token field)\r | |
127 | *\r | |
128 | * void show(tree)\r | |
129 | * AST *tree;\r | |
130 | * {\r | |
131 | * if ( tree == NULL ) return;\r | |
132 | * printf(" %s", zztokens[tree->token]);\r | |
133 | * }\r | |
134 | *\r | |
135 | * void before() { printf(" ("); }\r | |
136 | * void after() { printf(" )"); }\r | |
137 | *\r | |
138 | * LISPdump() { zzpre_ast(tree, show, before, after); }\r | |
139 | *\r | |
140 | */\r | |
141 | void\r | |
142 | #ifdef __USE_PROTOS\r | |
143 | zzpre_ast(\r | |
144 | AST *tree,\r | |
145 | void (*func)(AST *), /* apply this to each tree node */\r | |
146 | void (*before)(AST *), /* apply this to root of subtree before preordering it */\r | |
147 | void (*after)(AST *)) /* apply this to root of subtree after preordering it */\r | |
148 | #else\r | |
149 | zzpre_ast(tree, func, before, after)\r | |
150 | AST *tree;\r | |
151 | void (*func)(), /* apply this to each tree node */\r | |
152 | (*before)(), /* apply this to root of subtree before preordering it */\r | |
153 | (*after)(); /* apply this to root of subtree after preordering it */\r | |
154 | #endif\r | |
155 | {\r | |
156 | while ( tree!= NULL )\r | |
157 | {\r | |
158 | if ( tree->down != NULL ) (*before)(tree);\r | |
159 | (*func)(tree);\r | |
160 | zzpre_ast(tree->down, func, before, after);\r | |
161 | if ( tree->down != NULL ) (*after)(tree);\r | |
162 | tree = tree->right;\r | |
163 | }\r | |
164 | }\r | |
165 | \r | |
166 | /* free all AST nodes in tree; apply func to each before freeing */\r | |
167 | \r | |
168 | #if 0\r | |
169 | ////void\r | |
170 | ////#ifdef __USE_PROTOS\r | |
171 | ////zzfree_ast(AST *tree)\r | |
172 | ////#else\r | |
173 | ////zzfree_ast(tree)\r | |
174 | ////AST *tree;\r | |
175 | ////#endif\r | |
176 | ////{\r | |
177 | //// if ( tree == NULL ) return;\r | |
178 | //// zzfree_ast( tree->down );\r | |
179 | //// zzfree_ast( tree->right );\r | |
180 | //// zztfree( tree );\r | |
181 | ////}\r | |
182 | #endif\r | |
183 | \r | |
184 | /*\r | |
185 | MR19 Optimize freeing of the following structure to limit recursion\r | |
186 | SAKAI Kiyotaka (ksakai@isr.co.jp)\r | |
187 | */\r | |
188 | \r | |
189 | /*\r | |
190 | NULL o\r | |
191 | / \\r | |
192 | NULL o\r | |
193 | / \\r | |
194 | NULL NULL\r | |
195 | */\r | |
196 | \r | |
197 | /*\r | |
198 | MR21 Another refinement to replace recursion with iteration\r | |
199 | NAKAJIMA Mutsuki (muc@isr.co.jp).\r | |
200 | */\r | |
201 | \r | |
202 | void\r | |
203 | #ifdef __USE_PROTOS\r | |
204 | zzfree_ast(AST *tree)\r | |
205 | #else\r | |
206 | zzfree_ast(tree)\r | |
207 | AST *tree;\r | |
208 | #endif\r | |
209 | {\r | |
210 | \r | |
211 | AST *otree;\r | |
212 | \r | |
213 | if (tree == NULL) return;\r | |
214 | \r | |
215 | while (tree->down == NULL || tree->right == NULL) {\r | |
216 | \r | |
217 | if (tree->down == NULL && tree->right == NULL) {\r | |
218 | zztfree(tree);\r | |
219 | return;\r | |
220 | }\r | |
221 | \r | |
222 | otree = tree;\r | |
223 | if (tree->down == NULL) {\r | |
224 | tree = tree->right;\r | |
225 | } else {\r | |
226 | tree = tree->down;\r | |
227 | }\r | |
228 | zztfree( otree );\r | |
229 | }\r | |
230 | \r | |
231 | while (tree != NULL) {\r | |
232 | zzfree_ast(tree->down);\r | |
233 | otree = tree;\r | |
234 | tree = otree->right;\r | |
235 | zztfree(otree);\r | |
236 | }\r | |
237 | }\r | |
238 | \r | |
239 | /* build a tree (root child1 child2 ... NULL)\r | |
240 | * If root is NULL, simply make the children siblings and return ptr\r | |
241 | * to 1st sibling (child1). If root is not single node, return NULL.\r | |
242 | *\r | |
243 | * Siblings that are actually siblins lists themselves are handled\r | |
244 | * correctly. For example #( NULL, #( NULL, A, B, C), D) results\r | |
245 | * in the tree ( NULL A B C D ).\r | |
246 | *\r | |
247 | * Requires at least two parameters with the last one being NULL. If\r | |
248 | * both are NULL, return NULL.\r | |
249 | */\r | |
250 | #ifdef PCCTS_USE_STDARG\r | |
251 | AST *zztmake(AST *rt, ...)\r | |
252 | #else\r | |
253 | AST *zztmake(va_alist)\r | |
254 | va_dcl\r | |
255 | #endif\r | |
256 | {\r | |
257 | va_list ap;\r | |
258 | register AST *child, *sibling=NULL, *tail=NULL /* MR20 */, *w;\r | |
259 | AST *root;\r | |
260 | \r | |
261 | #ifdef PCCTS_USE_STDARG\r | |
262 | va_start(ap, rt);\r | |
263 | root = rt;\r | |
264 | #else\r | |
265 | va_start(ap);\r | |
266 | root = va_arg(ap, AST *);\r | |
267 | #endif\r | |
268 | \r | |
269 | if ( root != NULL )\r | |
270 | if ( root->down != NULL ) return NULL;\r | |
271 | child = va_arg(ap, AST *);\r | |
272 | while ( child != NULL )\r | |
273 | {\r | |
274 | for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */\r | |
275 | if ( sibling == NULL ) {sibling = child; tail = w;}\r | |
276 | else {tail->right = child; tail = w;}\r | |
277 | child = va_arg(ap, AST *);\r | |
278 | }\r | |
279 | if ( root==NULL ) root = sibling;\r | |
280 | else root->down = sibling;\r | |
281 | va_end(ap);\r | |
282 | return root;\r | |
283 | }\r | |
284 | \r | |
285 | /* tree duplicate */\r | |
286 | AST *\r | |
287 | #ifdef __USE_PROTOS\r | |
288 | zzdup_ast(AST *t)\r | |
289 | #else\r | |
290 | zzdup_ast(t)\r | |
291 | AST *t;\r | |
292 | #endif\r | |
293 | {\r | |
294 | AST *u;\r | |
295 | \r | |
296 | if ( t == NULL ) return NULL;\r | |
297 | u = zzastnew();\r | |
298 | *u = *t;\r | |
299 | #ifdef zzAST_DOUBLE\r | |
300 | u->up = NULL; /* set by calling invocation */\r | |
301 | u->left = NULL;\r | |
302 | #endif\r | |
303 | u->right = zzdup_ast(t->right);\r | |
304 | u->down = zzdup_ast(t->down);\r | |
305 | #ifdef zzAST_DOUBLE\r | |
306 | if ( u->right!=NULL ) u->right->left = u;\r | |
307 | if ( u->down!=NULL ) u->down->up = u;\r | |
308 | #endif\r | |
309 | return u;\r | |
310 | }\r | |
311 | \r | |
312 | void\r | |
313 | #ifdef __USE_PROTOS\r | |
314 | zztfree(AST *t)\r | |
315 | #else\r | |
316 | zztfree(t)\r | |
317 | AST *t;\r | |
318 | #endif\r | |
319 | {\r | |
320 | #ifdef zzd_ast\r | |
321 | zzd_ast( t );\r | |
322 | #endif\r | |
323 | free( t );\r | |
324 | }\r | |
325 | \r | |
326 | #ifdef zzAST_DOUBLE\r | |
327 | /*\r | |
328 | * Set the 'up', and 'left' pointers of all nodes in 't'.\r | |
329 | * Initial call is double_link(your_tree, NULL, NULL).\r | |
330 | */\r | |
331 | void\r | |
332 | #ifdef __USE_PROTOS\r | |
333 | zzdouble_link(AST *t, AST *left, AST *up)\r | |
334 | #else\r | |
335 | zzdouble_link(t, left, up)\r | |
336 | AST *t, *left, *up;\r | |
337 | #endif\r | |
338 | {\r | |
339 | if ( t==NULL ) return;\r | |
340 | t->left = left;\r | |
341 | t->up = up;\r | |
342 | zzdouble_link(t->down, NULL, t);\r | |
343 | zzdouble_link(t->right, t, up);\r | |
344 | }\r | |
345 | #endif\r |