/* | |
* PCCTSAST.C | |
* | |
* SOFTWARE RIGHTS | |
* | |
* We reserve no LEGAL rights to SORCERER -- SORCERER is in the public | |
* domain. An individual or company may do whatever they wish with | |
* source code distributed with SORCERER or the code generated by | |
* SORCERER, including the incorporation of SORCERER, or its output, into | |
* commerical software. | |
* | |
* We encourage users to develop software with SORCERER. However, we do | |
* ask that credit is given to us for developing SORCERER. By "credit", | |
* we mean that if you incorporate our source code into one of your | |
* programs (commercial product, research project, or otherwise) that you | |
* acknowledge this fact somewhere in the documentation, research report, | |
* etc... If you like SORCERER and have developed a nice tool with the | |
* output, please mention that you developed it using SORCERER. In | |
* addition, we ask that this header remain intact in our source code. | |
* As long as these guidelines are kept, we expect to continue enhancing | |
* this system and expect to make other tools available as they are | |
* completed. | |
* | |
* SORCERER 1.00B14 and ANTLR 1.33 | |
* Terence Parr | |
* Parr Research Corporation | |
* AHPCRC, University of Minnesota | |
* 1992-1998 | |
*/ | |
#define ANTLR_SUPPORT_CODE | |
#include "pcctscfg.h" | |
#include "PCCTSAST.h" | |
#include "pccts_stdarg.h" | |
PCCTS_NAMESPACE_STD | |
#include <ctype.h> | |
//#include "SList.h" | |
/* String Scanning/Parsing Stuff */ | |
const char *PCCTS_AST::scan_token_tbl[] = { /* MR20 const */ | |
"invalid", /* 0 */ | |
"LPAREN", /* 1 */ | |
"RPAREN", /* 2 */ | |
"PERCENT", /* 3 */ | |
"INT", /* 4 */ | |
"COLON", /* 5 */ | |
"POUND", /* 6 */ | |
"PERIOD", /* 7 */ | |
}; | |
void PCCTS_AST:: | |
addChild(PCCTS_AST *t) | |
{ | |
if ( t==NULL ) return; | |
PCCTS_AST *s = down(); | |
if ( s!=NULL ) | |
{ | |
while ( s->right()!=NULL ) s = s->right(); | |
s->setRight(t); | |
} | |
else | |
this->setDown(t); | |
} | |
void PCCTS_AST:: | |
lisp(FILE *f) | |
{ | |
if ( down() != NULL ) fprintf(f," ("); | |
lisp_action(f); | |
if ( down()!=NULL ) down()->lisp(f); | |
if ( down() != NULL ) fprintf(f," )"); | |
if ( right()!=NULL ) right()->lisp(f); | |
} | |
/* build a tree (root child1 child2 ... NULL) | |
* If root is NULL, simply make the children siblings and return ptr | |
* to 1st sibling (child1). If root is not single node, return NULL. | |
* | |
* Siblings that are actually sibling lists themselves are handled | |
* correctly. For example #( NULL, #( NULL, A, B, C), D) results | |
* in the tree ( NULL A B C D ). | |
* | |
* Requires at least two parameters with the last one being NULL. If | |
* both are NULL, return NULL. | |
* | |
* The down() and right() down/right pointers are used to make the tree. | |
*/ | |
PCCTS_AST *PCCTS_AST:: | |
make(PCCTS_AST *rt, ...) | |
{ | |
va_list ap; | |
register PCCTS_AST *child, *sibling=NULL, *tail, *w; | |
PCCTS_AST *root; | |
va_start(ap, rt); | |
root = rt; | |
if ( root != NULL ) | |
if ( root->down() != NULL ) return NULL; | |
child = va_arg(ap, PCCTS_AST *); | |
while ( child != NULL ) | |
{ | |
/* find end of child */ | |
for (w=child; w->right()!=NULL; w=w->right()) {;} | |
if ( sibling == NULL ) {sibling = child; tail = w;} | |
else {tail->setRight(child); tail = w;} | |
child = va_arg(ap, PCCTS_AST *); | |
} | |
if ( root==NULL ) root = sibling; | |
else root->setDown(sibling); | |
va_end(ap); | |
return root; | |
} | |
/* The following push and pop routines are only used by ast_find_all() */ | |
void PCCTS_AST:: | |
_push(PCCTS_AST **st, int *sp, PCCTS_AST *e) | |
{ | |
(*sp)--; | |
require((*sp)>=0, "stack overflow"); | |
st[(*sp)] = e; | |
} | |
PCCTS_AST *PCCTS_AST:: | |
_pop(PCCTS_AST **st, int *sp) | |
{ | |
PCCTS_AST *e = st[*sp]; | |
(*sp)++; | |
require((*sp)<=MaxTreeStackDepth, "stack underflow"); | |
return e; | |
} | |
/* Find all occurrences of u in t. | |
* 'cursor' must be initialized to 't'. It eventually | |
* returns NULL when no more occurrences of 'u' are found. | |
*/ | |
PCCTS_AST *PCCTS_AST:: | |
ast_find_all(PCCTS_AST *u, PCCTS_AST **cursor) | |
{ | |
PCCTS_AST *sib; | |
static PCCTS_AST *template_stack[MaxTreeStackDepth]; | |
static int tsp = MaxTreeStackDepth; | |
static int nesting = 0; | |
if ( *cursor == NULL ) return NULL; | |
if ( *cursor!=this ) sib = *cursor; | |
else { | |
/* else, first time--start at top of template 't' */ | |
tsp = MaxTreeStackDepth; | |
sib = this; | |
/* bottom of stack is always a NULL--"cookie" indicates "done" */ | |
_push(template_stack, &tsp, NULL); | |
} | |
keep_looking: | |
if ( sib==NULL ) /* hit end of sibling list */ | |
{ | |
sib = _pop(template_stack, &tsp); | |
if ( sib == NULL ) { *cursor = NULL; return NULL; } | |
} | |
if ( sib->type() != u->type() ) | |
{ | |
/* look for another match */ | |
if ( sib->down()!=NULL ) | |
{ | |
if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right()); | |
sib=sib->down(); | |
goto keep_looking; | |
} | |
/* nothing below to try, try next sibling */ | |
sib=sib->right(); | |
goto keep_looking; | |
} | |
/* found a matching root node, try to match what's below */ | |
if ( match_partial(sib, u) ) | |
{ | |
/* record sibling cursor so we can pick up next from there */ | |
if ( sib->down()!=NULL ) | |
{ | |
if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right()); | |
*cursor = sib->down(); | |
} | |
else if ( sib->right()!=NULL ) *cursor = sib->right(); | |
else *cursor = _pop(template_stack, &tsp); | |
return sib; | |
} | |
/* no match, keep searching */ | |
if ( sib->down()!=NULL ) | |
{ | |
if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right()); | |
sib=sib->down(); | |
} | |
else sib = sib->right(); /* else, try to right if zip below */ | |
goto keep_looking; | |
} | |
/* are two trees exactly alike? */ | |
int PCCTS_AST:: | |
match(PCCTS_AST *u) | |
{ | |
PCCTS_AST *t = this; | |
PCCTS_AST *sib; | |
if ( u==NULL ) return 0; | |
for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right()) | |
{ | |
if ( sib->type() != u->type() ) return 0; | |
if ( sib->down()!=NULL ) | |
if ( !sib->down()->match(u->down()) ) return 0; | |
} | |
return 1; | |
} | |
/* Is 'u' a subtree of 't' beginning at the root? */ | |
int PCCTS_AST:: | |
match_partial(PCCTS_AST *t, PCCTS_AST *u) | |
{ | |
PCCTS_AST *sib; | |
if ( u==NULL ) return 1; | |
if ( t==NULL ) if ( u!=NULL ) return 0; else return 1; | |
for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right()) | |
{ | |
if ( sib->type() != u->type() ) return 0; | |
if ( sib->down()!=NULL ) | |
if ( !match_partial(sib->down(), u->down()) ) return 0; | |
} | |
return 1; | |
} | |
/* Walk the template tree 't' (matching against 'this'), filling in the | |
* 'labels' array, and setting 'n' according to how many labels were matched. | |
*/ | |
int PCCTS_AST:: | |
scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n) | |
{ | |
ScanAST *sib; | |
PCCTS_AST *u = this; | |
if ( u==NULL ) return 0; | |
for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right()) | |
{ | |
/* make sure tokens match; token of '0' means wildcard match */ | |
if ( sib->type() != u->type() && sib->type()!=0 ) return 0; | |
/* we have a matched token here; set label pointers if exists */ | |
if ( sib->label_num>0 ) | |
{ | |
require(labels!=NULL, "label found in template, but no array of labels"); | |
(*n)++; | |
*(labels[sib->label_num-1]) = u; | |
} | |
/* match what's below if something there and current node is not wildcard */ | |
if ( sib->down()!=NULL && sib->type()!=0 ) | |
{ | |
if ( sib->down()==NULL ) if ( u->down()!=NULL ) return 0; else return 1; | |
if ( !u->down()->scanmatch(sib->down(), labels, n) ) return 0; | |
} | |
} | |
return 1; | |
} | |
void PCCTS_AST:: | |
insert_after(PCCTS_AST *b) | |
{ | |
PCCTS_AST *end; | |
if ( b==NULL ) return; | |
/* find end of b's child list */ | |
for (end=b; end->right()!=NULL; end=end->right()) {;} | |
end->setRight(this->right()); | |
this->setRight(b); | |
} | |
void PCCTS_AST:: | |
append(PCCTS_AST *b) | |
{ | |
PCCTS_AST *end; | |
require(b!=NULL, "append: NULL input tree"); | |
/* find end of child list */ | |
for (end=this; end->right()!=NULL; end=end->right()) {;} | |
end->setRight(b); | |
} | |
PCCTS_AST *PCCTS_AST:: | |
tail() | |
{ | |
PCCTS_AST *end; | |
/* find end of child list */ | |
for (end=this; end->right()!=NULL; end=end->right()) {;} | |
return end; | |
} | |
PCCTS_AST *PCCTS_AST:: | |
bottom() | |
{ | |
PCCTS_AST *end; | |
/* find end of child list */ | |
for (end=this; end->down()!=NULL; end=end->down()) {;} | |
return end; | |
} | |
PCCTS_AST *PCCTS_AST:: | |
cut_between(PCCTS_AST *a, PCCTS_AST *b) | |
{ | |
PCCTS_AST *end, *ret; | |
if (a==NULL||b==NULL) return NULL; | |
/* find node pointing to b */ | |
for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right()) | |
{;} | |
if (end->right()==NULL) return NULL; //ast_cut_between: a,b not connected | |
end->setRight(NULL); /* don't want it point to 'b' anymore */ | |
ret = a->right(); | |
a->setRight(b); | |
return ret; | |
} | |
#ifdef NOT_YET | |
SList *PCCTS_AST:: | |
to_slist() | |
{ | |
SList *list = new SList; | |
PCCTS_AST *p; | |
for (p=this; p!=NULL; p=p->right()) | |
{ | |
list->add(p); | |
} | |
return list; | |
} | |
#endif | |
void PCCTS_AST:: | |
tfree() | |
{ | |
PCCTS_AST *t = this; | |
if ( t->down()!=NULL ) t->down()->tfree(); | |
if ( t->right()!=NULL ) t->right()->tfree(); | |
delete t; | |
} | |
int PCCTS_AST:: | |
nsiblings() | |
{ | |
PCCTS_AST *t = this; | |
int n=0; | |
while ( t!=NULL ) | |
{ | |
n++; | |
t = t->right(); | |
} | |
return n; | |
} | |
PCCTS_AST *PCCTS_AST:: | |
sibling_index(int i) | |
{ | |
PCCTS_AST *t = this; | |
int j=1; | |
require(i>0, "sibling_index: i<=0"); | |
while ( t!=NULL ) | |
{ | |
if ( j==i ) return t; | |
j++; | |
t = t->right(); | |
} | |
return NULL; | |
} | |
/* Assume this is a root node of a tree-- | |
* duplicate that node and what's below; ignore siblings of root node. | |
*/ | |
// MR9 23-Sep-97 RJV | |
// MR9 | |
// MR9 RJV: Original version only duplicated the node and down elements. | |
// MR9 Made copies of the pointers to sibling. | |
// MR9 Changed call "down()->deepCopy()" to "down()->deepCopyBushy()" | |
// MR9 | |
PCCTS_AST *PCCTS_AST:: | |
deepCopy() | |
{ | |
PCCTS_AST *u = this->shallowCopy(); | |
if ( down()!=NULL ) u->setDown(down()->deepCopyBushy()); | |
u->setRight(NULL); | |
return u; | |
} | |
/* Copy all nodes including siblings of root. */ | |
PCCTS_AST *PCCTS_AST:: | |
deepCopyBushy() | |
{ | |
PCCTS_AST *u = this->shallowCopy(); | |
/* copy the rest of the tree */ | |
if ( down()!=NULL ) u->setDown(down()->deepCopyBushy()); | |
if ( right()!=NULL ) u->setRight(right()->deepCopyBushy()); | |
return u; | |
} | |
void PCCTS_AST:: | |
scanast_free(ScanAST *t) | |
{ | |
if ( t == NULL ) return; | |
scanast_free( t->down() ); | |
scanast_free( t->right() ); | |
free( (char *) t ); // MR1 | |
} | |
/* | |
* scan | |
* | |
* This function is like scanf(): it attempts to match a template | |
* against an input tree. A variable number of tree pointers | |
* may be set according to the '%i' labels in the template string. | |
* For example: | |
* | |
* t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )", | |
* &w, &x, &y, &z); | |
* | |
* Naturally, you'd want this converted from | |
* | |
* t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )", | |
* &w, &x, &y, &z); | |
* | |
* by SORCERER. | |
* | |
* This function call must be done withing a SORCERER file because SORCERER | |
* must convert the token references to the associated token number. | |
* | |
* This functions parses the template and creates trees which are then | |
* matched against the input tree. The labels are set as they are | |
* encountered; hence, partial matches may leave some pointers set | |
* and some NULL. This routines initializes all argument pointers to NULL | |
* at the beginning. | |
* | |
* This function returns the number of labels matched. | |
*/ | |
int PCCTS_AST:: | |
ast_scan(char *templ, ...) | |
{ | |
va_list ap; | |
ScanAST *tmpl; | |
int n, i, found=0; | |
PCCTS_AST ***label_ptrs=NULL; | |
va_start(ap, templ); | |
/* make a ScanAST tree out of the template */ | |
tmpl = stringparser_parse_scanast(templ, &n); | |
/* make an array out of the labels */ | |
if ( n>0 ) | |
{ | |
label_ptrs = (PCCTS_AST ***) calloc(n, sizeof(PCCTS_AST **)); | |
require(label_ptrs!=NULL, "scan: out of memory"); | |
for (i=1; i<=n; i++) | |
{ | |
label_ptrs[i-1] = va_arg(ap, PCCTS_AST **); | |
*(label_ptrs[i-1]) = NULL; | |
} | |
} | |
/* match the input tree against the template */ | |
scanmatch(tmpl, label_ptrs, &found); | |
scanast_free(tmpl); | |
free( (char *) label_ptrs); // MR1 | |
return found; | |
} | |
ScanAST *PCCTS_AST:: | |
new_scanast(int tok) | |
{ | |
ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST)); | |
// | |
// 7-Apr-97 133MR1 | |
// | |
if ( p == NULL ) { // MR1 | |
fprintf(stderr, "out of mem\n"); // MR1 | |
exit(PCCTS_EXIT_FAILURE); // MR1 | |
}; // MR1 | |
p->_token = tok; | |
return p; | |
} | |
ScanAST *PCCTS_AST:: | |
stringparser_parse_scanast(char *templ, int *num_labels) | |
{ | |
StringLexer lex; | |
StringParser parser; | |
ScanAST *t; | |
stringlexer_init(&lex, templ); | |
stringparser_init(&parser, &lex); | |
t = stringparser_parse_tree(&parser); | |
*num_labels = parser.num_labels; | |
return t; | |
} | |
void PCCTS_AST:: | |
stringparser_match(StringParser *parser, int token) | |
{ | |
if ( parser->token != token ) panic("bad tree in scan()"); | |
} | |
/* | |
* Match a tree of the form: | |
* (root child1 child2 ... childn) | |
* or, | |
* node | |
* | |
* where the elements are integers or labeled integers. | |
*/ | |
ScanAST *PCCTS_AST:: | |
stringparser_parse_tree(StringParser *parser) | |
{ | |
ScanAST *t=NULL, *root, *child, *last; | |
if ( parser->token != __POUND ) | |
{ | |
return stringparser_parse_element(parser); | |
} | |
stringparser_match(parser,__POUND); | |
parser->token = stringscan_gettok(parser->lexer); | |
stringparser_match(parser,__LPAREN); | |
parser->token = stringscan_gettok(parser->lexer); | |
root = stringparser_parse_element(parser); | |
while ( parser->token != __RPAREN ) | |
{ | |
child = stringparser_parse_element(parser); | |
if ( t==NULL ) { t = child; last = t; } | |
else { last->_right = child; last = child; } | |
} | |
stringparser_match(parser,__RPAREN); | |
parser->token = stringscan_gettok(parser->lexer); | |
root->_down = t; | |
return root; | |
} | |
ScanAST *PCCTS_AST:: | |
stringparser_parse_element(StringParser *parser) | |
{ | |
static char ebuf[100]; | |
int label = 0; | |
if ( parser->token == __POUND ) | |
{ | |
return stringparser_parse_tree(parser); | |
} | |
if ( parser->token == __PERCENT ) | |
{ | |
parser->token = stringscan_gettok(parser->lexer); | |
stringparser_match(parser,__INT); | |
label = atoi(parser->lexer->text); | |
parser->num_labels++; | |
if ( label==0 ) panic("%%0 is an invalid label"); | |
parser->token = stringscan_gettok(parser->lexer); | |
stringparser_match(parser,__COLON); | |
parser->token = stringscan_gettok(parser->lexer); | |
/* can label tokens and wildcards */ | |
if ( parser->token != __INT && parser->token != __PERIOD ) | |
panic("can only label tokens"); | |
} | |
if ( parser->token == __INT ) | |
{ | |
ScanAST *p = new_scanast(atoi(parser->lexer->text)); | |
parser->token = stringscan_gettok(parser->lexer); | |
p->label_num = label; | |
return p; | |
} | |
if ( parser->token == __PERIOD ) | |
{ | |
ScanAST *p = new_scanast(0); /* token of 0 is wildcard */ | |
parser->token = stringscan_gettok(parser->lexer); | |
p->label_num = label; | |
return p; | |
} | |
sprintf(ebuf, "mismatch token in scan(): %s", scan_token_str(parser->token)); | |
panic(ebuf); | |
return NULL; | |
} | |
void PCCTS_AST:: | |
stringparser_init(StringParser *parser, StringLexer *input) | |
{ | |
parser->lexer = input; | |
parser->token = stringscan_gettok(parser->lexer); | |
parser->num_labels = 0; | |
} | |
void PCCTS_AST:: | |
stringlexer_init(StringLexer *scanner, char *input) | |
{ | |
scanner->text[0]='\0'; | |
scanner->input = input; | |
scanner->p = input; | |
stringscan_advance(scanner); | |
} | |
void PCCTS_AST:: | |
stringscan_advance(StringLexer *scanner) | |
{ | |
if ( *(scanner->p) == '\0' ) scanner->c = __StringScanEOF; | |
scanner->c = *(scanner->p)++; | |
} | |
int PCCTS_AST:: | |
stringscan_gettok(StringLexer *scanner) | |
{ | |
char *index = &scanner->text[0]; | |
static char ebuf[100]; | |
while ( isspace(scanner->c) ) { stringscan_advance(scanner); } | |
if ( isdigit(scanner->c) ) | |
{ | |
int tok = __INT; | |
while ( isdigit(scanner->c) ) { | |
*index++ = scanner->c; | |
stringscan_advance(scanner); | |
} | |
*index = '\0'; | |
return tok; | |
} | |
switch ( scanner->c ) | |
{ | |
case '#' : stringscan_advance(scanner); return __POUND; | |
case '(' : stringscan_advance(scanner); return __LPAREN; | |
case ')' : stringscan_advance(scanner); return __RPAREN; | |
case '%' : stringscan_advance(scanner); return __PERCENT; | |
case ':' : stringscan_advance(scanner); return __COLON; | |
case '.' : stringscan_advance(scanner); return __PERIOD; | |
case '\0' : return __StringScanEOF; | |
case __StringScanEOF : return __StringScanEOF; | |
default : | |
sprintf(ebuf, "invalid char in scan: '%c'", scanner->c); | |
panic(ebuf); | |
} | |
return __StringScanEOF; // never reached | |
} | |
const char *PCCTS_AST:: /* MR20 const */ | |
scan_token_str(int t) | |
{ | |
if ( VALID_SCAN_TOKEN(t) ) return scan_token_tbl[t]; | |
else if ( t==__StringScanEOF ) return "<end-of-string>"; | |
else return "<invalid-token>"; | |
} |