X-Git-Url: https://git.proxmox.com/?p=mirror_edk2.git;a=blobdiff_plain;f=Tools%2FSource%2FTianoTools%2FPccts%2Fh%2FPCCTSAST.cpp;fp=Tools%2FSource%2FTianoTools%2FPccts%2Fh%2FPCCTSAST.cpp;h=0000000000000000000000000000000000000000;hp=a8249cdac0a26110238e83806d3d0b63441c8b19;hb=feccee87a78e68d575dbdf44b34ca0cb5a21ea8d;hpb=214b0d1914b48d651b25e58f321ddb77a46903b8 diff --git a/Tools/Source/TianoTools/Pccts/h/PCCTSAST.cpp b/Tools/Source/TianoTools/Pccts/h/PCCTSAST.cpp deleted file mode 100644 index a8249cdac0..0000000000 --- a/Tools/Source/TianoTools/Pccts/h/PCCTSAST.cpp +++ /dev/null @@ -1,684 +0,0 @@ -/* - * 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-2000 - */ - -#define ANTLR_SUPPORT_CODE - -#include "pcctscfg.h" - -#include "PCCTSAST.h" -#include "pccts_stdarg.h" - -PCCTS_NAMESPACE_STD - -#include - -//#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 ) /* MR23 */ printMessage(f," ("); - lisp_action(f); - if ( down()!=NULL ) down()->lisp(f); - if ( down() != NULL ) /* MR23 */ printMessage(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=NULL /*MR23*/, *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]; /* MR23 Remove "static" */ - /*** static ***/ int tsp = MaxTreeStackDepth; /* MR23 Remove "static" */ - -////static int nesting = 0; /* MR23 Not referenced */ - - 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 ) return 0; /* MR23 removed unreachable code */ - - 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; -} - -#ifdef _MSC_VER // MR23 -//Turn off "unreachable code" warning -#pragma warning(disable : 4702) -#endif -/* 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; -} -#ifdef _MSC_VER // MR23 -#pragma warning(default : 4702) -#endif - -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 ) - panic("out of memory\n"); // MR23 - 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=NULL /*MR23*/; - - 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) -{ - 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]; - char ebuf[100]; /* MR23 Remove static */ - - while ( isspace(scanner->c) ) { stringscan_advance(scanner); } - if ( isdigit(scanner->c) ) - { - int tok = __INT; - while ( isdigit(scanner->c) ) { - *index++ = (char) /* static_cast */ (scanner->c); // MR23 - 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 ""; - else return ""; -} - -//MR23 -int PCCTS_AST::printMessage(FILE* pFile, const char* pFormat, ...) -{ - va_list marker; - va_start( marker, pFormat ); - int iRet = vfprintf(pFile, pFormat, marker); - va_end( marker ); - return iRet; -}