pd.if.org Git - pccts/blob - antlr/pred.c

   1 /*
   2  * pred.c -- source for predicate detection, manipulation
   3  *
   4  * $Id: pred.c,v 1.6 95/09/26 12:58:44 parrt Exp $
   5  * $Revision: 1.6 $
   6  *
   7  * SOFTWARE RIGHTS
   8  *
   9  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  10  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  11  * company may do whatever they wish with source code distributed with
  12  * PCCTS or the code generated by PCCTS, including the incorporation of
  13  * PCCTS, or its output, into commerical software.
  14  *
  15  * We encourage users to develop software with PCCTS.  However, we do ask
  16  * that credit is given to us for developing PCCTS.  By "credit",
  17  * we mean that if you incorporate our source code into one of your
  18  * programs (commercial product, research project, or otherwise) that you
  19  * acknowledge this fact somewhere in the documentation, research report,
  20  * etc...  If you like PCCTS and have developed a nice tool with the
  21  * output, please mention that you developed it using PCCTS.  In
  22  * addition, we ask that this header remain intact in our source code.
  23  * As long as these guidelines are kept, we expect to continue enhancing
  24  * this system and expect to make other tools available as they are
  25  * completed.
  26  *
  27  * ANTLR 1.33
  28  * Terence Parr
  29  * Parr Research Corporation
  30  * with Purdue University and AHPCRC, University of Minnesota
  31  * 1989-1995
  32  */
  33 #include <stdio.h>
  34 #ifdef __cplusplus
  35 #ifndef __STDC__
  36 #define __STDC__
  37 #endif
  38 #endif
  39 #include "set.h"
  40 #include "syn.h"
  41 #include "hash.h"
  42 #include "generic.h"
  43 #include "dlgdef.h"
  44 #include <ctype.h>
  45
  46 #ifdef __STDC__
  47 static void complete_context_sets(RuleRefNode *, Predicate *);
  48 static void complete_context_trees(RuleRefNode *, Predicate *);
  49 #else
  50 static void complete_context_sets();
  51 static void complete_context_trees();
  52 #endif
  53
  54 static Predicate pred_empty = {
  55         NULL,NULL,NULL,NULL,NULL,NULL,0,
  56         {set_init,set_init},set_init
  57 };
  58
  59 char *PRED_AND_LIST = "AND";
  60 char *PRED_OR_LIST = "OR";
  61
  62 /*
  63  * In C mode, return the largest constant integer found as the
  64  * sole argument to LATEXT(i).
  65  *
  66  * In C++ mode, return the largest constant integer found as the
  67  * sole argument to LT(i) given that the char before is nonalpha.
  68  */
  69 static int
  70 #ifdef __STDC__
  71 predicateLookaheadDepth(ActionNode *a)
  72 #else
  73 predicateLookaheadDepth(a)
  74 ActionNode *a;
  75 #endif
  76 {
  77         int max_k=0;
  78
  79         if ( GenCC )
  80         {
  81                 /* scan for LT(i) */
  82                 int k = 0;
  83                 char *p = a->action;
  84                 while ( p!=NULL )
  85                 {
  86                         p = strstr(p, "LT(");
  87                         if ( p!=NULL )
  88                         {
  89                                 if ( p>=a->action && !isalpha(*(p-1)) )
  90                                 {
  91                                         k = atoi(p+strlen("LT("));
  92                                         if ( k>max_k ) max_k=k;
  93                                 }
  94                                 p += strlen("LT(");
  95                         }
  96                 }
  97         }
  98         else {
  99                 /* scan for LATEXT(i) */
 100                 int k = 0;
 101                 char *p = a->action;
 102                 while ( p!=NULL )
 103                 {
 104                         p = strstr(p, "LATEXT(");
 105                         if ( p!=NULL )
 106                         {
 107                                 p += strlen("LATEXT(");
 108                                 k = atoi(p);
 109                                 if ( k>max_k ) max_k=k;
 110                         }
 111                 }
 112         }
 113
 114         if ( max_k==0 )
 115         {
 116                 if ( !a->frmwarned )
 117                 {
 118                         a->frmwarned = 1;
 119                         warnFL(eMsg1("predicate: %s missing, bad, or with i=0; assuming i=1",
 120                                                  GenCC?"LT(i)":"LATEXT(i)"),
 121                                    FileStr[a->file], a->line);
 122                 }
 123                 max_k = 1;
 124         }
 125
 126         return max_k;
 127 }
 128
 129 /* Find all predicates in a block of alternatives.  DO NOT find predicates
 130  * behind the block because that predicate could depend on things set in
 131  * one of the nonoptional blocks
 132  */
 133 Predicate *
 134 #ifdef __STDC__
 135 find_in_aSubBlk( Junction *alt )
 136 #else
 137 find_in_aSubBlk( alt )
 138 Junction *alt;
 139 #endif
 140 {
 141         Predicate *a, *head=NULL, *tail, *root=NULL;
 142         Junction *p = alt;
 143
 144         for (; p!=NULL; p=(Junction *)p->p2)
 145         {
 146                 /* ignore empty alts */
 147                 if ( p->p1->ntype != nJunction ||
 148                          ((Junction *)p->p1)->jtype != EndBlk )
 149                 {
 150                         a = find_predicates(p->p1);     /* get preds for this alt */
 151                         if ( a==NULL ) continue;
 152
 153                         /* make an OR list of predicates */
 154                         if ( head==NULL )
 155                         {
 156                                 root = new_pred();
 157                                 root->expr = PRED_OR_LIST;
 158                                 head = tail = a;
 159                                 root->down = head;
 160                         }
 161                         else {
 162                                 tail->right = a;
 163                                 a->left = tail;
 164                                 a->up = tail->up;
 165                                 tail = a;
 166                         }
 167                 }
 168         }
 169
 170         /* if just one pred, remove OR root */
 171         if ( root!=NULL && root->down->right == NULL )
 172         {
 173                 Predicate *d = root->down;
 174                 free(root);
 175                 return d;
 176         }
 177
 178         return root;
 179 }
 180
 181 Predicate *
 182 #ifdef __STDC__
 183 find_in_aOptBlk( Junction *alt )
 184 #else
 185 find_in_aOptBlk( alt )
 186 Junction *alt;
 187 #endif
 188 {
 189         return find_in_aSubBlk( alt );
 190 }
 191
 192 Predicate *
 193 #ifdef __STDC__
 194 find_in_aLoopBegin( Junction *alt )
 195 #else
 196 find_in_aLoopBegin( alt )
 197 Junction *alt;
 198 #endif
 199 {
 200         return find_in_aSubBlk( (Junction *) alt->p1 ); /* get preds in alts */
 201 }
 202
 203 Predicate *
 204 #ifdef __STDC__
 205 find_in_aPlusBlk( Junction *alt )
 206 #else
 207 find_in_aPlusBlk( alt )
 208 Junction *alt;
 209 #endif
 210 {
 211         require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");
 212         return find_in_aSubBlk( alt );
 213 }
 214
 215 /* Look for a predicate;
 216  *
 217  * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.
 218  * This means that a "hoisting distance" of zero is the only distance
 219  * allowable.  Init actions are ignored.
 220  *
 221  * WARNING:
 222  *              Assumes no (..)? block after predicate for the moment.
 223  *              Does not check to see if pred is in production that can generate
 224  *                      a sequence contained in the set of ambiguous tuples.
 225  *
 226  * Return the predicate found if any.
 227  */
 228 Predicate *
 229 #ifdef __STDC__
 230 find_predicates( Node *alt )
 231 #else
 232 find_predicates( alt )
 233 Node *alt;
 234 #endif
 235 {
 236 #ifdef DBG_PRED
 237         Junction *j;
 238         RuleRefNode *r;
 239         TokNode *t;
 240 #endif
 241         Predicate *pred;
 242
 243         if ( alt==NULL ) return NULL;
 244
 245 #ifdef DBG_PRED
 246         switch ( alt->ntype )
 247         {
 248                 case nJunction :
 249                         j = (Junction *) alt;
 250                         fprintf(stderr, "Junction(in %s)", j->rname);
 251                         switch ( j->jtype )
 252                         {
 253                                 case aSubBlk :
 254                                         fprintf(stderr,"aSubBlk\n");
 255                                         break;
 256                                 case aOptBlk :
 257                                         fprintf(stderr,"aOptBlk\n");
 258                                         break;
 259                                 case aLoopBegin :
 260                                         fprintf(stderr,"aLoopBeginBlk\n");
 261                                         break;
 262                                 case aLoopBlk :
 263                                         fprintf(stderr,"aLoopBlk\n");
 264                                         break;
 265                                 case aPlusBlk :
 266                                         fprintf(stderr,"aPlusBlk\n");
 267                                         break;
 268                                 case EndBlk :
 269                                         fprintf(stderr,"EndBlk\n");
 270                                         break;
 271                                 case RuleBlk :
 272                                         fprintf(stderr,"RuleBlk\n");
 273                                         break;
 274                                 case Generic :
 275                                         fprintf(stderr,"Generic\n");
 276                                         break;
 277                                 case EndRule :
 278                                         fprintf(stderr,"EndRule\n");
 279                                         break;
 280                         }
 281                         break;
 282                 case nRuleRef :
 283                         r = (RuleRefNode *) alt;
 284                         fprintf(stderr, "RuleRef(in %s)\n", r->rname);
 285                         break;
 286                 case nToken :
 287                         t = (TokNode *) alt;
 288                         fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));
 289                         break;
 290                 case nAction :
 291                         fprintf(stderr, "Action\n");
 292                         break;
 293         }
 294 #endif
 295
 296         switch ( alt->ntype )
 297         {
 298                 case nJunction :
 299                 {
 300                         Predicate *a, *b;
 301                         Junction *p = (Junction *) alt;
 302
 303                         /* lock nodes */
 304                         if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
 305                                  p->jtype==aPlusBlk || p->jtype==EndRule )
 306                         {
 307                                 require(p->pred_lock!=NULL, "rJunc: lock array is NULL");
 308                                 if ( p->pred_lock[1] )
 309                                 {
 310                                         return NULL;
 311                                 }
 312                                 p->pred_lock[1] = TRUE;
 313                         }
 314
 315                         switch ( p->jtype )
 316                         {
 317                                 case aSubBlk :
 318                                         a = find_in_aSubBlk(p);
 319                                         return a;       /* nothing is visible past this guy */
 320                                 case aOptBlk :
 321                                         a = find_in_aOptBlk(p);
 322                                         return a;
 323                                 case aLoopBegin :
 324                                         a = find_in_aLoopBegin(p);
 325                                         return a;
 326                                 case aLoopBlk :
 327                                         a = find_in_aSubBlk(p);
 328                                         p->pred_lock[1] = FALSE;
 329                                         return a;
 330                                 case aPlusBlk :
 331                                         a = find_in_aPlusBlk(p);
 332                                         p->pred_lock[1] = FALSE;
 333                                         return a;       /* nothing is visible past this guy */
 334                                 case RuleBlk :
 335                                         a = find_predicates(p->p1);
 336                                         p->pred_lock[1] = FALSE;
 337                                         return a;
 338                                 case Generic :
 339                                         a = find_predicates(p->p1);
 340                                         b = find_predicates(p->p2);
 341                                         if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;
 342                                         if ( a==NULL ) return b;
 343                                         if ( b==NULL ) return a;
 344                                         /* otherwise OR the two preds together */
 345                                         {
 346                                         fatal_internal("hit unknown situation during predicate hoisting");
 347                                         }
 348                                 case EndBlk :
 349                                 case EndRule :  /* Find no predicates after a rule ref */
 350                                         return NULL;
 351                                 default:
 352                                         fatal_internal("this cannot be printed\n");
 353                                         break;
 354                         }
 355                 }
 356                 case nAction :
 357                 {
 358                         ActionNode *p = (ActionNode *) alt;
 359                         if ( p->init_action ) return find_predicates(p->next);
 360                         if ( p->is_predicate )
 361                         {
 362                                 Tree *t;
 363 #ifdef DBG_PRED
 364                                 fprintf(stderr, "predicate: <<%s>>?\n", p->action);
 365 #endif
 366                                 if ( p->guardpred!=NULL )
 367                                 {
 368                                         pred = p->guardpred;
 369                                 }
 370                                 else
 371                                 {
 372                                         pred = new_pred();
 373                                         pred->k = predicateLookaheadDepth(p);
 374                                         pred->source = p;
 375                                         pred->expr = p->action;
 376                                         if ( HoistPredicateContext && pred->k > 1 )
 377                                         {
 378                                                 if ( first_item_is_guess_block((Junction *)p->next) )
 379                                                 {
 380                                                         warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
 381                                                 }
 382                                                 else
 383                                                 {
 384                                                         ConstrainSearch = 0;
 385                                                         TRAV(p->next,
 386                                                                  pred->k,
 387                                                                  &(pred->completion), t);
 388                                                         pred->tcontext = t;
 389 #ifdef DBG_PRED
 390                                                         fprintf(stderr, "LL(%d) context:", pred->k);
 391                                                         preorder(t);
 392                                                         fprintf(stderr, "\n");
 393 #endif
 394                                                 }
 395                                         }
 396                                         else if ( HoistPredicateContext && pred->k == 1 )
 397                                         {
 398                                                 pred->scontext[1] = empty;
 399                                                 if ( first_item_is_guess_block((Junction *)p->next) )
 400                                                 {
 401                                                         warnFL("cannot compute context of predicate in front of (..)? block", FileStr[p->file], p->line);
 402                                                 }
 403                                                 else
 404                                                 {
 405                                                         REACH((Junction *)p->next,
 406                                                                   1,
 407                                                                   &(pred->completion),
 408                                                                   pred->scontext[1]);
 409 #ifdef DBG_PRED
 410                                                         fprintf(stderr, "LL(1) context:");
 411                                                         s_fprT(stderr, pred->scontext[1]);
 412                                                         fprintf(stderr, "\n");
 413 #endif
 414                                                 }
 415                                         }
 416                                 }
 417                                 {
 418                                         Predicate *d = find_predicates(p->next), *root;
 419 /* Warning: Doesn't seem like the up pointers will all be set correctly;
 420  * TJP: that's ok, we're not using them now.
 421  */
 422                                         if ( d!=NULL )
 423                                         {
 424                                                 root = new_pred();
 425                                                 root->expr = PRED_AND_LIST;
 426                                                 root->down = pred;
 427                                                 pred->right = d;
 428                                                 pred->up = root;
 429                                                 d->left = pred;
 430                                                 d->up = pred->up;
 431                                                 return root;
 432                                         }
 433                                 }
 434                                 return pred;
 435                         }
 436                         return NULL;
 437                 }
 438                 case nRuleRef :
 439                 {
 440                         Predicate *a;
 441                         RuleRefNode *p = (RuleRefNode *) alt;
 442                         Junction *r;
 443                         int save_halt;
 444                         RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
 445                         if ( q == NULL )
 446                         {
 447                                 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
 448                                 return NULL;
 449                         }
 450                         r = RulePtr[q->rulenum];
 451                         if ( r->pred_lock[1] )
 452                         {
 453                                 /* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis
 454                                  * must have seen it earlier.
 455                                  */
 456                                 return NULL;
 457                         }
 458                         save_halt = r->end->halt;
 459                         r->end->halt = TRUE;
 460 /*                      a = find_predicates((Node *)r->p1);*/
 461                         a = find_predicates((Node *)r);
 462                         r->end->halt = save_halt;
 463                         if ( a==NULL ) return NULL;
 464                         /* attempt to compute the "local" FOLLOW just like in normal lookahead
 465                          * computation if needed
 466                          */
 467                         complete_context_sets(p,a);
 468                         complete_context_trees(p,a);
 469                         return a;
 470                 }
 471                 case nToken :
 472                         break;
 473         }
 474
 475         return NULL;
 476 }
 477
 478 Predicate *
 479 #ifdef __STDC__
 480 new_pred( void )
 481 #else
 482 new_pred( )
 483 #endif
 484 {
 485         Predicate *p = (Predicate *) malloc(sizeof(Predicate));
 486         require(p!=NULL, "new_pred: cannot alloc predicate");
 487         *p = pred_empty;
 488         return p;
 489 }
 490
 491 static void
 492 #ifdef __STDC__
 493 complete_context_sets( RuleRefNode *p, Predicate *a )
 494 #else
 495 complete_context_sets( p, a )
 496 RuleRefNode *p;
 497 Predicate *a;
 498 #endif
 499 {
 500         set rk2, b;
 501         int k2;
 502
 503 #ifdef DBG_PRED
 504         fprintf(stderr, "enter complete_context_sets\n");
 505 #endif
 506         for (; a!=NULL; a=a->right)
 507         {
 508                 if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
 509                 {
 510                         complete_context_sets(p, a->down);
 511                         continue;
 512                 }
 513                 rk2 = b = empty;
 514                 while ( !set_nil(a->completion) )
 515                 {
 516                         k2 = set_int(a->completion);
 517                         set_rm(k2, a->completion);
 518                         REACH(p->next, k2, &rk2, b);
 519                         set_orin(&(a->scontext[1]), b);
 520                         set_free(b);
 521                 }
 522                 set_orin(&(a->completion), rk2);/* remember what we couldn't do */
 523                 set_free(rk2);
 524 #ifdef DBG_PRED
 525                 fprintf(stderr, "LL(1) context for %s(addr 0x%x) after ruleref:", a->expr, a);
 526                 s_fprT(stderr, a->scontext[1]);
 527                 fprintf(stderr, "\n");
 528 #endif
 529 /*              complete_context_sets(p, a->down);*/
 530         }
 531 #ifdef DBG_PRED
 532         fprintf(stderr, "exit complete_context_sets\n");
 533 #endif
 534 }
 535
 536 static void
 537 #ifdef __STDC__
 538 complete_context_trees( RuleRefNode *p, Predicate *a )
 539 #else
 540 complete_context_trees( p, a )
 541 RuleRefNode *p;
 542 Predicate *a;
 543 #endif
 544 {
 545         set rk2;
 546         int k2;
 547         Tree *u;
 548
 549 #ifdef DBG_PRED
 550         fprintf(stderr, "enter complete_context_trees\n");
 551 #endif
 552         for (; a!=NULL; a=a->right)
 553         {
 554                 if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
 555                 {
 556                         complete_context_trees(p, a->down);
 557                         continue;
 558                 }
 559                 rk2 = empty;
 560                 /* any k left to do? if so, link onto tree */
 561                 while ( !set_nil(a->completion) )
 562                 {
 563                         k2 = set_int(a->completion);
 564                         set_rm(k2, a->completion);
 565                         u = NULL;
 566                         TRAV(p->next, k2, &rk2, u);
 567                         /* any subtrees missing k2 tokens, add u onto end */
 568                         a->tcontext = tlink(a->tcontext, u, k2);
 569                 }
 570                 set_orin(&(a->completion), rk2);/* remember what we couldn't do */
 571                 set_free(rk2);
 572 #ifdef DBG_PRED
 573                 fprintf(stderr, "LL(i<%d) context after ruleref:", LL_k);
 574                 preorder(a->tcontext);
 575                 fprintf(stderr, "\n");
 576 #endif
 577 /*              complete_context_trees(p, a->down);*/
 578         }
 579 #ifdef DBG_PRED
 580         fprintf(stderr, "exit complete_context_trees\n");
 581 #endif
 582 }
 583
 584 /* Walk a list of predicates and return the set of all tokens in scontext[1]'s */
 585 set
 586 #ifdef __STDC__
 587 covered_set( Predicate *p )
 588 #else
 589 covered_set( p )
 590 Predicate *p;
 591 #endif
 592 {
 593         set a;
 594
 595         a = empty;
 596         for (; p!=NULL; p=p->right)
 597         {
 598                 if ( p->expr == PRED_AND_LIST || p->expr == PRED_OR_LIST )
 599                 {
 600                         set_orin(&a, covered_set(p->down));
 601                         continue;
 602                 }
 603                 set_orin(&a, p->scontext[1]);
 604                 set_orin(&a, covered_set(p->down));
 605         }
 606         return a;
 607 }