pd.if.org Git - pccts/blob - h/PCCTSAST.cpp

   1 /*
   2  * PCCTSAST.C
   3  *
   4  * SOFTWARE RIGHTS
   5  *
   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.
  11  *
  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
  22  * completed.
  23  *
  24  * SORCERER 1.00B14 and ANTLR 1.33
  25  * Terence Parr
  26  * Parr Research Corporation
  27  * AHPCRC, University of Minnesota
  28  * 1992-1995
  29  */
  30
  31 #define ANTLR_SUPPORT_CODE
  32
  33 #include "PCCTSAST.h"
  34 #include <stdarg.h>
  35 #include <ctype.h>
  36 //#include "SList.h"
  37
  38                /* String Scanning/Parsing Stuff */
  39
  40 char *PCCTS_AST::scan_token_tbl[] = {
  41         "invalid",      /*      0 */
  42         "LPAREN",       /*      1 */
  43         "RPAREN",       /*      2 */
  44         "PERCENT",      /*      3 */
  45         "INT",          /*      4 */
  46         "COLON",        /*      5 */
  47         "POUND",        /*      6 */
  48         "PERIOD",       /*      7 */
  49 };
  50
  51 void PCCTS_AST::
  52 addChild(PCCTS_AST *t)
  53 {
  54         if ( t==NULL ) return;
  55         PCCTS_AST *s = down();
  56         if ( s!=NULL )
  57         {
  58                 while ( s->right()!=NULL ) s = s->right();
  59                 s->setRight(t);
  60         }
  61         else
  62                 this->setDown(t);
  63 }
  64
  65 void PCCTS_AST::
  66 lisp(FILE *f)
  67 {
  68         if ( down() != NULL ) fprintf(f," (");
  69         lisp_action(f);
  70         if ( down()!=NULL ) down()->lisp(f);
  71         if ( down() != NULL ) fprintf(f," )");
  72         if ( right()!=NULL ) right()->lisp(f);
  73 }
  74
  75 /* build a tree (root child1 child2 ... NULL)
  76  * If root is NULL, simply make the children siblings and return ptr
  77  * to 1st sibling (child1).  If root is not single node, return NULL.
  78  *
  79  * Siblings that are actually sibling lists themselves are handled
  80  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
  81  * in the tree ( NULL A B C D ).
  82  *
  83  * Requires at least two parameters with the last one being NULL.  If
  84  * both are NULL, return NULL.
  85  *
  86  * The down() and right() down/right pointers are used to make the tree.
  87  */
  88 PCCTS_AST *PCCTS_AST::
  89 make(PCCTS_AST *rt, ...)
  90 {
  91         va_list ap;
  92         register PCCTS_AST *child, *sibling=NULL, *tail, *w;
  93         PCCTS_AST *root;
  94
  95         va_start(ap, rt);
  96         root = rt;
  97
  98         if ( root != NULL )
  99                 if ( root->down() != NULL ) return NULL;
 100         child = va_arg(ap, PCCTS_AST *);
 101         while ( child != NULL )
 102         {
 103                 /* find end of child */
 104                 for (w=child; w->right()!=NULL; w=w->right()) {;}
 105                 if ( sibling == NULL ) {sibling = child; tail = w;}
 106                 else {tail->setRight(child); tail = w;}
 107                 child = va_arg(ap, PCCTS_AST *);
 108         }
 109         if ( root==NULL ) root = sibling;
 110         else root->setDown(sibling);
 111         va_end(ap);
 112         return root;
 113 }
 114
 115 /* The following push and pop routines are only used by ast_find_all() */
 116
 117 void PCCTS_AST::
 118 _push(PCCTS_AST **st, int *sp, PCCTS_AST *e)
 119 {
 120         (*sp)--;
 121         require((*sp)>=0, "stack overflow");
 122         st[(*sp)] = e;
 123 }
 124
 125 PCCTS_AST *PCCTS_AST::
 126 _pop(PCCTS_AST **st, int *sp)
 127 {
 128         PCCTS_AST *e = st[*sp];
 129         (*sp)++;
 130         require((*sp)<=MaxTreeStackDepth, "stack underflow");
 131         return e;
 132 }
 133
 134 /* Find all occurrences of u in t.
 135  * 'cursor' must be initialized to 't'.  It eventually
 136  * returns NULL when no more occurrences of 'u' are found.
 137  */
 138 PCCTS_AST *PCCTS_AST::
 139 ast_find_all(PCCTS_AST *u, PCCTS_AST **cursor)
 140 {
 141         PCCTS_AST *sib;
 142         static PCCTS_AST *template_stack[MaxTreeStackDepth];
 143         static int tsp = MaxTreeStackDepth;
 144         static int nesting = 0;
 145
 146         if ( *cursor == NULL ) return NULL;
 147         if ( *cursor!=this ) sib = *cursor;
 148         else {
 149                 /* else, first time--start at top of template 't' */
 150                 tsp = MaxTreeStackDepth;
 151                 sib = this;
 152                 /* bottom of stack is always a NULL--"cookie" indicates "done" */
 153                 _push(template_stack, &tsp, NULL);
 154         }
 155
 156 keep_looking:
 157         if ( sib==NULL )        /* hit end of sibling list */
 158         {
 159                 sib = _pop(template_stack, &tsp);
 160                 if ( sib == NULL ) { *cursor = NULL; return NULL; }
 161         }
 162
 163         if ( sib->type() != u->type() )
 164         {
 165                 /* look for another match */
 166                 if ( sib->down()!=NULL )
 167                 {
 168                         if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
 169                         sib=sib->down();
 170                         goto keep_looking;
 171                 }
 172                 /* nothing below to try, try next sibling */
 173                 sib=sib->right();
 174                 goto keep_looking;
 175         }
 176
 177         /* found a matching root node, try to match what's below */
 178         if ( match_partial(sib, u) )
 179         {
 180                 /* record sibling cursor so we can pick up next from there */
 181                 if ( sib->down()!=NULL )
 182                 {
 183                         if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
 184                         *cursor = sib->down();
 185                 }
 186                 else if ( sib->right()!=NULL ) *cursor = sib->right();
 187                 else *cursor = _pop(template_stack, &tsp);
 188                 return sib;
 189         }
 190
 191         /* no match, keep searching */
 192         if ( sib->down()!=NULL )
 193         {
 194                 if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
 195                 sib=sib->down();
 196         }
 197         else sib = sib->right();        /* else, try to right if zip below */
 198         goto keep_looking;
 199 }
 200
 201 /* are two trees exactly alike? */
 202 int PCCTS_AST::
 203 match(PCCTS_AST *u)
 204 {
 205         PCCTS_AST *t = this;
 206         PCCTS_AST *sib;
 207
 208         if ( u==NULL ) return 0;
 209
 210         for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
 211         {
 212                 if ( sib->type() != u->type() ) return 0;
 213                 if ( sib->down()!=NULL )
 214                         if ( !sib->down()->match(u->down()) ) return 0;
 215         }
 216         return 1;
 217 }
 218
 219 /* Is 'u' a subtree of 't' beginning at the root? */
 220 int PCCTS_AST::
 221 match_partial(PCCTS_AST *t, PCCTS_AST *u)
 222 {
 223         PCCTS_AST *sib;
 224
 225         if ( u==NULL ) return 1;
 226         if ( t==NULL ) if ( u!=NULL ) return 0; else return 1;
 227
 228         for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
 229         {
 230                 if ( sib->type() != u->type() ) return 0;
 231                 if ( sib->down()!=NULL )
 232                         if ( !match_partial(sib->down(), u->down()) ) return 0;
 233         }
 234         return 1;
 235 }
 236
 237 /* Walk the template tree 't' (matching against 'this'), filling in the
 238  * 'labels' array, and setting 'n' according to how many labels were matched.
 239  */
 240 int PCCTS_AST::
 241 scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n)
 242 {
 243         ScanAST *sib;
 244         PCCTS_AST *u = this;
 245
 246         if ( u==NULL ) return 0;
 247
 248         for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
 249         {
 250                 /* make sure tokens match; token of '0' means wildcard match */
 251                 if ( sib->type() != u->type() && sib->type()!=0 ) return 0;
 252                 /* we have a matched token here; set label pointers if exists */
 253                 if ( sib->label_num>0 )
 254                 {
 255                         require(labels!=NULL, "label found in template, but no array of labels");
 256                         (*n)++;
 257                         *(labels[sib->label_num-1]) = u;
 258                 }
 259                 /* match what's below if something there and current node is not wildcard */
 260                 if ( sib->down()!=NULL && sib->type()!=0 )
 261                 {
 262                         if ( sib->down()==NULL ) if ( u->down()!=NULL ) return 0; else return 1;
 263                         if ( !u->down()->scanmatch(sib->down(), labels, n) ) return 0;
 264                 }
 265         }
 266         return 1;
 267 }
 268
 269 void PCCTS_AST::
 270 insert_after(PCCTS_AST *b)
 271 {
 272         PCCTS_AST *end;
 273         if ( b==NULL ) return;
 274         /* find end of b's child list */
 275         for (end=b; end->right()!=NULL; end=end->right()) {;}
 276         end->setRight(this->right());
 277         this->setRight(b);
 278 }
 279
 280 void PCCTS_AST::
 281 append(PCCTS_AST *b)
 282 {
 283         PCCTS_AST *end;
 284         require(b!=NULL, "append: NULL input tree");
 285         /* find end of child list */
 286         for (end=this; end->right()!=NULL; end=end->right()) {;}
 287         end->setRight(b);
 288 }
 289
 290 PCCTS_AST *PCCTS_AST::
 291 tail()
 292 {
 293         PCCTS_AST *end;
 294         /* find end of child list */
 295         for (end=this; end->right()!=NULL; end=end->right()) {;}
 296         return end;
 297 }
 298
 299 PCCTS_AST *PCCTS_AST::
 300 bottom()
 301 {
 302         PCCTS_AST *end;
 303         /* find end of child list */
 304         for (end=this; end->down()!=NULL; end=end->down()) {;}
 305         return end;
 306 }
 307
 308 PCCTS_AST *PCCTS_AST::
 309 cut_between(PCCTS_AST *a, PCCTS_AST *b)
 310 {
 311         PCCTS_AST *end, *ret;
 312         if (a==NULL||b==NULL) return NULL;
 313         /* find node pointing to b */
 314         for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right())
 315                 {;}
 316         if (end->right()==NULL) return NULL; //ast_cut_between: a,b not connected
 317         end->setRight(NULL);    /* don't want it point to 'b' anymore */
 318         ret = a->right();
 319         a->setRight(b);
 320         return ret;
 321 }
 322
 323 #ifdef NOT_YET
 324 SList *PCCTS_AST::
 325 to_slist()
 326 {
 327         SList *list = new SList;
 328         PCCTS_AST *p;
 329
 330         for (p=this; p!=NULL; p=p->right())
 331         {
 332                 list->add(p);
 333         }
 334         return list;
 335 }
 336 #endif
 337
 338 void PCCTS_AST::
 339 tfree()
 340 {
 341         PCCTS_AST *t = this;
 342     if ( t->down()!=NULL ) t->down()->tfree();
 343     if ( t->right()!=NULL ) t->right()->tfree();
 344     delete t;
 345 }
 346
 347 int PCCTS_AST::
 348 nsiblings()
 349 {
 350         PCCTS_AST *t = this;
 351         int n=0;
 352
 353         while ( t!=NULL )
 354         {
 355                 n++;
 356                 t = t->right();
 357         }
 358         return n;
 359 }
 360
 361 PCCTS_AST *PCCTS_AST::
 362 sibling_index(int i)
 363 {
 364         PCCTS_AST *t = this;
 365         int j=1;
 366         require(i>0, "sibling_index: i<=0");
 367
 368         while ( t!=NULL )
 369         {
 370                 if ( j==i ) return t;
 371                 j++;
 372                 t = t->right();
 373         }
 374         return NULL;
 375 }
 376
 377 /* Assume this is a root node of a tree--
 378  * duplicate that node and what's below; ignore siblings of root node.
 379  */
 380 PCCTS_AST *PCCTS_AST::
 381 deepCopy()
 382 {
 383         PCCTS_AST *u = this->shallowCopy();
 384         if ( down()!=NULL ) u->setDown(down()->deepCopy());
 385         return u;
 386 }
 387
 388 /* Copy all nodes including siblings of root. */
 389 PCCTS_AST *PCCTS_AST::
 390 deepCopyBushy()
 391 {
 392         PCCTS_AST *u = this->shallowCopy();
 393         /* copy the rest of the tree */
 394         if ( down()!=NULL ) u->setDown(down()->deepCopy());
 395         if ( right()!=NULL ) u->setRight(right()->deepCopy());
 396         return u;
 397 }
 398
 399 void PCCTS_AST::
 400 scanast_free(ScanAST *t)
 401 {
 402     if ( t == NULL ) return;
 403     scanast_free( t->down() );
 404     scanast_free( t->right() );
 405     free( t );
 406 }
 407
 408 /*
 409  * scan
 410  *
 411  * This function is like scanf(): it attempts to match a template
 412  * against an input tree.  A variable number of tree pointers
 413  * may be set according to the '%i' labels in the template string.
 414  * For example:
 415  *
 416  *   t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
 417  *            &w, &x, &y, &z);
 418  *
 419  * Naturally, you'd want this converted from
 420  *
 421  *       t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
 422  *                        &w, &x, &y, &z);
 423  *
 424  * by SORCERER.
 425  *
 426  * This function call must be done withing a SORCERER file because SORCERER
 427  * must convert the token references to the associated token number.
 428  *
 429  * This functions parses the template and creates trees which are then
 430  * matched against the input tree.  The labels are set as they are
 431  * encountered; hence, partial matches may leave some pointers set
 432  * and some NULL.  This routines initializes all argument pointers to NULL
 433  * at the beginning.
 434  *
 435  * This function returns the number of labels matched.
 436  */
 437 int PCCTS_AST::
 438 ast_scan(char *templ, ...)
 439 {
 440         va_list ap;
 441         ScanAST *tmpl;
 442         int n, i, found=0;
 443         PCCTS_AST ***label_ptrs=NULL;
 444
 445         va_start(ap, templ);
 446
 447         /* make a ScanAST tree out of the template */
 448         tmpl = stringparser_parse_scanast(templ, &n);
 449
 450         /* make an array out of the labels */
 451         if ( n>0 )
 452         {
 453                 label_ptrs = (PCCTS_AST ***) calloc(n, sizeof(PCCTS_AST **));
 454                 require(label_ptrs!=NULL, "scan: out of memory");
 455                 for (i=1; i<=n; i++)
 456                 {
 457                         label_ptrs[i-1] = va_arg(ap, PCCTS_AST **);
 458                         *(label_ptrs[i-1]) = NULL;
 459                 }
 460         }
 461
 462         /* match the input tree against the template */
 463         scanmatch(tmpl, label_ptrs, &found);
 464
 465         scanast_free(tmpl);
 466         free(label_ptrs);
 467
 468         return found;
 469 }
 470
 471 ScanAST *PCCTS_AST::
 472 new_scanast(int tok)
 473 {
 474     ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST));
 475     if ( p == NULL ) {fprintf(stderr, "out of mem\n"); exit(EXIT_FAILURE);}
 476         p->_token = tok;
 477         return p;
 478 }
 479
 480 ScanAST *PCCTS_AST::
 481 stringparser_parse_scanast(char *templ, int *num_labels)
 482 {
 483         StringLexer lex;
 484         StringParser parser;
 485         ScanAST *t;
 486
 487         stringlexer_init(&lex, templ);
 488         stringparser_init(&parser, &lex);
 489         t = stringparser_parse_tree(&parser);
 490         *num_labels = parser.num_labels;
 491         return t;
 492 }
 493
 494 void PCCTS_AST::
 495 stringparser_match(StringParser *parser, int token)
 496 {
 497         if ( parser->token != token ) panic("bad tree in scan()");
 498 }
 499
 500 /*
 501  * Match a tree of the form:
 502  *              (root child1 child2 ... childn)
 503  * or,
 504  *              node
 505  *
 506  * where the elements are integers or labeled integers.
 507  */
 508 ScanAST *PCCTS_AST::
 509 stringparser_parse_tree(StringParser *parser)
 510 {
 511         ScanAST *t=NULL, *root, *child, *last;
 512
 513         if ( parser->token != __POUND )
 514         {
 515                 return stringparser_parse_element(parser);
 516         }
 517         stringparser_match(parser,__POUND);
 518         parser->token = stringscan_gettok(parser->lexer);
 519         stringparser_match(parser,__LPAREN);
 520         parser->token = stringscan_gettok(parser->lexer);
 521         root = stringparser_parse_element(parser);
 522         while ( parser->token != __RPAREN )
 523         {
 524                 child = stringparser_parse_element(parser);
 525                 if ( t==NULL ) { t = child; last = t; }
 526                 else { last->_right = child; last = child; }
 527         }
 528         stringparser_match(parser,__RPAREN);
 529         parser->token = stringscan_gettok(parser->lexer);
 530         root->_down = t;
 531         return root;
 532 }
 533
 534 ScanAST *PCCTS_AST::
 535 stringparser_parse_element(StringParser *parser)
 536 {
 537         static char ebuf[100];
 538         int label = 0;
 539
 540         if ( parser->token == __POUND )
 541         {
 542                 return stringparser_parse_tree(parser);
 543         }
 544         if ( parser->token == __PERCENT )
 545         {
 546                 parser->token = stringscan_gettok(parser->lexer);
 547                 stringparser_match(parser,__INT);
 548                 label = atoi(parser->lexer->text);
 549                 parser->num_labels++;
 550                 if ( label==0 ) panic("%%0 is an invalid label");
 551                 parser->token = stringscan_gettok(parser->lexer);
 552                 stringparser_match(parser,__COLON);
 553                 parser->token = stringscan_gettok(parser->lexer);
 554                 /* can label tokens and wildcards */
 555                 if ( parser->token != __INT && parser->token != __PERIOD )
 556                         panic("can only label tokens");
 557         }
 558         if ( parser->token == __INT )
 559         {
 560                 ScanAST *p = new_scanast(atoi(parser->lexer->text));
 561                 parser->token = stringscan_gettok(parser->lexer);
 562                 p->label_num = label;
 563                 return p;
 564         }
 565         if ( parser->token == __PERIOD )
 566         {
 567                 ScanAST *p = new_scanast(0);    /* token of 0 is wildcard */
 568                 parser->token = stringscan_gettok(parser->lexer);
 569                 p->label_num = label;
 570                 return p;
 571         }
 572         sprintf(ebuf, "mismatch token in scan(): %s", scan_token_str(parser->token));
 573         panic(ebuf);
 574         return NULL;
 575 }
 576
 577 void PCCTS_AST::
 578 stringparser_init(StringParser *parser, StringLexer *input)
 579 {
 580         parser->lexer = input;
 581         parser->token = stringscan_gettok(parser->lexer);
 582         parser->num_labels = 0;
 583 }
 584
 585 void PCCTS_AST::
 586 stringlexer_init(StringLexer *scanner, char *input)
 587 {
 588         scanner->text[0]='\0';
 589         scanner->input = input;
 590         scanner->p = input;
 591         stringscan_advance(scanner);
 592 }
 593
 594 void PCCTS_AST::
 595 stringscan_advance(StringLexer *scanner)
 596 {
 597         if ( *(scanner->p) == '\0' ) scanner->c = __StringScanEOF;
 598         scanner->c = *(scanner->p)++;
 599 }
 600
 601 int PCCTS_AST::
 602 stringscan_gettok(StringLexer *scanner)
 603 {
 604         char *index = &scanner->text[0];
 605         static char ebuf[100];
 606
 607         while ( isspace(scanner->c) ) { stringscan_advance(scanner); }
 608         if ( isdigit(scanner->c) )
 609         {
 610                 int tok = __INT;
 611                 while ( isdigit(scanner->c) ) {
 612                         *index++ = scanner->c;
 613                         stringscan_advance(scanner);
 614                 }
 615                 *index = '\0';
 616                 return tok;
 617         }
 618         switch ( scanner->c )
 619         {
 620                 case '#' : stringscan_advance(scanner); return __POUND;
 621                 case '(' : stringscan_advance(scanner); return __LPAREN;
 622                 case ')' : stringscan_advance(scanner); return __RPAREN;
 623                 case '%' : stringscan_advance(scanner); return __PERCENT;
 624                 case ':' : stringscan_advance(scanner); return __COLON;
 625                 case '.' : stringscan_advance(scanner); return __PERIOD;
 626                 case '\0' : return __StringScanEOF;
 627                 case __StringScanEOF : return __StringScanEOF;
 628                 default  :
 629                         sprintf(ebuf, "invalid char in scan: '%c'", scanner->c);
 630                         panic(ebuf);
 631         }
 632         return __StringScanEOF; // never reached
 633 }
 634
 635 char *PCCTS_AST::
 636 scan_token_str(int t)
 637 {
 638         if ( VALID_SCAN_TOKEN(t) ) return scan_token_tbl[t];
 639         else if ( t==__StringScanEOF ) return "<end-of-string>";
 640         else return "<invalid-token>";
 641 }