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

   1 /*
   2  * fset2.c
   3  *
   4  * $Id: fset2.c,v 1.7 95/10/05 11:57:01 parrt Exp $
   5  * $Revision: 1.7 $
   6  *
   7  * Compute FIRST sets for full LL(k)
   8  *
   9  * SOFTWARE RIGHTS
  10  *
  11  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  12  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  13  * company may do whatever they wish with source code distributed with
  14  * PCCTS or the code generated by PCCTS, including the incorporation of
  15  * PCCTS, or its output, into commerical software.
  16  *
  17  * We encourage users to develop software with PCCTS.  However, we do ask
  18  * that credit is given to us for developing PCCTS.  By "credit",
  19  * we mean that if you incorporate our source code into one of your
  20  * programs (commercial product, research project, or otherwise) that you
  21  * acknowledge this fact somewhere in the documentation, research report,
  22  * etc...  If you like PCCTS and have developed a nice tool with the
  23  * output, please mention that you developed it using PCCTS.  In
  24  * addition, we ask that this header remain intact in our source code.
  25  * As long as these guidelines are kept, we expect to continue enhancing
  26  * this system and expect to make other tools available as they are
  27  * completed.
  28  *
  29  * ANTLR 1.33
  30  * Terence Parr
  31  * Parr Research Corporation
  32  * with Purdue University and AHPCRC, University of Minnesota
  33  * 1989-1995
  34  */
  35 #include <stdio.h>
  36 #ifdef __cplusplus
  37 #ifndef __STDC__
  38 #define __STDC__
  39 #endif
  40 #endif
  41 #ifdef __STDC__
  42 #include <stdarg.h>
  43 #else
  44 #include <varargs.h>
  45 #endif
  46 #include "set.h"
  47 #include "syn.h"
  48 #include "hash.h"
  49 #include "generic.h"
  50 #include "dlgdef.h"
  51
  52 extern char tokens[];
  53
  54 extern char *PRED_AND_LIST;
  55 extern char *PRED_OR_LIST;
  56
  57 /* ick! globals.  Used by permute() to track which elements of a set have been used */
  58 static int *findex;
  59 static set *fset;
  60 static unsigned **ftbl;
  61 static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
  62 int ConstrainSearch;
  63 static int maxk; /* set to initial k upon tree construction request */
  64 static Tree *FreeList = NULL;
  65
  66 #ifdef __STDC__
  67 static int tmember_of_context(Tree *, Predicate *);
  68 #else
  69 static int tmember_of_context();
  70 #endif
  71
  72 /* Do root
  73  * Then each sibling
  74  */
  75 void
  76 #ifdef __STDC__
  77 preorder( Tree *tree )
  78 #else
  79 preorder( tree )
  80 Tree *tree;
  81 #endif
  82 {
  83         if ( tree == NULL ) return;
  84         if ( tree->down != NULL ) fprintf(stderr, " (");
  85         if ( tree->token == ALT ) fprintf(stderr, " J");
  86         else fprintf(stderr, " %s", TerminalString(tree->token));
  87         if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
  88         preorder(tree->down);
  89         if ( tree->down != NULL ) fprintf(stderr, " )");
  90         preorder(tree->right);
  91 }
  92
  93 /* check the depth of each primary sibling to see that it is exactly
  94  * k deep. e.g.;
  95  *
  96  *      ALT
  97  *   |
  98  *   A ------- B
  99  *   |         |
 100  *   C -- D    E
 101  *
 102  * Remove all branches <= k deep.
 103  *
 104  * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.
 105  */
 106 Tree *
 107 #ifdef __STDC__
 108 prune( Tree *t, int k )
 109 #else
 110 prune( t, k )
 111 Tree *t;
 112 int k;
 113 #endif
 114 {
 115     if ( t == NULL ) return NULL;
 116     if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree");
 117     if ( t->right!=NULL ) t->right = prune(t->right, k);
 118     if ( k>1 )
 119         {
 120                 if ( t->down!=NULL ) t->down = prune(t->down, k-1);
 121                 if ( t->down == NULL )
 122                 {
 123                         Tree *r = t->right;
 124                         t->right = NULL;
 125                         Tfree(t);
 126                         return r;
 127                 }
 128         }
 129     return t;
 130 }
 131
 132 /* build a tree (root child1 child2 ... NULL) */
 133 #ifdef __STDC__
 134 Tree *tmake(Tree *root, ...)
 135 #else
 136 Tree *tmake(va_alist)
 137 va_dcl
 138 #endif
 139 {
 140         Tree *w;
 141         va_list ap;
 142         Tree *child, *sibling=NULL, *tail;
 143 #ifndef __STDC__
 144         Tree *root;
 145 #endif
 146
 147 #ifdef __STDC__
 148         va_start(ap, root);
 149 #else
 150         va_start(ap);
 151         root = va_arg(ap, Tree *);
 152 #endif
 153         child = va_arg(ap, Tree *);
 154         while ( child != NULL )
 155         {
 156 #ifdef DUM
 157                 /* added "find end of child" thing TJP March 1994 */
 158                 for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
 159 #else
 160                 w = child;
 161 #endif
 162
 163                 if ( sibling == NULL ) {sibling = child; tail = w;}
 164                 else {tail->right = child; tail = w;}
 165                 child = va_arg(ap, Tree *);
 166         }
 167
 168         /* was "root->down = sibling;" */
 169         if ( root==NULL ) root = sibling;
 170         else root->down = sibling;
 171
 172         va_end(ap);
 173         return root;
 174 }
 175
 176 Tree *
 177 #ifdef __STDC__
 178 tnode( int tok )
 179 #else
 180 tnode( tok )
 181 int tok;
 182 #endif
 183 {
 184         Tree *p, *newblk;
 185         static int n=0;
 186
 187         if ( FreeList == NULL )
 188         {
 189                 /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
 190                 if ( TreeResourceLimit > 0 )
 191                 {
 192                         if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
 193                         {
 194                                 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
 195                                 fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",
 196                                                                 CurAmbigAlt1,
 197                                                                 CurAmbigAlt2,
 198                                                                 CurAmbigbtype);
 199                                 exit(PCCTS_EXIT_FAILURE);
 200                         }
 201                 }
 202                 newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
 203                 if ( newblk == NULL )
 204                 {
 205                         fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
 206                         fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",
 207                                                         CurAmbigAlt1,
 208                                                         CurAmbigAlt2,
 209                                                         CurAmbigbtype);
 210                         exit(PCCTS_EXIT_FAILURE);
 211                 }
 212                 n += TreeBlockAllocSize;
 213                 for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
 214                 {
 215                         p->right = FreeList;    /* add all new Tree nodes to Free List */
 216                         FreeList = p;
 217                 }
 218         }
 219         p = FreeList;
 220         FreeList = FreeList->right;             /* remove a tree node */
 221         p->right = NULL;                                /* zero out ptrs */
 222         p->down = NULL;
 223         p->token = tok;
 224 #ifdef TREE_DEBUG
 225         require(!p->in_use, "tnode: node in use!");
 226         p->in_use = 1;
 227 #endif
 228         return p;
 229 }
 230
 231 static Tree *
 232 #ifdef __STDC__
 233 eofnode( int k )
 234 #else
 235 eofnode( k )
 236 int k;
 237 #endif
 238 {
 239         Tree *t=NULL;
 240         int i;
 241
 242         for (i=1; i<=k; i++)
 243         {
 244                 t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL);
 245         }
 246         return t;
 247 }
 248
 249
 250
 251 void
 252 #ifdef __STDC__
 253 _Tfree( Tree *t )
 254 #else
 255 _Tfree( t )
 256 Tree *t;
 257 #endif
 258 {
 259         if ( t!=NULL )
 260         {
 261 #ifdef TREE_DEBUG
 262                 require(t->in_use, "_Tfree: node not in use!");
 263                 t->in_use = 0;
 264 #endif
 265                 t->right = FreeList;
 266                 FreeList = t;
 267         }
 268 }
 269
 270 /* tree duplicate */
 271 Tree *
 272 #ifdef __STDC__
 273 tdup( Tree *t )
 274 #else
 275 tdup( t )
 276 Tree *t;
 277 #endif
 278 {
 279         Tree *u;
 280
 281         if ( t == NULL ) return NULL;
 282         u = tnode(t->token);
 283         u->v.rk = t->v.rk;
 284         u->right = tdup(t->right);
 285         u->down = tdup(t->down);
 286         return u;
 287 }
 288
 289 /* tree duplicate (assume tree is a chain downwards) */
 290 Tree *
 291 #ifdef __STDC__
 292 tdup_chain( Tree *t )
 293 #else
 294 tdup_chain( t )
 295 Tree *t;
 296 #endif
 297 {
 298         Tree *u;
 299
 300         if ( t == NULL ) return NULL;
 301         u = tnode(t->token);
 302         u->v.rk = t->v.rk;
 303         u->down = tdup(t->down);
 304         return u;
 305 }
 306
 307 Tree *
 308 #ifdef __STDC__
 309 tappend( Tree *t, Tree *u )
 310 #else
 311 tappend( t, u )
 312 Tree *t;
 313 Tree *u;
 314 #endif
 315 {
 316         Tree *w;
 317
 318         /*fprintf(stderr, "tappend(");
 319         preorder(t); fprintf(stderr, ",");
 320         preorder(u); fprintf(stderr, " )\n");*/
 321         if ( t == NULL ) return u;
 322         if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
 323         for (w=t; w->right!=NULL; w=w->right) {;}
 324         w->right = u;
 325         return t;
 326 }
 327
 328 /* dealloc all nodes in a tree */
 329 void
 330 #ifdef __STDC__
 331 Tfree( Tree *t )
 332 #else
 333 Tfree( t )
 334 Tree *t;
 335 #endif
 336 {
 337         if ( t == NULL ) return;
 338         Tfree( t->down );
 339         Tfree( t->right );
 340         _Tfree( t );
 341 }
 342
 343 /* find all children (alts) of t that require remaining_k nodes to be LL_k
 344  * tokens long.
 345  *
 346  * t-->o
 347  *     |
 348  *     a1--a2--...--an          <-- LL(1) tokens
 349  *     |   |        |
 350  *     b1  b2  ...  bn          <-- LL(2) tokens
 351  *     |   |        |
 352  *     .   .        .
 353  *     .   .        .
 354  *     z1  z2  ...  zn          <-- LL(LL_k) tokens
 355  *
 356  * We look for all [Ep] needing remaining_k nodes and replace with u.
 357  * u is not destroyed or actually used by the tree (a copy is made).
 358  */
 359 Tree *
 360 #ifdef __STDC__
 361 tlink( Tree *t, Tree *u, int remaining_k )
 362 #else
 363 tlink( t, u, remaining_k )
 364 Tree *t;
 365 Tree *u;
 366 int remaining_k;
 367 #endif
 368 {
 369         Tree *p;
 370         require(remaining_k!=0, "tlink: bad tree");
 371
 372         if ( t==NULL ) return NULL;
 373         /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/
 374         if ( t->token == EpToken && t->v.rk == remaining_k )
 375         {
 376                 require(t->down==NULL, "tlink: invalid tree");
 377                 if ( u == NULL ) return t->right;
 378                 p = tdup( u );
 379                 p->right = t->right;
 380                 _Tfree( t );
 381                 return p;
 382         }
 383         t->down = tlink(t->down, u, remaining_k);
 384         t->right = tlink(t->right, u, remaining_k);
 385         return t;
 386 }
 387
 388 /* remove as many ALT nodes as possible while still maintaining semantics */
 389 Tree *
 390 #ifdef __STDC__
 391 tshrink( Tree *t )
 392 #else
 393 tshrink( t )
 394 Tree *t;
 395 #endif
 396 {
 397         if ( t == NULL ) return NULL;
 398         t->down = tshrink( t->down );
 399         t->right = tshrink( t->right );
 400         if ( t->down == NULL )
 401         {
 402                 if ( t->token == ALT )
 403                 {
 404                         Tree *u = t->right;
 405                         _Tfree(t);
 406                         return u;                       /* remove useless alts */
 407                 }
 408                 return t;
 409         }
 410
 411         /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
 412         if ( t->token == ALT && t->down->right == NULL)
 413         {
 414                 Tree *u = t->down;
 415                 u->right = t->right;
 416                 _Tfree( t );
 417                 return u;
 418         }
 419         /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
 420         if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
 421         {
 422                 Tree *u = t->down->down;
 423                 _Tfree( t->down );
 424                 t->down = u;
 425                 return t;
 426         }
 427         return t;
 428 }
 429
 430 Tree *
 431 #ifdef __STDC__
 432 tflatten( Tree *t )
 433 #else
 434 tflatten( t )
 435 Tree *t;
 436 #endif
 437 {
 438         if ( t == NULL ) return NULL;
 439         t->down = tflatten( t->down );
 440         t->right = tflatten( t->right );
 441         if ( t->down == NULL ) return t;
 442
 443         if ( t->token == ALT )
 444         {
 445                 Tree *u;
 446                 /* find tail of children */
 447                 for (u=t->down; u->right!=NULL; u=u->right) {;}
 448                 u->right = t->right;
 449                 u = t->down;
 450                 _Tfree( t );
 451                 return u;
 452         }
 453         return t;
 454 }
 455
 456 Tree *
 457 #ifdef __STDC__
 458 tJunc( Junction *p, int k, set *rk )
 459 #else
 460 tJunc( p, k, rk )
 461 Junction *p;
 462 int k;
 463 set *rk;
 464 #endif
 465 {
 466         Tree *t=NULL, *u=NULL;
 467         Junction *alt;
 468         Tree *tail, *r;
 469
 470 #ifdef DBG_TRAV
 471         fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,
 472                         decodeJType[p->jtype], ((Junction *)p)->rname);
 473 #endif
 474         if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
 475                  p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
 476         {
 477                 if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {
 478                         require(p->lock!=NULL, "rJunc: lock array is NULL");
 479                         if ( p->lock[k] ) return NULL;
 480                         p->lock[k] = TRUE;
 481                 }
 482                 TRAV(p->p1, k, rk, tail);
 483                 if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
 484                 r = tmake(tnode(ALT), tail, NULL);
 485                 for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
 486                 {
 487                         /* if this is one of the added optional alts for (...)+ then break */
 488                         if ( alt->ignore ) break;
 489
 490                         if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
 491                         else
 492                         {
 493                                 TRAV(alt->p1, k, rk, tail->right);
 494                                 if ( tail->right != NULL ) tail = tail->right;
 495                         }
 496                 }
 497                 if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
 498 #ifdef DBG_TREES
 499                 fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");
 500 #endif
 501                 if ( r->down == NULL ) {_Tfree(r); return NULL;}
 502                 return r;
 503         }
 504
 505         if ( p->jtype==EndRule )
 506         {
 507                 if ( p->halt )                                          /* don't want FOLLOW here? */
 508                 {
 509 /*                      if ( ContextGuardTRAV ) return NULL;*/
 510                         set_orel(k, rk);                                /* indicate this k value needed */
 511                         t = tnode(EpToken);
 512                         t->v.rk = k;
 513                         return t;
 514                 }
 515                 require(p->lock!=NULL, "rJunc: lock array is NULL");
 516                 if ( p->lock[k] ) return NULL;
 517                 /* if no FOLLOW assume k EOF's */
 518                 if ( p->p1 == NULL ) return eofnode(k);
 519                 p->lock[k] = TRUE;
 520         }
 521
 522         if ( p->p2 == NULL )
 523         {
 524                 TRAV(p->p1, k, rk,t);
 525                 if ( p->jtype==EndRule ) p->lock[k]=FALSE;
 526                 return t;
 527         }
 528         TRAV(p->p1, k, rk, t);
 529         if ( p->jtype!=RuleBlk ) TRAV(p->p2, k, rk, u);
 530         if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */
 531
 532         if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
 533         return tmake(tnode(ALT), t, u, NULL);
 534 }
 535
 536 Tree *
 537 #ifdef __STDC__
 538 tRuleRef( RuleRefNode *p, int k, set *rk_out )
 539 #else
 540 tRuleRef( p, k, rk_out )
 541 RuleRefNode *p;
 542 int k;
 543 set *rk_out;
 544 #endif
 545 {
 546         int k2;
 547         Tree *t, *u;
 548         Junction *r;
 549         set rk, rk2;
 550         int save_halt;
 551         RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
 552
 553 #ifdef DBG_TRAV
 554         fprintf(stderr, "tRuleRef: %s\n", p->text);
 555 #endif
 556         if ( q == NULL )
 557         {
 558                 TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
 559                 return t;
 560         }
 561         rk = rk2 = empty;
 562         r = RulePtr[q->rulenum];
 563         if ( r->lock[k] ) return NULL;
 564         save_halt = r->end->halt;
 565         r->end->halt = TRUE;            /* don't let reach fall off end of rule here */
 566         TRAV(r, k, &rk, t);
 567         r->end->halt = save_halt;
 568 #ifdef DBG_TREES
 569         fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");
 570 #endif
 571         t = tshrink( t );
 572         while ( !set_nil(rk) ) {        /* any k left to do? if so, link onto tree */
 573                 k2 = set_int(rk);
 574                 set_rm(k2, rk);
 575                 TRAV(p->next, k2, &rk2, u);
 576                 t = tlink(t, u, k2);    /* any alts missing k2 toks, add u onto end */
 577         }
 578         set_free(rk);                           /* rk is empty, but free it's memory */
 579         set_orin(rk_out, rk2);          /* remember what we couldn't do */
 580         set_free(rk2);
 581         return t;
 582 }
 583
 584 Tree *
 585 #ifdef __STDC__
 586 tToken( TokNode *p, int k, set *rk )
 587 #else
 588 tToken( p, k, rk )
 589 TokNode *p;
 590 int k;
 591 set *rk;
 592 #endif
 593 {
 594         Tree *t, *tset=NULL, *u;
 595
 596         if ( ConstrainSearch )
 597         {
 598                 require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
 599                 constrain = &fset[maxk-k+1];
 600         }
 601
 602 #ifdef DBG_TRAV
 603         fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));
 604         if ( ConstrainSearch ) {
 605                 fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");
 606         }
 607 #endif
 608         /* is it a meta token (set of tokens)? */
 609         if ( !set_nil(p->tset) )
 610         {
 611                 unsigned e=0;
 612                 set a;
 613                 Tree *n, *tail = NULL;
 614
 615                 if ( ConstrainSearch ) a = set_and(p->tset, *constrain);
 616                 else a = set_dup(p->tset);
 617 #ifdef DUM
 618                 if ( ConstrainSearch ) a = set_dif(p->tset, *constrain);
 619                 else a = set_dup(p->tset);
 620 #endif
 621                 for (; !set_nil(a); set_rm(e, a))
 622                 {
 623                         e = set_int(a);
 624                         n = tnode(e);
 625                         if ( tset==NULL ) { tset = n; tail = n; }
 626                         else { tail->right = n; tail = n; }
 627                 }
 628                 set_free( a );
 629         }
 630         else if ( ConstrainSearch && !set_el(p->token, *constrain) )
 631     {
 632 /*      fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
 633                 k);*/
 634         return NULL;
 635     }
 636         else tset = tnode( p->token );
 637
 638         if ( k == 1 ) return tset;
 639
 640         TRAV(p->next, k-1, rk, t);
 641         /* here, we are positive that, at least, this tree will not contribute
 642          * to the LL(2) tree since it will be too shallow, IF t==NULL.
 643          * If doing a context guard walk, then don't prune.
 644          */
 645         if ( t == NULL && !ContextGuardTRAV )   /* tree will be too shallow */
 646         {
 647                 if ( tset!=NULL ) Tfree( tset );
 648                 return NULL;
 649         }
 650 #ifdef DBG_TREES
 651         fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");
 652 #endif
 653
 654         /* if single token root, then just make new tree and return */
 655         if ( set_nil(p->tset) ) return tmake(tnode(p->token), t, NULL);
 656
 657         /* here we must make a copy of t as a child of each element of the tset;
 658          * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) )
 659          */
 660         for (u=tset; u!=NULL; u=u->right)
 661         {
 662                 /* make a copy of t and hook it onto bottom of u */
 663                 u->down = tdup(t);
 664         }
 665         Tfree( t );
 666 #ifdef DBG_TREES
 667         fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n");
 668 #endif
 669         return tset;
 670 }
 671
 672 Tree *
 673 #ifdef __STDC__
 674 tAction( ActionNode *p, int k, set *rk )
 675 #else
 676 tAction( p, k, rk )
 677 ActionNode *p;
 678 int k;
 679 set *rk;
 680 #endif
 681 {
 682         Tree *t;
 683
 684         /*fprintf(stderr, "tAction\n");*/
 685         TRAV(p->next, k, rk, t);
 686         return t;
 687 }
 688
 689 /* see if e exists in s as a possible input permutation (e is always a chain) */
 690 int
 691 #ifdef __STDC__
 692 tmember( Tree *e, Tree *s )
 693 #else
 694 tmember( e, s )
 695 Tree *e;
 696 Tree *s;
 697 #endif
 698 {
 699         if ( e==NULL||s==NULL ) return 0;
 700         /*fprintf(stderr, "tmember(");
 701         preorder(e); fprintf(stderr, ",");
 702         preorder(s); fprintf(stderr, " )\n");*/
 703         if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
 704         if ( e->token!=s->token )
 705         {
 706                 if ( s->right==NULL ) return 0;
 707                 return tmember(e, s->right);
 708         }
 709         if ( e->down==NULL && s->down == NULL ) return 1;
 710         if ( tmember(e->down, s->down) ) return 1;
 711         if ( s->right==NULL ) return 0;
 712         return tmember(e, s->right);
 713 }
 714
 715 /* see if e exists in s as a possible input permutation (e is always a chain);
 716  * Only check s to the depth of e.  In other words, 'e' can be a shorter
 717  * sequence than s.
 718  */
 719 int
 720 #ifdef __STDC__
 721 tmember_constrained( Tree *e, Tree *s)
 722 #else
 723 tmember_constrained( e, s )
 724 Tree *e;
 725 Tree *s;
 726 #endif
 727 {
 728         if ( e==NULL||s==NULL ) return 0;
 729 /*      fprintf(stderr, "tmember_constrained(");
 730         preorder(e); fprintf(stderr, ",");
 731         preorder(s); fprintf(stderr, " )\n");*/
 732         if ( s->token == ALT && s->right == NULL )
 733                 return tmember_constrained(e, s->down);
 734         if ( e->token!=s->token )
 735         {
 736                 if ( s->right==NULL ) return 0;
 737                 return tmember_constrained(e, s->right);
 738         }
 739         if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */
 740         if ( tmember_constrained(e->down, s->down) ) return 1;
 741         if ( s->right==NULL ) return 0;
 742         return tmember_constrained(e, s->right);
 743 }
 744
 745 /* combine (? (A t) ... (A u) ...) into (? (A t u)) */
 746 Tree *
 747 #ifdef __STDC__
 748 tleft_factor( Tree *t )
 749 #else
 750 tleft_factor( t )
 751 Tree *t;
 752 #endif
 753 {
 754         Tree *u, *v, *trail, *w;
 755
 756         /* left-factor what is at this level */
 757         if ( t == NULL ) return NULL;
 758         for (u=t; u!=NULL; u=u->right)
 759         {
 760                 trail = u;
 761                 v=u->right;
 762                 while ( v!=NULL )
 763                 {
 764                         if ( u->token == v->token )
 765                         {
 766                                 if ( u->down!=NULL )
 767                                 {
 768                                         for (w=u->down; w->right!=NULL; w=w->right) {;}
 769                                         w->right = v->down;     /* link children together */
 770                                 }
 771                                 else u->down = v->down;
 772                                 trail->right = v->right;                /* unlink factored node */
 773                                 _Tfree( v );
 774                                 v = trail->right;
 775                         }
 776                         else {trail = v; v=v->right;}
 777                 }
 778         }
 779         /* left-factor what is below */
 780         for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
 781         return t;
 782 }
 783
 784 /* remove the permutation p from t if present */
 785 Tree *
 786 #ifdef __STDC__
 787 trm_perm( Tree *t, Tree *p )
 788 #else
 789 trm_perm( t, p )
 790 Tree *t;
 791 Tree *p;
 792 #endif
 793 {
 794         /*
 795         fprintf(stderr, "trm_perm(");
 796         preorder(t); fprintf(stderr, ",");
 797         preorder(p); fprintf(stderr, " )\n");
 798         */
 799         if ( t == NULL || p == NULL ) return NULL;
 800         if ( t->token == ALT )
 801         {
 802                 t->down = trm_perm(t->down, p);
 803                 if ( t->down == NULL )                          /* nothing left below, rm cur node */
 804                 {
 805                         Tree *u = t->right;
 806                         _Tfree( t );
 807                         return trm_perm(u, p);
 808                 }
 809                 t->right = trm_perm(t->right, p);       /* look for more instances of p */
 810                 return t;
 811         }
 812         if ( p->token != t->token )                             /* not found, try a sibling */
 813         {
 814                 t->right = trm_perm(t->right, p);
 815                 return t;
 816         }
 817         t->down = trm_perm(t->down, p->down);
 818         if ( t->down == NULL )                                  /* nothing left below, rm cur node */
 819         {
 820                 Tree *u = t->right;
 821                 _Tfree( t );
 822                 return trm_perm(u, p);
 823         }
 824         t->right = trm_perm(t->right, p);               /* look for more instances of p */
 825         return t;
 826 }
 827
 828 /* add the permutation 'perm' to the LL_k sets in 'fset' */
 829 void
 830 #ifdef __STDC__
 831 tcvt( set *fset, Tree *perm )
 832 #else
 833 tcvt( fset, perm )
 834 set *fset;
 835 Tree *perm;
 836 #endif
 837 {
 838         if ( perm==NULL ) return;
 839         set_orel(perm->token, fset);
 840         tcvt(fset+1, perm->down);
 841 }
 842
 843 /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
 844  * as a child.
 845  */
 846 Tree *
 847 #ifdef __STDC__
 848 permute( int k, int max_k )
 849 #else
 850 permute( k, max_k )
 851 int k, max_k;
 852 #endif
 853 {
 854         Tree *t, *u;
 855
 856         if ( k>max_k ) return NULL;
 857         if ( ftbl[k][findex[k]] == nil ) return NULL;
 858         t = permute(k+1, max_k);
 859         if ( t==NULL&&k<max_k )         /* no permutation left below for k+1 tokens? */
 860         {
 861                 findex[k+1] = 0;
 862                 (findex[k])++;                  /* try next token at this k */
 863                 return permute(k, max_k);
 864         }
 865
 866         u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);
 867         if ( k == max_k ) (findex[k])++;
 868         return u;
 869 }
 870
 871 /* Compute LL(k) trees for alts alt1 and alt2 of p.
 872  * function result is tree of ambiguous input permutations
 873  *
 874  * ALGORITHM may change to look for something other than LL_k size
 875  * trees ==> maxk will have to change.
 876  */
 877 Tree *
 878 #ifdef __STDC__
 879 VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )
 880 #else
 881 VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )
 882 Junction *alt1;
 883 Junction *alt2;
 884 unsigned **ft;
 885 set *fs;
 886 Tree **t;
 887 Tree **u;
 888 int *numAmbig;
 889 #endif
 890 {
 891         set rk;
 892         Tree *perm, *ambig=NULL;
 893         Junction *p;
 894         int k;
 895
 896         maxk = LL_k;                            /* NOTE: for now, we look for LL_k */
 897         ftbl = ft;
 898         fset = fs;
 899         constrain = &(fset[1]);
 900         findex = (int *) calloc(LL_k+1, sizeof(int));
 901         if ( findex == NULL )
 902         {
 903                 fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
 904                 fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",
 905                                                 CurAmbigAlt1,
 906                                                 CurAmbigAlt2,
 907                                                 CurAmbigbtype);
 908                 exit(PCCTS_EXIT_FAILURE);
 909         }
 910         for (k=1; k<=LL_k; k++) findex[k] = 0;
 911
 912         rk = empty;
 913         ConstrainSearch = 1;    /* consider only tokens in ambig sets */
 914
 915         p = analysis_point((Junction *)alt1->p1);
 916         TRAV(p, LL_k, &rk, *t);
 917         *t = tshrink( *t );
 918         *t = tflatten( *t );
 919         *t = prune(*t, LL_k);
 920         *t = tleft_factor( *t );
 921 /*      fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
 922         if ( *t == NULL )
 923         {
 924 /*              fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
 925                 Tfree( *t );    /* kill if impossible to have ambig */
 926                 *t = NULL;
 927         }
 928
 929         p = analysis_point((Junction *)alt2->p1);
 930         TRAV(p, LL_k, &rk, *u);
 931         *u = tshrink( *u );
 932         *u = tflatten( *u );
 933         *u = prune(*u, LL_k);
 934         *u = tleft_factor( *u );
 935 /*      fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/
 936         if ( *u == NULL )
 937         {
 938 /*              fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
 939                 Tfree( *u );
 940                 *u = NULL;
 941         }
 942
 943         for (k=1; k<=LL_k; k++) set_clr( fs[k] );
 944
 945         ambig = tnode(ALT);
 946         k = 0;
 947         if ( *t!=NULL && *u!=NULL )
 948         {
 949                 while ( (perm=permute(1,LL_k))!=NULL )
 950                 {
 951 /*                      fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
 952                         if ( tmember(perm, *t) && tmember(perm, *u) )
 953                         {
 954 /*                              fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/
 955                                 k++;
 956                                 perm->right = ambig->down;
 957                                 ambig->down = perm;
 958                                 tcvt(&(fs[1]), perm);
 959                         }
 960                         else Tfree( perm );
 961                 }
 962         }
 963
 964         *numAmbig = k;
 965         if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}
 966         free( (char *)findex );
 967 /*      fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
 968         return ambig;
 969 }
 970
 971 static Tree *
 972 #ifdef __STDC__
 973 bottom_of_chain( Tree *t )
 974 #else
 975 bottom_of_chain( t )
 976 Tree *t;
 977 #endif
 978 {
 979     if ( t==NULL ) return NULL;
 980     for (; t->down != NULL; t=t->down) {;}
 981     return t;
 982 }
 983
 984 /*
 985  * Make a tree from k sets where the degree of the first k-1 sets is 1.
 986  */
 987 Tree *
 988 #ifdef __STDC__
 989 make_tree_from_sets( set *fset1, set *fset2 )
 990 #else
 991 make_tree_from_sets( fset1, fset2 )
 992 set *fset1;
 993 set *fset2;
 994 #endif
 995 {
 996         set inter;
 997         int i;
 998         Tree *t=NULL, *n, *u;
 999         unsigned *p,*q;
1000         require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");
1001
1002         /* do the degree 1 sets first */
1003         for (i=1; i<=LL_k-1; i++)
1004         {
1005                 inter = set_and(fset1[i], fset2[i]);
1006                 require(set_deg(inter)==1, "invalid set to tree conversion");
1007                 n = tnode(set_int(inter));
1008                 if (t==NULL) t=n; else tmake(t, n, NULL);
1009                 set_free(inter);
1010         }
1011
1012         /* now add the chain of tokens at depth k */
1013         u = bottom_of_chain(t);
1014         inter = set_and(fset1[LL_k], fset2[LL_k]);
1015         if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq");
1016         /* first one is linked to bottom, then others are sibling linked */
1017         n = tnode(*p++);
1018         u->down = n;
1019         u = u->down;
1020         while ( *p != nil )
1021         {
1022                 n = tnode(*p);
1023                 u->right = n;
1024                 u = u->right;
1025                 p++;
1026         }
1027         free((char *)q);
1028
1029         return t;
1030 }
1031
1032 /* create and return the tree of lookahead k-sequences that are in t, but not
1033  * in the context of predicates in predicate list p.
1034  */
1035 Tree *
1036 #ifdef __STDC__
1037 tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )
1038 #else
1039 tdif( ambig_tuples, p, fset1, fset2 )
1040 Tree *ambig_tuples;
1041 Predicate *p;
1042 set *fset1;
1043 set *fset2;
1044 #endif
1045 {
1046         unsigned **ft;
1047         Tree *dif=NULL;
1048         Tree *perm;
1049         set b;
1050         int i,k;
1051
1052         if ( p == NULL ) return tdup(ambig_tuples);
1053
1054         ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
1055         require(ft!=NULL, "cannot allocate ft");
1056         for (i=1; i<=CLL_k; i++)
1057         {
1058                 b = set_and(fset1[i], fset2[i]);
1059                 ft[i] = set_pdq(b);
1060                 set_free(b);
1061         }
1062         findex = (int *) calloc(LL_k+1, sizeof(int));
1063         if ( findex == NULL )
1064         {
1065                 fatal_internal("out of memory in tdif while checking predicates");
1066         }
1067         for (k=1; k<=LL_k; k++) findex[k] = 0;
1068
1069 #ifdef DBG_TRAV
1070         fprintf(stderr, "tdif_%d[", p->k);
1071         preorder(ambig_tuples);
1072         fprintf(stderr, ",");
1073         preorder(p->tcontext);
1074         fprintf(stderr, "] =");
1075 #endif
1076
1077         ftbl = ft;
1078         while ( (perm=permute(1,p->k))!=NULL )
1079         {
1080 #ifdef DBG_TRAV
1081                 fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n");
1082 #endif
1083                 if ( tmember_constrained(perm, ambig_tuples) &&
1084                          !tmember_of_context(perm, p) )
1085                 {
1086 #ifdef DBG_TRAV
1087                         fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n");
1088 #endif
1089                         k++;
1090                         if ( dif==NULL ) dif = perm;
1091                         else
1092                         {
1093                                 perm->right = dif;
1094                                 dif = perm;
1095                         }
1096                 }
1097                 else Tfree( perm );
1098         }
1099
1100 #ifdef DBG_TRAV
1101         preorder(dif);
1102         fprintf(stderr, "\n");
1103 #endif
1104
1105         for (i=1; i<=CLL_k; i++) free( (char *)ft[i] );
1106         free((char *)ft);
1107         free((char *)findex);
1108
1109         return dif;
1110 }
1111
1112 /* is lookahead sequence t a member of any context tree for any
1113  * predicate in p?
1114  */
1115 static int
1116 #ifdef __STDC__
1117 tmember_of_context( Tree *t, Predicate *p )
1118 #else
1119 tmember_of_context( t, p )
1120 Tree *t;
1121 Predicate *p;
1122 #endif
1123 {
1124         for (; p!=NULL; p=p->right)
1125         {
1126                 if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST )
1127                         return tmember_of_context(t, p->down);
1128                 if ( tmember_constrained(t, p->tcontext) ) return 1;
1129                 if ( tmember_of_context(t, p->down) ) return 1;
1130         }
1131         return 0;
1132 }
1133
1134 int
1135 #ifdef __STDC__
1136 is_single_tuple( Tree *t )
1137 #else
1138 is_single_tuple( t )
1139 Tree *t;
1140 #endif
1141 {
1142         if ( t == NULL ) return 0;
1143         if ( t->right != NULL ) return 0;
1144         if ( t->down == NULL ) return 1;
1145         return is_single_tuple(t->down);
1146 }
1147
1148 /*
1149  * Look at a (...)? generalized-predicate context-guard and compute
1150  * either a lookahead set (k==1) or a lookahead tree for k>1.  The
1151  * k level is determined by the guard itself rather than the LL_k
1152  * variable.  For example, ( A B )? is an LL(2) guard and ( ID )?
1153  * is an LL(1) guard.  For the moment, you can only have a single
1154  * tuple in the guard.  Physically, the block must look like this
1155  *   --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o--
1156  * An error is printed for any other type.
1157  */
1158 Predicate *
1159 #ifdef __STDC__
1160 computePredicateFromContextGuard(Graph blk)
1161 #else
1162 computePredicateFromContextGuard(blk)
1163 Graph blk;
1164 #endif
1165 {
1166     Junction *junc = (Junction *)blk.left, *p;
1167         Tree *t;
1168         Predicate *pred = NULL;
1169         set scontext, rk;
1170     require(junc!=NULL && junc->ntype == nJunction, "bad context guard");
1171
1172         rk = empty;
1173         p = junc;
1174         pred = new_pred();
1175         pred->k = LL_k;
1176         if ( LL_k > 1 )
1177         {
1178                 ConstrainSearch = 0;
1179                 ContextGuardTRAV = 1;
1180                 TRAV(p, LL_k, &rk, t);
1181                 ContextGuardTRAV = 0;
1182                 set_free(rk);
1183                 t = tshrink( t );
1184                 t = tflatten( t );
1185                 t = tleft_factor( t );
1186 /*
1187                 fprintf(stderr, "ctx guard:");
1188                 preorder(t);
1189                 fprintf(stderr, "\n");
1190 */
1191                 pred->tcontext = t;
1192         }
1193         else
1194         {
1195                 REACH(p, 1, &rk, scontext);
1196                 require(set_nil(rk), "rk != nil");
1197                 set_free(rk);
1198 /*
1199                 fprintf(stderr, "LL(1) ctx guard is:");
1200                 s_fprT(stderr, scontext);
1201                 fprintf(stderr, "\n");
1202 */
1203                 pred->scontext[1] = scontext;
1204         }
1205
1206         return pred;
1207 }