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
38 /* String Scanning/Parsing Stuff */
40 char *PCCTS_AST::scan_token_tbl[] = {
52 addChild(PCCTS_AST *t)
54 if ( t==NULL ) return;
55 PCCTS_AST *s = down();
58 while ( s->right()!=NULL ) s = s->right();
68 if ( down() != NULL ) fprintf(f," (");
70 if ( down()!=NULL ) down()->lisp(f);
71 if ( down() != NULL ) fprintf(f," )");
72 if ( right()!=NULL ) right()->lisp(f);
75 /* build a tree (root child1 child2 ... NULL)
76 * If root is NULL, simply make the children siblings and return ptr
77 * to 1st sibling (child1). If root is not single node, return NULL.
79 * Siblings that are actually sibling lists themselves are handled
80 * correctly. For example #( NULL, #( NULL, A, B, C), D) results
81 * in the tree ( NULL A B C D ).
83 * Requires at least two parameters with the last one being NULL. If
84 * both are NULL, return NULL.
86 * The down() and right() down/right pointers are used to make the tree.
88 PCCTS_AST *PCCTS_AST::
89 make(PCCTS_AST *rt, ...)
92 register PCCTS_AST *child, *sibling=NULL, *tail, *w;
99 if ( root->down() != NULL ) return NULL;
100 child = va_arg(ap, PCCTS_AST *);
101 while ( child != NULL )
103 /* find end of child */
104 for (w=child; w->right()!=NULL; w=w->right()) {;}
105 if ( sibling == NULL ) {sibling = child; tail = w;}
106 else {tail->setRight(child); tail = w;}
107 child = va_arg(ap, PCCTS_AST *);
109 if ( root==NULL ) root = sibling;
110 else root->setDown(sibling);
115 /* The following push and pop routines are only used by ast_find_all() */
118 _push(PCCTS_AST **st, int *sp, PCCTS_AST *e)
121 require((*sp)>=0, "stack overflow");
125 PCCTS_AST *PCCTS_AST::
126 _pop(PCCTS_AST **st, int *sp)
128 PCCTS_AST *e = st[*sp];
130 require((*sp)<=MaxTreeStackDepth, "stack underflow");
134 /* Find all occurrences of u in t.
135 * 'cursor' must be initialized to 't'. It eventually
136 * returns NULL when no more occurrences of 'u' are found.
138 PCCTS_AST *PCCTS_AST::
139 ast_find_all(PCCTS_AST *u, PCCTS_AST **cursor)
142 static PCCTS_AST *template_stack[MaxTreeStackDepth];
143 static int tsp = MaxTreeStackDepth;
144 static int nesting = 0;
146 if ( *cursor == NULL ) return NULL;
147 if ( *cursor!=this ) sib = *cursor;
149 /* else, first time--start at top of template 't' */
150 tsp = MaxTreeStackDepth;
152 /* bottom of stack is always a NULL--"cookie" indicates "done" */
153 _push(template_stack, &tsp, NULL);
157 if ( sib==NULL ) /* hit end of sibling list */
159 sib = _pop(template_stack, &tsp);
160 if ( sib == NULL ) { *cursor = NULL; return NULL; }
163 if ( sib->type() != u->type() )
165 /* look for another match */
166 if ( sib->down()!=NULL )
168 if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
172 /* nothing below to try, try next sibling */
177 /* found a matching root node, try to match what's below */
178 if ( match_partial(sib, u) )
180 /* record sibling cursor so we can pick up next from there */
181 if ( sib->down()!=NULL )
183 if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
184 *cursor = sib->down();
186 else if ( sib->right()!=NULL ) *cursor = sib->right();
187 else *cursor = _pop(template_stack, &tsp);
191 /* no match, keep searching */
192 if ( sib->down()!=NULL )
194 if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
197 else sib = sib->right(); /* else, try to right if zip below */
201 /* are two trees exactly alike? */
208 if ( u==NULL ) return 0;
210 for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
212 if ( sib->type() != u->type() ) return 0;
213 if ( sib->down()!=NULL )
214 if ( !sib->down()->match(u->down()) ) return 0;
219 /* Is 'u' a subtree of 't' beginning at the root? */
221 match_partial(PCCTS_AST *t, PCCTS_AST *u)
225 if ( u==NULL ) return 1;
226 if ( t==NULL ) if ( u!=NULL ) return 0; else return 1;
228 for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
230 if ( sib->type() != u->type() ) return 0;
231 if ( sib->down()!=NULL )
232 if ( !match_partial(sib->down(), u->down()) ) return 0;
237 /* Walk the template tree 't' (matching against 'this'), filling in the
238 * 'labels' array, and setting 'n' according to how many labels were matched.
241 scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n)
246 if ( u==NULL ) return 0;
248 for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
250 /* make sure tokens match; token of '0' means wildcard match */
251 if ( sib->type() != u->type() && sib->type()!=0 ) return 0;
252 /* we have a matched token here; set label pointers if exists */
253 if ( sib->label_num>0 )
255 require(labels!=NULL, "label found in template, but no array of labels");
257 *(labels[sib->label_num-1]) = u;
259 /* match what's below if something there and current node is not wildcard */
260 if ( sib->down()!=NULL && sib->type()!=0 )
262 if ( sib->down()==NULL ) if ( u->down()!=NULL ) return 0; else return 1;
263 if ( !u->down()->scanmatch(sib->down(), labels, n) ) return 0;
270 insert_after(PCCTS_AST *b)
273 if ( b==NULL ) return;
274 /* find end of b's child list */
275 for (end=b; end->right()!=NULL; end=end->right()) {;}
276 end->setRight(this->right());
284 require(b!=NULL, "append: NULL input tree");
285 /* find end of child list */
286 for (end=this; end->right()!=NULL; end=end->right()) {;}
290 PCCTS_AST *PCCTS_AST::
294 /* find end of child list */
295 for (end=this; end->right()!=NULL; end=end->right()) {;}
299 PCCTS_AST *PCCTS_AST::
303 /* find end of child list */
304 for (end=this; end->down()!=NULL; end=end->down()) {;}
308 PCCTS_AST *PCCTS_AST::
309 cut_between(PCCTS_AST *a, PCCTS_AST *b)
311 PCCTS_AST *end, *ret;
312 if (a==NULL||b==NULL) return NULL;
313 /* find node pointing to b */
314 for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right())
316 if (end->right()==NULL) return NULL; //ast_cut_between: a,b not connected
317 end->setRight(NULL); /* don't want it point to 'b' anymore */
327 SList *list = new SList;
330 for (p=this; p!=NULL; p=p->right())
342 if ( t->down()!=NULL ) t->down()->tfree();
343 if ( t->right()!=NULL ) t->right()->tfree();
361 PCCTS_AST *PCCTS_AST::
366 require(i>0, "sibling_index: i<=0");
370 if ( j==i ) return t;
377 /* Assume this is a root node of a tree--
378 * duplicate that node and what's below; ignore siblings of root node.
380 PCCTS_AST *PCCTS_AST::
383 PCCTS_AST *u = this->shallowCopy();
384 if ( down()!=NULL ) u->setDown(down()->deepCopy());
388 /* Copy all nodes including siblings of root. */
389 PCCTS_AST *PCCTS_AST::
392 PCCTS_AST *u = this->shallowCopy();
393 /* copy the rest of the tree */
394 if ( down()!=NULL ) u->setDown(down()->deepCopy());
395 if ( right()!=NULL ) u->setRight(right()->deepCopy());
400 scanast_free(ScanAST *t)
402 if ( t == NULL ) return;
403 scanast_free( t->down() );
404 scanast_free( t->right() );
411 * This function is like scanf(): it attempts to match a template
412 * against an input tree. A variable number of tree pointers
413 * may be set according to the '%i' labels in the template string.
416 * t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
419 * Naturally, you'd want this converted from
421 * t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
426 * This function call must be done withing a SORCERER file because SORCERER
427 * must convert the token references to the associated token number.
429 * This functions parses the template and creates trees which are then
430 * matched against the input tree. The labels are set as they are
431 * encountered; hence, partial matches may leave some pointers set
432 * and some NULL. This routines initializes all argument pointers to NULL
435 * This function returns the number of labels matched.
438 ast_scan(char *templ, ...)
443 PCCTS_AST ***label_ptrs=NULL;
447 /* make a ScanAST tree out of the template */
448 tmpl = stringparser_parse_scanast(templ, &n);
450 /* make an array out of the labels */
453 label_ptrs = (PCCTS_AST ***) calloc(n, sizeof(PCCTS_AST **));
454 require(label_ptrs!=NULL, "scan: out of memory");
457 label_ptrs[i-1] = va_arg(ap, PCCTS_AST **);
458 *(label_ptrs[i-1]) = NULL;
462 /* match the input tree against the template */
463 scanmatch(tmpl, label_ptrs, &found);
474 ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST));
475 if ( p == NULL ) {fprintf(stderr, "out of mem\n"); exit(EXIT_FAILURE);}
481 stringparser_parse_scanast(char *templ, int *num_labels)
487 stringlexer_init(&lex, templ);
488 stringparser_init(&parser, &lex);
489 t = stringparser_parse_tree(&parser);
490 *num_labels = parser.num_labels;
495 stringparser_match(StringParser *parser, int token)
497 if ( parser->token != token ) panic("bad tree in scan()");
501 * Match a tree of the form:
502 * (root child1 child2 ... childn)
506 * where the elements are integers or labeled integers.
509 stringparser_parse_tree(StringParser *parser)
511 ScanAST *t=NULL, *root, *child, *last;
513 if ( parser->token != __POUND )
515 return stringparser_parse_element(parser);
517 stringparser_match(parser,__POUND);
518 parser->token = stringscan_gettok(parser->lexer);
519 stringparser_match(parser,__LPAREN);
520 parser->token = stringscan_gettok(parser->lexer);
521 root = stringparser_parse_element(parser);
522 while ( parser->token != __RPAREN )
524 child = stringparser_parse_element(parser);
525 if ( t==NULL ) { t = child; last = t; }
526 else { last->_right = child; last = child; }
528 stringparser_match(parser,__RPAREN);
529 parser->token = stringscan_gettok(parser->lexer);
535 stringparser_parse_element(StringParser *parser)
537 static char ebuf[100];
540 if ( parser->token == __POUND )
542 return stringparser_parse_tree(parser);
544 if ( parser->token == __PERCENT )
546 parser->token = stringscan_gettok(parser->lexer);
547 stringparser_match(parser,__INT);
548 label = atoi(parser->lexer->text);
549 parser->num_labels++;
550 if ( label==0 ) panic("%%0 is an invalid label");
551 parser->token = stringscan_gettok(parser->lexer);
552 stringparser_match(parser,__COLON);
553 parser->token = stringscan_gettok(parser->lexer);
554 /* can label tokens and wildcards */
555 if ( parser->token != __INT && parser->token != __PERIOD )
556 panic("can only label tokens");
558 if ( parser->token == __INT )
560 ScanAST *p = new_scanast(atoi(parser->lexer->text));
561 parser->token = stringscan_gettok(parser->lexer);
562 p->label_num = label;
565 if ( parser->token == __PERIOD )
567 ScanAST *p = new_scanast(0); /* token of 0 is wildcard */
568 parser->token = stringscan_gettok(parser->lexer);
569 p->label_num = label;
572 sprintf(ebuf, "mismatch token in scan(): %s", scan_token_str(parser->token));
578 stringparser_init(StringParser *parser, StringLexer *input)
580 parser->lexer = input;
581 parser->token = stringscan_gettok(parser->lexer);
582 parser->num_labels = 0;
586 stringlexer_init(StringLexer *scanner, char *input)
588 scanner->text[0]='\0';
589 scanner->input = input;
591 stringscan_advance(scanner);
595 stringscan_advance(StringLexer *scanner)
597 if ( *(scanner->p) == '\0' ) scanner->c = __StringScanEOF;
598 scanner->c = *(scanner->p)++;
602 stringscan_gettok(StringLexer *scanner)
604 char *index = &scanner->text[0];
605 static char ebuf[100];
607 while ( isspace(scanner->c) ) { stringscan_advance(scanner); }
608 if ( isdigit(scanner->c) )
611 while ( isdigit(scanner->c) ) {
612 *index++ = scanner->c;
613 stringscan_advance(scanner);
618 switch ( scanner->c )
620 case '#' : stringscan_advance(scanner); return __POUND;
621 case '(' : stringscan_advance(scanner); return __LPAREN;
622 case ')' : stringscan_advance(scanner); return __RPAREN;
623 case '%' : stringscan_advance(scanner); return __PERCENT;
624 case ':' : stringscan_advance(scanner); return __COLON;
625 case '.' : stringscan_advance(scanner); return __PERIOD;
626 case '\0' : return __StringScanEOF;
627 case __StringScanEOF : return __StringScanEOF;
629 sprintf(ebuf, "invalid char in scan: '%c'", scanner->c);
632 return __StringScanEOF; // never reached
636 scan_token_str(int t)
638 if ( VALID_SCAN_TOKEN(t) ) return scan_token_tbl[t];
639 else if ( t==__StringScanEOF ) return "<end-of-string>";
640 else return "<invalid-token>";