diff options
Diffstat (limited to 'src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/h/PCCTSAST.cpp')
| -rw-r--r-- | src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/h/PCCTSAST.cpp | 684 |
1 files changed, 684 insertions, 0 deletions
diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/h/PCCTSAST.cpp b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/h/PCCTSAST.cpp new file mode 100644 index 00000000..c29b69fa --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/h/PCCTSAST.cpp @@ -0,0 +1,684 @@ +/* + * 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 <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 ) /* 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<char> */ (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 "<end-of-string>"; + else return "<invalid-token>"; +} + +//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; +} |