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