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
) /* MR23 */ printMessage(f
," (");
76 if ( down()!=NULL
) down()->lisp(f
);
77 if ( down() != NULL
) /* MR23 */ printMessage(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
=NULL
/*MR23*/, *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
]; /* MR23 Remove "static" */
149 /*** static ***/ int tsp
= MaxTreeStackDepth
; /* MR23 Remove "static" */
151 ////static int nesting = 0; /* MR23 Not referenced */
153 if ( *cursor
== NULL
) return NULL
;
154 if ( *cursor
!=this ) sib
= *cursor
;
156 /* else, first time--start at top of template 't' */
157 tsp
= MaxTreeStackDepth
;
159 /* bottom of stack is always a NULL--"cookie" indicates "done" */
160 _push(template_stack
, &tsp
, NULL
);
164 if ( sib
==NULL
) /* hit end of sibling list */
166 sib
= _pop(template_stack
, &tsp
);
167 if ( sib
== NULL
) { *cursor
= NULL
; return NULL
; }
170 if ( sib
->type() != u
->type() )
172 /* look for another match */
173 if ( sib
->down()!=NULL
)
175 if ( sib
->right()!=NULL
) _push(template_stack
, &tsp
, sib
->right());
179 /* nothing below to try, try next sibling */
184 /* found a matching root node, try to match what's below */
185 if ( match_partial(sib
, u
) )
187 /* record sibling cursor so we can pick up next from there */
188 if ( sib
->down()!=NULL
)
190 if ( sib
->right()!=NULL
) _push(template_stack
, &tsp
, sib
->right());
191 *cursor
= sib
->down();
193 else if ( sib
->right()!=NULL
) *cursor
= sib
->right();
194 else *cursor
= _pop(template_stack
, &tsp
);
198 /* no match, keep searching */
199 if ( sib
->down()!=NULL
)
201 if ( sib
->right()!=NULL
) _push(template_stack
, &tsp
, sib
->right());
204 else sib
= sib
->right(); /* else, try to right if zip below */
208 /* are two trees exactly alike? */
215 if ( u
==NULL
) return 0;
217 for (sib
=t
; sib
!=NULL
&&u
!=NULL
; sib
=sib
->right(), u
=u
->right())
219 if ( sib
->type() != u
->type() ) return 0;
220 if ( sib
->down()!=NULL
)
221 if ( !sib
->down()->match(u
->down()) ) return 0;
226 /* Is 'u' a subtree of 't' beginning at the root? */
228 match_partial(PCCTS_AST
*t
, PCCTS_AST
*u
)
232 if ( u
==NULL
) return 1;
233 if ( t
==NULL
) return 0; /* MR23 removed unreachable code */
235 for (sib
=t
; sib
!=NULL
&&u
!=NULL
; sib
=sib
->right(), u
=u
->right())
237 if ( sib
->type() != u
->type() ) return 0;
238 if ( sib
->down()!=NULL
)
239 if ( !match_partial(sib
->down(), u
->down()) ) return 0;
244 #ifdef _MSC_VER // MR23
245 //Turn off "unreachable code" warning
246 #pragma warning(disable : 4702)
248 /* Walk the template tree 't' (matching against 'this'), filling in the
249 * 'labels' array, and setting 'n' according to how many labels were matched.
252 scanmatch(ScanAST
*t
, PCCTS_AST
**labels
[], int *n
)
257 if ( u
==NULL
) return 0;
259 for (sib
=t
; sib
!=NULL
&&u
!=NULL
; sib
=sib
->right(), u
=u
->right())
261 /* make sure tokens match; token of '0' means wildcard match */
262 if ( sib
->type() != u
->type() && sib
->type()!=0 ) return 0;
263 /* we have a matched token here; set label pointers if exists */
264 if ( sib
->label_num
>0 )
266 require(labels
!=NULL
, "label found in template, but no array of labels");
268 *(labels
[sib
->label_num
-1]) = u
;
270 /* match what's below if something there and current node is not wildcard */
271 if ( sib
->down()!=NULL
&& sib
->type()!=0 )
273 if ( sib
->down()==NULL
)
275 if ( u
->down()!=NULL
)
280 if ( !u
->down()->scanmatch(sib
->down(), labels
, n
) ) return 0;
285 #ifdef _MSC_VER // MR23
286 #pragma warning(default : 4702)
290 insert_after(PCCTS_AST
*b
)
293 if ( b
==NULL
) return;
294 /* find end of b's child list */
295 for (end
=b
; end
->right()!=NULL
; end
=end
->right()) {;}
296 end
->setRight(this->right());
304 require(b
!=NULL
, "append: NULL input tree");
305 /* find end of child list */
306 for (end
=this; end
->right()!=NULL
; end
=end
->right()) {;}
310 PCCTS_AST
*PCCTS_AST::
314 /* find end of child list */
315 for (end
=this; end
->right()!=NULL
; end
=end
->right()) {;}
319 PCCTS_AST
*PCCTS_AST::
323 /* find end of child list */
324 for (end
=this; end
->down()!=NULL
; end
=end
->down()) {;}
328 PCCTS_AST
*PCCTS_AST::
329 cut_between(PCCTS_AST
*a
, PCCTS_AST
*b
)
331 PCCTS_AST
*end
, *ret
;
332 if (a
==NULL
||b
==NULL
) return NULL
;
333 /* find node pointing to b */
334 for (end
=a
; end
->right()!=NULL
&&end
->right()!=b
; end
=end
->right())
336 if (end
->right()==NULL
) return NULL
; //ast_cut_between: a,b not connected
337 end
->setRight(NULL
); /* don't want it point to 'b' anymore */
347 SList
*list
= new SList
;
350 for (p
=this; p
!=NULL
; p
=p
->right())
362 if ( t
->down()!=NULL
) t
->down()->tfree();
363 if ( t
->right()!=NULL
) t
->right()->tfree();
381 PCCTS_AST
*PCCTS_AST::
386 require(i
>0, "sibling_index: i<=0");
390 if ( j
==i
) return t
;
397 /* Assume this is a root node of a tree--
398 * duplicate that node and what's below; ignore siblings of root node.
403 // MR9 RJV: Original version only duplicated the node and down elements.
404 // MR9 Made copies of the pointers to sibling.
405 // MR9 Changed call "down()->deepCopy()" to "down()->deepCopyBushy()"
408 PCCTS_AST
*PCCTS_AST::
411 PCCTS_AST
*u
= this->shallowCopy();
412 if ( down()!=NULL
) u
->setDown(down()->deepCopyBushy());
417 /* Copy all nodes including siblings of root. */
418 PCCTS_AST
*PCCTS_AST::
421 PCCTS_AST
*u
= this->shallowCopy();
422 /* copy the rest of the tree */
423 if ( down()!=NULL
) u
->setDown(down()->deepCopyBushy());
424 if ( right()!=NULL
) u
->setRight(right()->deepCopyBushy());
429 scanast_free(ScanAST
*t
)
431 if ( t
== NULL
) return;
432 scanast_free( t
->down() );
433 scanast_free( t
->right() );
434 free( (char *) t
); // MR1
440 * This function is like scanf(): it attempts to match a template
441 * against an input tree. A variable number of tree pointers
442 * may be set according to the '%i' labels in the template string.
445 * t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
448 * Naturally, you'd want this converted from
450 * t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
455 * This function call must be done withing a SORCERER file because SORCERER
456 * must convert the token references to the associated token number.
458 * This functions parses the template and creates trees which are then
459 * matched against the input tree. The labels are set as they are
460 * encountered; hence, partial matches may leave some pointers set
461 * and some NULL. This routines initializes all argument pointers to NULL
464 * This function returns the number of labels matched.
467 ast_scan(char *templ
, ...)
472 PCCTS_AST
***label_ptrs
=NULL
;
476 /* make a ScanAST tree out of the template */
477 tmpl
= stringparser_parse_scanast(templ
, &n
);
479 /* make an array out of the labels */
482 label_ptrs
= (PCCTS_AST
***) calloc(n
, sizeof(PCCTS_AST
**));
483 require(label_ptrs
!=NULL
, "scan: out of memory");
486 label_ptrs
[i
-1] = va_arg(ap
, PCCTS_AST
**);
487 *(label_ptrs
[i
-1]) = NULL
;
491 /* match the input tree against the template */
492 scanmatch(tmpl
, label_ptrs
, &found
);
495 free( (char *) label_ptrs
); // MR1
503 ScanAST
*p
= (ScanAST
*) calloc(1, sizeof(ScanAST
));
508 panic("out of memory\n"); // MR23
514 stringparser_parse_scanast(char *templ
, int *num_labels
)
520 stringlexer_init(&lex
, templ
);
521 stringparser_init(&parser
, &lex
);
522 t
= stringparser_parse_tree(&parser
);
523 *num_labels
= parser
.num_labels
;
528 stringparser_match(StringParser
*parser
, int token
)
530 if ( parser
->token
!= token
) panic("bad tree in scan()");
534 * Match a tree of the form:
535 * (root child1 child2 ... childn)
539 * where the elements are integers or labeled integers.
542 stringparser_parse_tree(StringParser
*parser
)
544 ScanAST
*t
=NULL
, *root
, *child
, *last
=NULL
/*MR23*/;
546 if ( parser
->token
!= __POUND
)
548 return stringparser_parse_element(parser
);
550 stringparser_match(parser
,__POUND
);
551 parser
->token
= stringscan_gettok(parser
->lexer
);
552 stringparser_match(parser
,__LPAREN
);
553 parser
->token
= stringscan_gettok(parser
->lexer
);
554 root
= stringparser_parse_element(parser
);
555 while ( parser
->token
!= __RPAREN
)
557 child
= stringparser_parse_element(parser
);
558 if ( t
==NULL
) { t
= child
; last
= t
; }
559 else { last
->_right
= child
; last
= child
; }
561 stringparser_match(parser
,__RPAREN
);
562 parser
->token
= stringscan_gettok(parser
->lexer
);
568 stringparser_parse_element(StringParser
*parser
)
573 if ( parser
->token
== __POUND
)
575 return stringparser_parse_tree(parser
);
577 if ( parser
->token
== __PERCENT
)
579 parser
->token
= stringscan_gettok(parser
->lexer
);
580 stringparser_match(parser
,__INT
);
581 label
= atoi(parser
->lexer
->text
);
582 parser
->num_labels
++;
583 if ( label
==0 ) panic("%%0 is an invalid label");
584 parser
->token
= stringscan_gettok(parser
->lexer
);
585 stringparser_match(parser
,__COLON
);
586 parser
->token
= stringscan_gettok(parser
->lexer
);
587 /* can label tokens and wildcards */
588 if ( parser
->token
!= __INT
&& parser
->token
!= __PERIOD
)
589 panic("can only label tokens");
591 if ( parser
->token
== __INT
)
593 ScanAST
*p
= new_scanast(atoi(parser
->lexer
->text
));
594 parser
->token
= stringscan_gettok(parser
->lexer
);
595 p
->label_num
= label
;
598 if ( parser
->token
== __PERIOD
)
600 ScanAST
*p
= new_scanast(0); /* token of 0 is wildcard */
601 parser
->token
= stringscan_gettok(parser
->lexer
);
602 p
->label_num
= label
;
605 sprintf(ebuf
, "mismatch token in scan(): %s", scan_token_str(parser
->token
));
611 stringparser_init(StringParser
*parser
, StringLexer
*input
)
613 parser
->lexer
= input
;
614 parser
->token
= stringscan_gettok(parser
->lexer
);
615 parser
->num_labels
= 0;
619 stringlexer_init(StringLexer
*scanner
, char *input
)
621 scanner
->text
[0]='\0';
622 scanner
->input
= input
;
624 stringscan_advance(scanner
);
628 stringscan_advance(StringLexer
*scanner
)
630 if ( *(scanner
->p
) == '\0' ) scanner
->c
= __StringScanEOF
;
631 scanner
->c
= *(scanner
->p
)++;
635 stringscan_gettok(StringLexer
*scanner
)
637 char *index
= &scanner
->text
[0];
638 char ebuf
[100]; /* MR23 Remove static */
640 while ( isspace(scanner
->c
) ) { stringscan_advance(scanner
); }
641 if ( isdigit(scanner
->c
) )
644 while ( isdigit(scanner
->c
) ) {
645 *index
++ = (char) /* static_cast<char> */ (scanner
->c
); // MR23
646 stringscan_advance(scanner
);
651 switch ( scanner
->c
)
653 case '#' : stringscan_advance(scanner
); return __POUND
;
654 case '(' : stringscan_advance(scanner
); return __LPAREN
;
655 case ')' : stringscan_advance(scanner
); return __RPAREN
;
656 case '%' : stringscan_advance(scanner
); return __PERCENT
;
657 case ':' : stringscan_advance(scanner
); return __COLON
;
658 case '.' : stringscan_advance(scanner
); return __PERIOD
;
659 case '\0' : return __StringScanEOF
;
660 case __StringScanEOF
: return __StringScanEOF
;
662 sprintf(ebuf
, "invalid char in scan: '%c'", scanner
->c
);
665 return __StringScanEOF
; // never reached
668 const char *PCCTS_AST:: /* MR20 const */
669 scan_token_str(int t
)
671 if ( VALID_SCAN_TOKEN(t
) ) return scan_token_tbl
[t
];
672 else if ( t
==__StringScanEOF
) return "<end-of-string>";
673 else return "<invalid-token>";
677 int PCCTS_AST::printMessage(FILE* pFile
, const char* pFormat
, ...)
680 va_start( marker
, pFormat
);
681 int iRet
= vfprintf(pFile
, pFormat
, marker
);