]>
git.proxmox.com Git - mirror_edk2.git/blob - EdkCompatibilityPkg/Other/Maintained/Tools/Pccts/h/PCCTSAST.cpp
6 * We reserve no LEGAL rights to SORCERER -- SORCERER is in the public
7 * domain. An individual or company may do whatever they wish with
8 * source code distributed with SORCERER or the code generated by
9 * SORCERER, including the incorporation of SORCERER, or its output, into
10 * commerical software.
12 * We encourage users to develop software with SORCERER. However, we do
13 * ask that credit is given to us for developing SORCERER. By "credit",
14 * we mean that if you incorporate our source code into one of your
15 * programs (commercial product, research project, or otherwise) that you
16 * acknowledge this fact somewhere in the documentation, research report,
17 * etc... If you like SORCERER and have developed a nice tool with the
18 * output, please mention that you developed it using SORCERER. In
19 * addition, we ask that this header remain intact in our source code.
20 * As long as these guidelines are kept, we expect to continue enhancing
21 * this system and expect to make other tools available as they are
24 * SORCERER 1.00B14 and ANTLR 1.33
26 * Parr Research Corporation
27 * AHPCRC, University of Minnesota
31 #define ANTLR_SUPPORT_CODE
36 #include "pccts_stdarg.h"
44 /* String Scanning/Parsing Stuff */
46 const char *PCCTS_AST::scan_token_tbl
[] = { /* MR20 const */
58 addChild(PCCTS_AST
*t
)
60 if ( t
==NULL
) return;
61 PCCTS_AST
*s
= down();
64 while ( s
->right()!=NULL
) s
= s
->right();
74 if ( down() != NULL
) fprintf(f
," (");
76 if ( down()!=NULL
) down()->lisp(f
);
77 if ( down() != NULL
) fprintf(f
," )");
78 if ( right()!=NULL
) right()->lisp(f
);
81 /* build a tree (root child1 child2 ... NULL)
82 * If root is NULL, simply make the children siblings and return ptr
83 * to 1st sibling (child1). If root is not single node, return NULL.
85 * Siblings that are actually sibling lists themselves are handled
86 * correctly. For example #( NULL, #( NULL, A, B, C), D) results
87 * in the tree ( NULL A B C D ).
89 * Requires at least two parameters with the last one being NULL. If
90 * both are NULL, return NULL.
92 * The down() and right() down/right pointers are used to make the tree.
94 PCCTS_AST
*PCCTS_AST::
95 make(PCCTS_AST
*rt
, ...)
98 register PCCTS_AST
*child
, *sibling
=NULL
, *tail
, *w
;
105 if ( root
->down() != NULL
) return NULL
;
106 child
= va_arg(ap
, PCCTS_AST
*);
107 while ( child
!= NULL
)
109 /* find end of child */
110 for (w
=child
; w
->right()!=NULL
; w
=w
->right()) {;}
111 if ( sibling
== NULL
) {sibling
= child
; tail
= w
;}
112 else {tail
->setRight(child
); tail
= w
;}
113 child
= va_arg(ap
, PCCTS_AST
*);
115 if ( root
==NULL
) root
= sibling
;
116 else root
->setDown(sibling
);
121 /* The following push and pop routines are only used by ast_find_all() */
124 _push(PCCTS_AST
**st
, int *sp
, PCCTS_AST
*e
)
127 require((*sp
)>=0, "stack overflow");
131 PCCTS_AST
*PCCTS_AST::
132 _pop(PCCTS_AST
**st
, int *sp
)
134 PCCTS_AST
*e
= st
[*sp
];
136 require((*sp
)<=MaxTreeStackDepth
, "stack underflow");
140 /* Find all occurrences of u in t.
141 * 'cursor' must be initialized to 't'. It eventually
142 * returns NULL when no more occurrences of 'u' are found.
144 PCCTS_AST
*PCCTS_AST::
145 ast_find_all(PCCTS_AST
*u
, PCCTS_AST
**cursor
)
148 static PCCTS_AST
*template_stack
[MaxTreeStackDepth
];
149 static int tsp
= MaxTreeStackDepth
;
150 static int nesting
= 0;
152 if ( *cursor
== NULL
) return NULL
;
153 if ( *cursor
!=this ) sib
= *cursor
;
155 /* else, first time--start at top of template 't' */
156 tsp
= MaxTreeStackDepth
;
158 /* bottom of stack is always a NULL--"cookie" indicates "done" */
159 _push(template_stack
, &tsp
, NULL
);
163 if ( sib
==NULL
) /* hit end of sibling list */
165 sib
= _pop(template_stack
, &tsp
);
166 if ( sib
== NULL
) { *cursor
= NULL
; return NULL
; }
169 if ( sib
->type() != u
->type() )
171 /* look for another match */
172 if ( sib
->down()!=NULL
)
174 if ( sib
->right()!=NULL
) _push(template_stack
, &tsp
, sib
->right());
178 /* nothing below to try, try next sibling */
183 /* found a matching root node, try to match what's below */
184 if ( match_partial(sib
, u
) )
186 /* record sibling cursor so we can pick up next from there */
187 if ( sib
->down()!=NULL
)
189 if ( sib
->right()!=NULL
) _push(template_stack
, &tsp
, sib
->right());
190 *cursor
= sib
->down();
192 else if ( sib
->right()!=NULL
) *cursor
= sib
->right();
193 else *cursor
= _pop(template_stack
, &tsp
);
197 /* no match, keep searching */
198 if ( sib
->down()!=NULL
)
200 if ( sib
->right()!=NULL
) _push(template_stack
, &tsp
, sib
->right());
203 else sib
= sib
->right(); /* else, try to right if zip below */
207 /* are two trees exactly alike? */
214 if ( u
==NULL
) return 0;
216 for (sib
=t
; sib
!=NULL
&&u
!=NULL
; sib
=sib
->right(), u
=u
->right())
218 if ( sib
->type() != u
->type() ) return 0;
219 if ( sib
->down()!=NULL
)
220 if ( !sib
->down()->match(u
->down()) ) return 0;
225 /* Is 'u' a subtree of 't' beginning at the root? */
227 match_partial(PCCTS_AST
*t
, PCCTS_AST
*u
)
231 if ( u
==NULL
) return 1;
232 if ( t
==NULL
) if ( u
!=NULL
) return 0; else return 1;
234 for (sib
=t
; sib
!=NULL
&&u
!=NULL
; sib
=sib
->right(), u
=u
->right())
236 if ( sib
->type() != u
->type() ) return 0;
237 if ( sib
->down()!=NULL
)
238 if ( !match_partial(sib
->down(), u
->down()) ) return 0;
243 /* Walk the template tree 't' (matching against 'this'), filling in the
244 * 'labels' array, and setting 'n' according to how many labels were matched.
247 scanmatch(ScanAST
*t
, PCCTS_AST
**labels
[], int *n
)
252 if ( u
==NULL
) return 0;
254 for (sib
=t
; sib
!=NULL
&&u
!=NULL
; sib
=sib
->right(), u
=u
->right())
256 /* make sure tokens match; token of '0' means wildcard match */
257 if ( sib
->type() != u
->type() && sib
->type()!=0 ) return 0;
258 /* we have a matched token here; set label pointers if exists */
259 if ( sib
->label_num
>0 )
261 require(labels
!=NULL
, "label found in template, but no array of labels");
263 *(labels
[sib
->label_num
-1]) = u
;
265 /* match what's below if something there and current node is not wildcard */
266 if ( sib
->down()!=NULL
&& sib
->type()!=0 )
268 if ( sib
->down()==NULL
) if ( u
->down()!=NULL
) return 0; else return 1;
269 if ( !u
->down()->scanmatch(sib
->down(), labels
, n
) ) return 0;
276 insert_after(PCCTS_AST
*b
)
279 if ( b
==NULL
) return;
280 /* find end of b's child list */
281 for (end
=b
; end
->right()!=NULL
; end
=end
->right()) {;}
282 end
->setRight(this->right());
290 require(b
!=NULL
, "append: NULL input tree");
291 /* find end of child list */
292 for (end
=this; end
->right()!=NULL
; end
=end
->right()) {;}
296 PCCTS_AST
*PCCTS_AST::
300 /* find end of child list */
301 for (end
=this; end
->right()!=NULL
; end
=end
->right()) {;}
305 PCCTS_AST
*PCCTS_AST::
309 /* find end of child list */
310 for (end
=this; end
->down()!=NULL
; end
=end
->down()) {;}
314 PCCTS_AST
*PCCTS_AST::
315 cut_between(PCCTS_AST
*a
, PCCTS_AST
*b
)
317 PCCTS_AST
*end
, *ret
;
318 if (a
==NULL
||b
==NULL
) return NULL
;
319 /* find node pointing to b */
320 for (end
=a
; end
->right()!=NULL
&&end
->right()!=b
; end
=end
->right())
322 if (end
->right()==NULL
) return NULL
; //ast_cut_between: a,b not connected
323 end
->setRight(NULL
); /* don't want it point to 'b' anymore */
333 SList
*list
= new SList
;
336 for (p
=this; p
!=NULL
; p
=p
->right())
348 if ( t
->down()!=NULL
) t
->down()->tfree();
349 if ( t
->right()!=NULL
) t
->right()->tfree();
367 PCCTS_AST
*PCCTS_AST::
372 require(i
>0, "sibling_index: i<=0");
376 if ( j
==i
) return t
;
383 /* Assume this is a root node of a tree--
384 * duplicate that node and what's below; ignore siblings of root node.
389 // MR9 RJV: Original version only duplicated the node and down elements.
390 // MR9 Made copies of the pointers to sibling.
391 // MR9 Changed call "down()->deepCopy()" to "down()->deepCopyBushy()"
394 PCCTS_AST
*PCCTS_AST::
397 PCCTS_AST
*u
= this->shallowCopy();
398 if ( down()!=NULL
) u
->setDown(down()->deepCopyBushy());
403 /* Copy all nodes including siblings of root. */
404 PCCTS_AST
*PCCTS_AST::
407 PCCTS_AST
*u
= this->shallowCopy();
408 /* copy the rest of the tree */
409 if ( down()!=NULL
) u
->setDown(down()->deepCopyBushy());
410 if ( right()!=NULL
) u
->setRight(right()->deepCopyBushy());
415 scanast_free(ScanAST
*t
)
417 if ( t
== NULL
) return;
418 scanast_free( t
->down() );
419 scanast_free( t
->right() );
420 free( (char *) t
); // MR1
426 * This function is like scanf(): it attempts to match a template
427 * against an input tree. A variable number of tree pointers
428 * may be set according to the '%i' labels in the template string.
431 * t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
434 * Naturally, you'd want this converted from
436 * t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
441 * This function call must be done withing a SORCERER file because SORCERER
442 * must convert the token references to the associated token number.
444 * This functions parses the template and creates trees which are then
445 * matched against the input tree. The labels are set as they are
446 * encountered; hence, partial matches may leave some pointers set
447 * and some NULL. This routines initializes all argument pointers to NULL
450 * This function returns the number of labels matched.
453 ast_scan(char *templ
, ...)
458 PCCTS_AST
***label_ptrs
=NULL
;
462 /* make a ScanAST tree out of the template */
463 tmpl
= stringparser_parse_scanast(templ
, &n
);
465 /* make an array out of the labels */
468 label_ptrs
= (PCCTS_AST
***) calloc(n
, sizeof(PCCTS_AST
**));
469 require(label_ptrs
!=NULL
, "scan: out of memory");
472 label_ptrs
[i
-1] = va_arg(ap
, PCCTS_AST
**);
473 *(label_ptrs
[i
-1]) = NULL
;
477 /* match the input tree against the template */
478 scanmatch(tmpl
, label_ptrs
, &found
);
481 free( (char *) label_ptrs
); // MR1
489 ScanAST
*p
= (ScanAST
*) calloc(1, sizeof(ScanAST
));
493 if ( p
== NULL
) { // MR1
494 fprintf(stderr
, "out of mem\n"); // MR1
495 exit(PCCTS_EXIT_FAILURE
); // MR1
502 stringparser_parse_scanast(char *templ
, int *num_labels
)
508 stringlexer_init(&lex
, templ
);
509 stringparser_init(&parser
, &lex
);
510 t
= stringparser_parse_tree(&parser
);
511 *num_labels
= parser
.num_labels
;
516 stringparser_match(StringParser
*parser
, int token
)
518 if ( parser
->token
!= token
) panic("bad tree in scan()");
522 * Match a tree of the form:
523 * (root child1 child2 ... childn)
527 * where the elements are integers or labeled integers.
530 stringparser_parse_tree(StringParser
*parser
)
532 ScanAST
*t
=NULL
, *root
, *child
, *last
;
534 if ( parser
->token
!= __POUND
)
536 return stringparser_parse_element(parser
);
538 stringparser_match(parser
,__POUND
);
539 parser
->token
= stringscan_gettok(parser
->lexer
);
540 stringparser_match(parser
,__LPAREN
);
541 parser
->token
= stringscan_gettok(parser
->lexer
);
542 root
= stringparser_parse_element(parser
);
543 while ( parser
->token
!= __RPAREN
)
545 child
= stringparser_parse_element(parser
);
546 if ( t
==NULL
) { t
= child
; last
= t
; }
547 else { last
->_right
= child
; last
= child
; }
549 stringparser_match(parser
,__RPAREN
);
550 parser
->token
= stringscan_gettok(parser
->lexer
);
556 stringparser_parse_element(StringParser
*parser
)
558 static char ebuf
[100];
561 if ( parser
->token
== __POUND
)
563 return stringparser_parse_tree(parser
);
565 if ( parser
->token
== __PERCENT
)
567 parser
->token
= stringscan_gettok(parser
->lexer
);
568 stringparser_match(parser
,__INT
);
569 label
= atoi(parser
->lexer
->text
);
570 parser
->num_labels
++;
571 if ( label
==0 ) panic("%%0 is an invalid label");
572 parser
->token
= stringscan_gettok(parser
->lexer
);
573 stringparser_match(parser
,__COLON
);
574 parser
->token
= stringscan_gettok(parser
->lexer
);
575 /* can label tokens and wildcards */
576 if ( parser
->token
!= __INT
&& parser
->token
!= __PERIOD
)
577 panic("can only label tokens");
579 if ( parser
->token
== __INT
)
581 ScanAST
*p
= new_scanast(atoi(parser
->lexer
->text
));
582 parser
->token
= stringscan_gettok(parser
->lexer
);
583 p
->label_num
= label
;
586 if ( parser
->token
== __PERIOD
)
588 ScanAST
*p
= new_scanast(0); /* token of 0 is wildcard */
589 parser
->token
= stringscan_gettok(parser
->lexer
);
590 p
->label_num
= label
;
593 sprintf(ebuf
, "mismatch token in scan(): %s", scan_token_str(parser
->token
));
599 stringparser_init(StringParser
*parser
, StringLexer
*input
)
601 parser
->lexer
= input
;
602 parser
->token
= stringscan_gettok(parser
->lexer
);
603 parser
->num_labels
= 0;
607 stringlexer_init(StringLexer
*scanner
, char *input
)
609 scanner
->text
[0]='\0';
610 scanner
->input
= input
;
612 stringscan_advance(scanner
);
616 stringscan_advance(StringLexer
*scanner
)
618 if ( *(scanner
->p
) == '\0' ) scanner
->c
= __StringScanEOF
;
619 scanner
->c
= *(scanner
->p
)++;
623 stringscan_gettok(StringLexer
*scanner
)
625 char *index
= &scanner
->text
[0];
626 static char ebuf
[100];
628 while ( isspace(scanner
->c
) ) { stringscan_advance(scanner
); }
629 if ( isdigit(scanner
->c
) )
632 while ( isdigit(scanner
->c
) ) {
633 *index
++ = scanner
->c
;
634 stringscan_advance(scanner
);
639 switch ( scanner
->c
)
641 case '#' : stringscan_advance(scanner
); return __POUND
;
642 case '(' : stringscan_advance(scanner
); return __LPAREN
;
643 case ')' : stringscan_advance(scanner
); return __RPAREN
;
644 case '%' : stringscan_advance(scanner
); return __PERCENT
;
645 case ':' : stringscan_advance(scanner
); return __COLON
;
646 case '.' : stringscan_advance(scanner
); return __PERIOD
;
647 case '\0' : return __StringScanEOF
;
648 case __StringScanEOF
: return __StringScanEOF
;
650 sprintf(ebuf
, "invalid char in scan: '%c'", scanner
->c
);
653 return __StringScanEOF
; // never reached
656 const char *PCCTS_AST:: /* MR20 const */
657 scan_token_str(int t
)
659 if ( VALID_SCAN_TOKEN(t
) ) return scan_token_tbl
[t
];
660 else if ( t
==__StringScanEOF
) return "<end-of-string>";
661 else return "<invalid-token>";