1
/* Abstract syntax tree manipulation functions
5
* We reserve no LEGAL rights to the Purdue Compiler Construction Tool
6
* Set (PCCTS) -- PCCTS is in the public domain. An individual or
7
* company may do whatever they wish with source code distributed with
8
* PCCTS or the code generated by PCCTS, including the incorporation of
9
* PCCTS, or its output, into commerical software.
11
* We encourage users to develop software with PCCTS. However, we do ask
12
* that credit is given to us for developing PCCTS. By "credit",
13
* we mean that if you incorporate our source code into one of your
14
* programs (commercial product, research project, or otherwise) that you
15
* acknowledge this fact somewhere in the documentation, research report,
16
* etc... If you like PCCTS and have developed a nice tool with the
17
* output, please mention that you developed it using PCCTS. In
18
* addition, we ask that this header remain intact in our source code.
19
* As long as these guidelines are kept, we expect to continue enhancing
20
* this system and expect to make other tools available as they are
25
* Parr Research Corporation
26
* with Purdue University and AHPCRC, University of Minnesota
32
#ifdef PCCTS_USE_STDARG
33
#include "pccts_stdarg.h"
38
/* ensure that tree manipulation variables are current after a rule
44
zzlink(AST **_root, AST **_sibling, AST **_tail)
46
zzlink(_root, _sibling, _tail)
47
AST **_root, **_sibling, **_tail;
50
if ( *_sibling == NULL ) return;
51
if ( *_root == NULL ) *_root = *_sibling;
52
else if ( *_root != *_sibling ) (*_root)->down = *_sibling;
53
if ( *_tail==NULL ) *_tail = *_sibling;
54
while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right;
64
AST *p = (AST *) calloc(1, sizeof(AST));
65
if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__);
69
/* add a child node to the current sibling list */
72
zzsubchild(AST **_root, AST **_sibling, AST **_tail)
74
zzsubchild(_root, _sibling, _tail)
75
AST **_root, **_sibling, **_tail;
82
zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
84
zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
87
if ( *_tail != NULL ) (*_tail)->right = n;
90
if ( *_root != NULL ) (*_root)->down = *_sibling;
93
if ( *_root == NULL ) *_root = *_sibling;
97
/* make a new AST node. Make the newly-created
98
* node the root for the current sibling list. If a root node already
99
* exists, make the newly-created node the root of the current root.
103
zzsubroot(AST **_root, AST **_sibling, AST **_tail)
105
zzsubroot(_root, _sibling, _tail)
106
AST **_root, **_sibling, **_tail;
113
zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0));
115
zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1));
118
if ( *_root != NULL )
119
if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root;
121
(*_root)->down = *_sibling;
125
/* Apply function to root then each sibling
126
* example: print tree in child-sibling LISP-format (AST has token field)
131
* if ( tree == NULL ) return;
132
* printf(" %s", zztokens[tree->token]);
135
* void before() { printf(" ("); }
136
* void after() { printf(" )"); }
138
* LISPdump() { zzpre_ast(tree, show, before, after); }
145
void (*func)(AST *), /* apply this to each tree node */
146
void (*before)(AST *), /* apply this to root of subtree before preordering it */
147
void (*after)(AST *)) /* apply this to root of subtree after preordering it */
149
zzpre_ast(tree, func, before, after)
151
void (*func)(), /* apply this to each tree node */
152
(*before)(), /* apply this to root of subtree before preordering it */
153
(*after)(); /* apply this to root of subtree after preordering it */
156
while ( tree!= NULL )
158
if ( tree->down != NULL ) (*before)(tree);
160
zzpre_ast(tree->down, func, before, after);
161
if ( tree->down != NULL ) (*after)(tree);
166
/* free all AST nodes in tree; apply func to each before freeing */
170
////#ifdef __USE_PROTOS
171
////zzfree_ast(AST *tree)
177
//// if ( tree == NULL ) return;
178
//// zzfree_ast( tree->down );
179
//// zzfree_ast( tree->right );
180
//// zztfree( tree );
185
MR19 Optimize freeing of the following structure to limit recursion
186
SAKAI Kiyotaka (ksakai@isr.co.jp)
198
MR21 Another refinement to replace recursion with iteration
199
NAKAJIMA Mutsuki (muc@isr.co.jp).
204
zzfree_ast(AST *tree)
213
if (tree == NULL) return;
215
while (tree->down == NULL || tree->right == NULL) {
217
if (tree->down == NULL && tree->right == NULL) {
223
if (tree->down == NULL) {
231
while (tree != NULL) {
232
zzfree_ast(tree->down);
239
/* build a tree (root child1 child2 ... NULL)
240
* If root is NULL, simply make the children siblings and return ptr
241
* to 1st sibling (child1). If root is not single node, return NULL.
243
* Siblings that are actually siblins lists themselves are handled
244
* correctly. For example #( NULL, #( NULL, A, B, C), D) results
245
* in the tree ( NULL A B C D ).
247
* Requires at least two parameters with the last one being NULL. If
248
* both are NULL, return NULL.
250
#ifdef PCCTS_USE_STDARG
251
AST *zztmake(AST *rt, ...)
253
AST *zztmake(va_alist)
258
register AST *child, *sibling=NULL, *tail=NULL /* MR20 */, *w;
261
#ifdef PCCTS_USE_STDARG
266
root = va_arg(ap, AST *);
270
if ( root->down != NULL ) return NULL;
271
child = va_arg(ap, AST *);
272
while ( child != NULL )
274
for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
275
if ( sibling == NULL ) {sibling = child; tail = w;}
276
else {tail->right = child; tail = w;}
277
child = va_arg(ap, AST *);
279
if ( root==NULL ) root = sibling;
280
else root->down = sibling;
296
if ( t == NULL ) return NULL;
300
u->up = NULL; /* set by calling invocation */
303
u->right = zzdup_ast(t->right);
304
u->down = zzdup_ast(t->down);
306
if ( u->right!=NULL ) u->right->left = u;
307
if ( u->down!=NULL ) u->down->up = u;
328
* Set the 'up', and 'left' pointers of all nodes in 't'.
329
* Initial call is double_link(your_tree, NULL, NULL).
333
zzdouble_link(AST *t, AST *left, AST *up)
335
zzdouble_link(t, left, up)
339
if ( t==NULL ) return;
342
zzdouble_link(t->down, NULL, t);
343
zzdouble_link(t->right, t, up);
added
removed
pccts/h/ast.c
