]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/VfrCompile/Pccts/h/ast.c
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
);