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

   1 /*
   2  * fset.c
   3  *
   4  * $Id: fset.c,v 1.6 95/06/15 18:07:09 parrt Exp $
   5  * $Revision: 1.6 $
   6  *
   7  * Compute FIRST and FOLLOW sets.
   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 #include "set.h"
  42 #include "syn.h"
  43 #include "hash.h"
  44 #include "generic.h"
  45 #include "dlgdef.h"
  46
  47 extern char *PRED_AND_LIST;
  48 extern char *PRED_OR_LIST;
  49
  50 #ifdef __STDC__
  51 static void ensure_predicates_cover_ambiguous_lookahead_sequences(Junction *, Junction *, char *, Tree *);
  52 #else
  53 static void ensure_predicates_cover_ambiguous_lookahead_sequences();
  54 #endif
  55
  56 /*
  57  * What tokens are k tokens away from junction q?
  58  *
  59  * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
  60  * node.
  61  * We lock the junction according to k--the lookahead.  If we have been at this
  62  * junction before looking for the same, k, number of lookahead tokens, we will
  63  * do it again and again...until we blow up the stack.  Locks are only used on aLoopBlk,
  64  * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from
  65  * FIRST and FOLLOW calcs.
  66  *
  67  * If p->jtype == EndRule we are going to attempt a FOLLOW.  (FOLLOWs are really defined
  68  * in terms of FIRST's, however).  To proceed with the FOLLOW, p->halt cannot be
  69  * set.  p->halt is set to indicate that a reference to the current rule is in progress
  70  * and the FOLLOW is not desirable.
  71  *
  72  * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule
  73  * junction yields an empty set, replace the empty set with EOF.  No FOLLOW means that
  74  * only EOF can follow the current rule.  This normally occurs only on the start symbol
  75  * since all other rules are referenced by another rule somewhere.
  76  *
  77  * Normally, both p1 and p2 are followed.  However, checking p2 on a RuleBlk node is
  78  * the same as checking the next rule which is clearly incorrect.
  79  *
  80  * Cycles in the FOLLOW sense are possible.  e.g. Fo(c) requires Fo(b) which requires
  81  * Fo(c).  Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c).  Let's say
  82  * Fo(c) is attempted first.  It finds all of the FOLLOW symbols and then attempts
  83  * to do Fo(b) which finds of its FOLLOW symbols.  So, we have:
  84  *
  85  *                  Fo(c)
  86  *                 /     \
  87  *              a set    Fo(b)
  88  *                      /     \
  89  *                   a set    Fo(c) .....Hmmmm..... Infinite recursion!
  90  *
  91  * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now
  92  * correctly Fo(c) union Fo(b).  We wish to pick up where we left off, so the fact
  93  * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already
  94  * laying around.  SOOOOoooo, we track FOLLOW cycles.  All FOLLOW computations are
  95  * cached in a hash table.  After the sequence of FOLLOWs finish, we reconcile all
  96  * cycles --> correct all Fo(rule) sets in the cache.
  97  *
  98  * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
  99  * TJP 8/93 -- can now read PhD thesis from Purdue.
 100  *
 101  * Also, FIRST sets are cached in the hash table.  Keys are (rulename,Fi/Fo,k).
 102  * Only FIRST sets, for which the FOLLOW is not included, are stored.
 103  *
 104  * SPECIAL CASE of (...)+ blocks:
 105  * I added an optional alt so that the alts could see what
 106  * was behind the (...)+ block--thus using enough lookahead
 107  * to branch out rather than just enough to distinguish
 108  * between alts in the (...)+.  However, when the FIRST("(...)+") is
 109  * is needed, must not use this last "optional" alt.  This routine
 110  * turns off this path by setting a new 'ignore' flag for
 111  * the alt and then resetting it afterwards.
 112  */
 113 set
 114 #ifdef __STDC__
 115 rJunc( Junction *p, int k, set *rk )
 116 #else
 117 rJunc( p, k, rk )
 118 Junction *p;
 119 int k;
 120 set *rk;
 121 #endif
 122 {
 123         set a, b;
 124         require(p!=NULL,                                "rJunc: NULL node");
 125         require(p->ntype==nJunction,    "rJunc: not junction");
 126
 127 #ifdef DBG_LL1
 128         if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k);
 129         else fprintf(stderr, "rJunc: %s in rule %s\n",
 130                         decodeJType[p->jtype], ((Junction *)p)->rname);
 131 #endif
 132         /* if this is one of the added optional alts for (...)+ then return */
 133         if ( p->ignore ) return empty;
 134
 135         /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */
 136         if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
 137                  p->jtype==aPlusBlk || p->jtype==EndRule )
 138         {
 139                 require(p->lock!=NULL, "rJunc: lock array is NULL");
 140                 if ( p->lock[k] )
 141                 {
 142                         if ( p->jtype == EndRule )      /* FOLLOW cycle? */
 143                         {
 144 #ifdef DBG_LL1
 145                                 fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);
 146 #endif
 147                                 RegisterCycle(p->rname, k);
 148                         }
 149                         return empty;
 150                 }
 151                 if ( p->jtype == RuleBlk && p->end->halt )      /* check for FIRST cache */
 152                 {
 153                         CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
 154                         if ( q != NULL )
 155                         {
 156                                 set_orin(rk, q->rk);
 157                                 return set_dup( q->fset );
 158                         }
 159                 }
 160                 if ( p->jtype == EndRule )              /* FOLLOW set cached already? */
 161                 {
 162                         CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
 163                         if ( q != NULL )
 164                         {
 165 #ifdef DBG_LL1
 166                                 fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k);
 167                                 s_fprT(stderr, q->fset);
 168                                 if ( q->incomplete ) fprintf(stderr, " (incomplete)");
 169                                 fprintf(stderr, "\n");
 170 #endif
 171                                 if ( !q->incomplete )
 172                                 {
 173                                         return set_dup( q->fset );
 174                                 }
 175                         }
 176                 }
 177                 p->lock[k] = TRUE;      /* This rule is busy */
 178         }
 179
 180         a = b = empty;
 181
 182         if ( p->jtype == EndRule )
 183         {
 184                 if ( p->halt )                                                          /* don't want FOLLOW here? */
 185                 {
 186                         p->lock[k] = FALSE;
 187                         set_orel(k, rk);                                                /* indicate this k value needed */
 188                         return empty;
 189                 }
 190                 FoPush(p->rname, k);                                            /* Attempting FOLLOW */
 191                 if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */
 192 #ifdef DBG_LL1
 193                 fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);
 194 #endif
 195         }
 196
 197         if ( p->p1 != NULL ) REACH(p->p1, k, rk, a);
 198
 199         /* C a c h e  R e s u l t s */
 200         if ( p->jtype == RuleBlk && p->end->halt )              /* can save FIRST set? */
 201         {
 202                 CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) );
 203                 /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/
 204                 hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q);
 205                 q->fset = set_dup( a );
 206                 q->rk = set_dup( *rk );
 207         }
 208
 209         if ( p->jtype == EndRule )                                              /* just completed FOLLOW? */
 210         {
 211                 /* Cache Follow set */
 212                 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
 213                 if ( q==NULL )
 214                 {
 215                         q = newCacheEntry( Fkey(p->rname,'o',k) );
 216                         hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
 217                 }
 218                 /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
 219                 if ( set_nil(a) && !q->incomplete )
 220                 {
 221                         /* Don't ever save a nil set as complete.
 222                          * Turn it into an eof set.
 223                          */
 224                         set_orel(EofToken, &a);
 225                 }
 226                 set_orin(&(q->fset), a);
 227                 FoPop( k );
 228                 if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
 229 #ifdef DBG_LL1
 230                 fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k);
 231                 s_fprT(stderr, q->fset);
 232                 if ( q->incomplete ) fprintf(stderr, " (incomplete)");
 233                 fprintf(stderr, "\n");
 234 #endif
 235         }
 236
 237         if ( p->jtype != RuleBlk && p->p2 != NULL ) REACH(p->p2, k, rk, b);
 238         if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
 239                  p->jtype==aPlusBlk || p->jtype==EndRule )
 240                 p->lock[k] = FALSE;                                                     /* unlock node */
 241
 242         set_orin(&a, b);
 243         set_free(b);
 244         return a;
 245 }
 246
 247 set
 248 #ifdef __STDC__
 249 rRuleRef( RuleRefNode *p, int k, set *rk_out )
 250 #else
 251 rRuleRef( p, k, rk_out )
 252 RuleRefNode *p;
 253 int k;
 254 set *rk_out;
 255 #endif
 256 {
 257         set rk;
 258         Junction *r;
 259         int k2;
 260         set a, rk2, b;
 261         int save_halt;
 262         RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
 263         require(p!=NULL,                        "rRuleRef: NULL node");
 264         require(p->ntype==nRuleRef,     "rRuleRef: not rule ref");
 265
 266 #ifdef DBG_LL1
 267         fprintf(stderr, "rRuleRef: %s\n", p->text);
 268 #endif
 269         if ( q == NULL )
 270         {
 271                 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
 272                 REACH(p->next, k, rk_out, a);
 273                 return a;
 274         }
 275         rk2 = empty;
 276         r = RulePtr[q->rulenum];
 277         if ( r->lock[k] )
 278         {
 279                 errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
 280                                                 r->rname, p->rname) );
 281                 return empty;
 282         }
 283         save_halt = r->end->halt;
 284         r->end->halt = TRUE;            /* don't let reach fall off end of rule here */
 285         rk = empty;
 286         REACH(r, k, &rk, a);
 287         r->end->halt = save_halt;
 288         while ( !set_nil(rk) ) {
 289                 k2 = set_int(rk);
 290                 set_rm(k2, rk);
 291                 REACH(p->next, k2, &rk2, b);
 292                 set_orin(&a, b);
 293                 set_free(b);
 294         }
 295         set_free(rk);                           /* this has no members, but free it's memory */
 296         set_orin(rk_out, rk2);          /* remember what we couldn't do */
 297         set_free(rk2);
 298         return a;
 299 }
 300
 301 /*
 302  * Return FIRST sub k ( token_node )
 303  *
 304  * TJP 10/11/93 modified this so that token nodes that are actually
 305  * ranges (T1..T2) work.
 306  */
 307 set
 308 #ifdef __STDC__
 309 rToken( TokNode *p, int k, set *rk )
 310 #else
 311 rToken( p, k, rk )
 312 TokNode *p;
 313 int k;
 314 set *rk;
 315 #endif
 316 {
 317         set a;
 318         require(p!=NULL,                        "rToken: NULL node");
 319         require(p->ntype==nToken,       "rToken: not token node");
 320
 321 #ifdef DBG_LL1
 322         fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):
 323                                                                         ExprString(p->token));
 324 #endif
 325         if ( k-1 == 0 )
 326         {
 327                 if ( !set_nil(p->tset) ) return set_dup(p->tset);
 328                 return set_of(p->token);
 329         }
 330         REACH(p->next, k-1, rk, a);
 331
 332         return a;
 333 }
 334
 335 set
 336 #ifdef __STDC__
 337 rAction( ActionNode *p, int k, set *rk )
 338 #else
 339 rAction( p, k, rk )
 340 ActionNode *p;
 341 int k;
 342 set *rk;
 343 #endif
 344 {
 345         set a;
 346         require(p!=NULL,                        "rJunc: NULL node");
 347         require(p->ntype==nAction,      "rJunc: not action");
 348
 349         REACH(p->next, k, rk, a);       /* ignore actions */
 350         return a;
 351 }
 352
 353                                 /* A m b i g u i t y  R e s o l u t i o n */
 354
 355
 356 void
 357 #ifdef __STDC__
 358 dumpAmbigMsg( set *fset, FILE *f, int want_nls )
 359 #else
 360 dumpAmbigMsg( fset, f, want_nls )
 361 set *fset;
 362 FILE *f;
 363 int want_nls;
 364 #endif
 365 {
 366         int i;
 367
 368         if ( want_nls ) fprintf(f, "\n\t");
 369         else fprintf(f, " ");
 370         for (i=1; i<=CLL_k; i++)
 371         {
 372                 if ( i>1 )
 373                 {
 374                         if ( !want_nls ) fprintf(f, ", ");
 375                 }
 376                 if ( set_deg(fset[i]) > 3 && elevel == 1 )
 377                 {
 378                         int e,m;
 379                         fprintf(f, "{");
 380                         for (m=1; m<=3; m++)
 381                         {
 382                                 e=set_int(fset[i]);
 383                                 fprintf(f, " %s", TerminalString(e));
 384                                 set_rm(e, fset[i]);
 385                         }
 386                         fprintf(f, " ... }");
 387                 }
 388                 else s_fprT(f, fset[i]);
 389                 if ( want_nls ) fprintf(f, "\n\t");
 390         }
 391         fprintf(f, "\n");
 392 }
 393
 394 static void
 395 #ifdef __USE_PROTOS
 396 verify_context(Predicate *predicate)
 397 #else
 398 verify_context(predicate)
 399 Predicate *predicate;
 400 #endif
 401 {
 402         if ( predicate == NULL ) return;
 403
 404         if ( predicate->expr == PRED_OR_LIST ||
 405                  predicate->expr == PRED_AND_LIST )
 406         {
 407                 verify_context(predicate->down);
 408                 return;
 409         }
 410
 411         if ( !predicate->source->ctxwarned && predicate->source->guardpred==NULL &&
 412                  ((predicate->k > 1 &&
 413                  !is_single_tuple(predicate->tcontext)) ||
 414                  ( predicate->k == 1 &&
 415                           set_deg(predicate->scontext[1])>1 )) )
 416         {
 417                 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],
 418                                 predicate->source->line);
 419                 fprintf(stderr, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate->k);
 420                 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],
 421                                 predicate->source->line);
 422                 fprintf(stderr, " [you may only want one lookahead %d-sequence to apply.\n", predicate->k);
 423                 fprintf(stderr, ErrHdr, FileStr[predicate->source->file],
 424                                 predicate->source->line);
 425                 fprintf(stderr, "  Try using a context guard '(...)? =>'.]\n");
 426                 predicate->source->ctxwarned = 1;
 427         }
 428 }
 429
 430 /*
 431  * If delta is the set of ambiguous lookahead sequences, then make sure that
 432  * the predicate(s) for productions alt1,alt2 cover the sequences in delta.
 433  *
 434  * For example,
 435  *      a : <<PRED1>>? (A B|A C)
 436  *        | b
 437  *    ;
 438  *      b : <<PRED2>>? A B
 439  *        | A C
 440  *        ;
 441  *
 442  * This should give a warning that (A C) predicts both productions and alt2
 443  * does not have a predicate in the production that generates (A C).
 444  *
 445  * The warning detection is simple.  Let delta = LOOK(alt1) intersection LOOK(alt2).
 446  * Now, if ( delta set-difference context(predicates-for-alt1) != empty then
 447  * alt1 does not "cover" all ambiguous sequences.
 448  *
 449  * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset
 450  * info.  Actually, sets are used only if k=1 for this grammar.
 451  */
 452 static void
 453 #ifdef __USE_PROTOS
 454 ensure_predicates_cover_ambiguous_lookahead_sequences( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )
 455 #else
 456 ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )
 457 Junction *alt1;
 458 Junction *alt2;
 459 char *sub;
 460 Tree *ambig;
 461 #endif
 462 {
 463         if ( !ParseWithPredicates ) return;
 464
 465         if ( ambig!=NULL )
 466         {
 467                 Tree *non_covered = NULL;
 468                 if ( alt1->predicate!=NULL )
 469                         non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset);
 470                 if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 )
 471                 {
 472                         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 473                         fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
 474                                                         alt1->altnum, sub);
 475                         if ( alt1->predicate!=NULL && non_covered!=NULL )
 476                         {
 477                                 fprintf(stderr, " upon");
 478                                 preorder(non_covered);
 479                         }
 480                         else if ( alt1->predicate==NULL )
 481                         {
 482                                 fprintf(stderr, " upon");
 483                                 preorder(ambig->down);
 484                         }
 485                         fprintf(stderr, "\n");
 486                 }
 487                 Tfree(non_covered);
 488                 non_covered = NULL;
 489                 if ( alt2->predicate!=NULL )
 490                         non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset);
 491                 if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 )
 492                 {
 493                         fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
 494                         fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
 495                                                         alt2->altnum, sub);
 496                         if ( alt2->predicate!=NULL && non_covered!=NULL )
 497                         {
 498                                 fprintf(stderr, " upon");
 499                                 preorder(non_covered);
 500                         }
 501                         else if ( alt2->predicate==NULL )
 502                         {
 503                                 fprintf(stderr, " upon");
 504                                 preorder(ambig->down);
 505                         }
 506                         fprintf(stderr, "\n");
 507                 }
 508                 Tfree(non_covered);
 509         }
 510         else if ( !set_nil(alt1->fset[1]) )
 511         {
 512                 set delta, non_covered;
 513                 delta = set_and(alt1->fset[1], alt2->fset[1]);
 514                 non_covered = set_dif(delta, covered_set(alt1->predicate));
 515                 if ( set_deg(non_covered)>0 && WarningLevel>1 )
 516                 {
 517                         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 518                         fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
 519                                                         alt1->altnum, sub);
 520                         if ( alt1->predicate!=NULL )
 521                         {
 522                                 fprintf(stderr, " upon ");
 523                                 s_fprT(stderr, non_covered);
 524                         }
 525                         fprintf(stderr, "\n");
 526                 }
 527                 set_free( non_covered );
 528                 non_covered = set_dif(delta, covered_set(alt2->predicate));
 529                 if ( set_deg(non_covered)>0 && WarningLevel>1 )
 530                 {
 531                         fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
 532                         fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
 533                                                         alt2->altnum, sub);
 534                         if ( alt2->predicate!=NULL )
 535                         {
 536                                 fprintf(stderr, " upon ");
 537                                 s_fprT(stderr, non_covered);
 538                         }
 539                         fprintf(stderr, "\n");
 540                 }
 541                 set_free( non_covered );
 542                 set_free( delta );
 543         }
 544         else fatal_internal("productions have no lookahead in predicate checking routine");
 545 }
 546
 547 void
 548 #ifdef __STDC__
 549 HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )
 550 #else
 551 HandleAmbiguity( block, alt1, alt2, jtype )
 552 Junction *block;
 553 Junction *alt1;
 554 Junction *alt2;
 555 int jtype;
 556 #endif
 557 {
 558         unsigned **ftbl;
 559         set *fset, b;
 560         int i, numAmbig, n, n2;
 561         Tree *ambig=NULL, *t, *u;
 562         char *sub = "";
 563         require(block!=NULL, "NULL block");
 564         require(block->ntype==nJunction, "invalid block");
 565
 566         /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */
 567         fset = (set *) calloc(CLL_k+1, sizeof(set));
 568         require(fset!=NULL, "cannot allocate fset");
 569         ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
 570         require(ftbl!=NULL, "cannot allocate ftbl");
 571         /* create constraint table and count number of possible ambiguities (use<=LL_k) */
 572         for (n=1,i=1; i<=CLL_k; i++)
 573         {
 574                 b = set_and(alt1->fset[i], alt2->fset[i]);
 575                 n *= set_deg(b);
 576                 fset[i] = set_dup(b);
 577                 ftbl[i] = set_pdq(b);
 578                 set_free(b);
 579         }
 580
 581         switch ( jtype )
 582         {
 583                 case aSubBlk: sub = "of (..) "; break;
 584                 case aOptBlk: sub = "of {..} "; break;
 585                 case aLoopBegin: sub = "of (..)* "; break;
 586                 case aLoopBlk: sub = "of (..)* "; break;
 587                 case aPlusBlk: sub = "of (..)+ "; break;
 588                 case RuleBlk: sub = "of the rule itself "; break;
 589                 default : sub = ""; break;
 590         }
 591
 592         /* If the block is marked as a compressed lookahead only block, then
 593          * simply return; ambiguity warning is given only at warning level 2.
 594          */
 595         if ( block->approx>0 )
 596         {
 597                 if ( ParseWithPredicates )
 598                 {
 599                         alt1->predicate = find_predicates((Node *)alt1->p1);
 600                         alt2->predicate = find_predicates((Node *)alt2->p1);
 601                         if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
 602                         {
 603                                 verify_context(alt1->predicate);
 604                                 verify_context(alt2->predicate);
 605                         }
 606
 607                         if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
 608                         ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
 609                 }
 610
 611                 if ( WarningLevel>1 )
 612                 {
 613                         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 614                         if ( jtype == aLoopBegin || jtype == aPlusBlk )
 615                                 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
 616                         else
 617                                 fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon",
 618                                                 alt1->altnum, alt2->altnum, sub);
 619                         dumpAmbigMsg(fset, stderr, 0);
 620                 }
 621                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 622                 free((char *)fset);
 623                 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 624                 free((char *)ftbl);
 625                 return;
 626     }
 627
 628         /* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation;
 629          * don't bother doing full LL(k) analysis.
 630          * (This "if" block handles the LL(1) case)
 631          */
 632         n2 = 0;
 633         for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]);
 634         if ( n2==2*(LL_k-1) )
 635         {
 636 /* TJP: added to fix the case where LL(1) and syntactic predicates didn't
 637  * work.  It now recognizes syntactic predicates, but does not like combo:
 638  * LL(1)/syn/sem predicates. (10/24/93)
 639  */
 640                 if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
 641                 {
 642                         if ( WarningLevel==1 )
 643                         {
 644                                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 645                                 free((char *)fset);
 646                                 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 647                                 free((char *)ftbl);
 648                                 return;
 649                         }
 650
 651                         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 652                         if ( jtype == aLoopBegin || jtype == aPlusBlk )
 653                            fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
 654                         else
 655                            fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
 656                                            alt1->altnum, alt2->altnum, sub);
 657                         dumpAmbigMsg(fset, stderr, 0);
 658                 }
 659
 660                 ambig = NULL;
 661                 if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset);
 662                 if ( ParseWithPredicates )
 663                 {
 664                    alt1->predicate = find_predicates((Node *)alt1->p1);
 665                    alt2->predicate = find_predicates((Node *)alt2->p1);
 666                    if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
 667                    {
 668                                 verify_context(alt1->predicate);
 669                                 verify_context(alt2->predicate);
 670                    }
 671                    if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1)
 672                           ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
 673                    if ( WarningLevel == 1 &&
 674                            (alt1->predicate!=NULL||alt2->predicate!=NULL))
 675                    {
 676                           for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 677                           free((char *)fset);
 678                           for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 679                           free((char *)ftbl);
 680                           Tfree(ambig);
 681                           return;
 682                    }
 683                 }
 684 /* end TJP (10/24/93) */
 685
 686                 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 687                 if ( jtype == aLoopBegin || jtype == aPlusBlk )
 688                         fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
 689                 else
 690                    fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
 691                                    alt1->altnum, alt2->altnum, sub);
 692                 if ( elevel == 3 && LL_k>1 )
 693                 {
 694                    preorder(ambig);
 695                    fprintf(stderr, "\n");
 696                    Tfree(ambig);
 697                    return;
 698             }
 699                 Tfree(ambig);
 700                 dumpAmbigMsg(fset, stderr, 0);
 701
 702                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 703                 free((char *)fset);
 704                 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 705                 free((char *)ftbl);
 706                 return;
 707         }
 708
 709         /* in case tree construction runs out of memory, set info to make good err msg */
 710         CurAmbigAlt1 = alt1->altnum;
 711         CurAmbigAlt2 = alt2->altnum;
 712         CurAmbigbtype = sub;
 713         CurAmbigfile = alt1->file;
 714         CurAmbigline = alt1->line;
 715
 716         /* Don't do full LL(n) analysis if (...)? block because the block,
 717            by definition, defies LL(n) analysis.
 718            If guess (...)? block and ambiguous then don't remove anything from
 719            2nd alt to resolve ambig.
 720            Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block
 721            since it is much cheaper than LL(n).  LL sup 1 ( n ) "covers" the LL(n)
 722            lookahead information.
 723
 724            Note: LL(n) context cannot be computed for semantic predicates when
 725            followed by (..)?.
 726
 727            If (..)? then we scream "AAAHHHH!  No LL(n) analysis will help"
 728
 729        Is 'ambig' always defined if we enter this if?  I hope so
 730            because the 'ensure...()' func references it. TJP Nov 1993.
 731            */
 732         if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
 733         {
 734                 if ( ParseWithPredicates )
 735                 {
 736                         alt1->predicate = find_predicates((Node *)alt1->p1);
 737                         alt2->predicate = find_predicates((Node *)alt2->p1);
 738                         if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
 739                         {
 740                                 verify_context(alt1->predicate);
 741                                 verify_context(alt2->predicate);
 742                         }
 743                         if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
 744                                 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
 745                         if ( WarningLevel==1 &&
 746                                 (alt1->predicate!=NULL||alt2->predicate!=NULL))
 747                         {
 748                                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 749                                 free((char *)fset);
 750                                 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 751                                 free((char *)ftbl);
 752                                 return;
 753                         }
 754                 }
 755
 756                 if ( WarningLevel>1 )
 757                 {
 758                         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 759                         if ( jtype == aLoopBegin || jtype == aPlusBlk )
 760                                 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
 761                         else
 762                                 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
 763                                                 alt1->altnum, alt2->altnum, sub);
 764                         dumpAmbigMsg(fset, stderr, 0);
 765                 }
 766
 767                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 768                 free((char *)fset);
 769                 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 770                 free((char *)ftbl);
 771                 return;
 772         }
 773
 774         /* Not resolved with (..)? block.  Do full LL(n) analysis */
 775
 776         /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */
 777         ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);
 778         for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
 779         free((char *)ftbl);
 780
 781         /* are all things in intersection really ambigs? */
 782         if ( numAmbig < n )
 783         {
 784                 Tree *v;
 785
 786                 /* remove ambig permutation from 2nd alternative to resolve ambig;
 787                  * We want to compute the set of artificial tuples, arising from
 788                  * LL sup 1 (n) compression, that collide with real tuples from the
 789                  * 2nd alternative.  This is the set of "special case" tuples that
 790                  * the LL sup 1 (n) decision template maps incorrectly.
 791                  */
 792                 if ( ambig!=NULL )
 793                 {
 794                         for (v=ambig->down; v!=NULL; v=v->right)
 795                         {
 796                                 u = trm_perm(u, v);
 797                         }
 798 /*                      fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
 799                 }
 800                 Tfree( t );
 801                 alt1->ftree = tappend(alt1->ftree, u);
 802                 alt1->ftree = tleft_factor(alt1->ftree);
 803         }
 804
 805         if ( ambig==NULL )
 806         {
 807                 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 808                 free((char *)fset);
 809                 return;
 810         }
 811
 812         ambig = tleft_factor(ambig);
 813
 814 /* TJP:
 815  * At this point, we surely have an LL(k) ambiguity.  Check for predicates
 816  */
 817         if ( ParseWithPredicates )
 818         {
 819                 alt1->predicate = find_predicates((Node *)alt1->p1);
 820                 alt2->predicate = find_predicates((Node *)alt2->p1);
 821                 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
 822                 {
 823                         verify_context(alt1->predicate);
 824                         verify_context(alt2->predicate);
 825                 }
 826                 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
 827                    ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
 828                 if ( WarningLevel==1 &&
 829                         (alt1->predicate!=NULL||alt2->predicate!=NULL))
 830                 {
 831                         /* We found at least one pred for at least one of the alts;
 832                          * If warnings are low, just return.
 833                          */
 834                         Tfree(ambig);
 835                         return;
 836                 }
 837                 /* else we're gonna give a warning */
 838         }
 839 /* end TJP addition */
 840
 841         fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
 842         if ( jtype == aLoopBegin || jtype == aPlusBlk )
 843                 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
 844         else
 845                 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
 846                                         alt1->altnum, alt2->altnum, sub);
 847         if ( elevel == 3 )
 848         {
 849                 preorder(ambig->down);
 850                 fprintf(stderr, "\n");
 851                 Tfree(ambig);
 852                 return;
 853         }
 854         Tfree(ambig);
 855         dumpAmbigMsg(fset, stderr, 0);
 856         for (i=1; i<=CLL_k; i++) set_free( fset[i] );
 857         free((char *)fset);
 858 }
 859
 860 /* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze
 861  * Return the 1st node of the beta block if present else return j.
 862  */
 863 Junction *
 864 #ifdef __STDC__
 865 analysis_point( Junction *j )
 866 #else
 867 analysis_point( j )
 868 Junction *j;
 869 #endif
 870 {
 871         Junction *gblock;
 872
 873         if ( j->ntype!=nJunction ) return j;
 874         gblock = first_item_is_guess_block((Junction *)j);
 875
 876         if ( gblock!=NULL )
 877         {
 878                 Junction *past = gblock->end;
 879                 Junction *p;
 880                 require(past!=NULL, "analysis_point: no end block on (...)? block");
 881
 882                 for (p=(Junction *)past->p1; p!=NULL; )
 883                 {
 884                         if ( p->ntype==nAction )
 885                         {
 886                                 p=(Junction *)((ActionNode *)p)->next;
 887                                 continue;
 888                         }
 889                         if ( p->ntype!=nJunction )
 890                         {
 891                                 return (Junction *)past->p1;
 892                         }
 893                         if ( p->jtype==EndBlk || p->jtype==EndRule )
 894                         {
 895                                 return j;
 896                         }
 897                         p=(Junction *)p->p1;
 898                 }
 899         }
 900         return j;
 901 }
 902
 903 set
 904 #ifdef __STDC__
 905 First( Junction *j, int k, int jtype, int *max_k )
 906 #else
 907 First( j, k, jtype, max_k )
 908 Junction *j;
 909 int k;
 910 int jtype;
 911 int *max_k;
 912 #endif
 913 {
 914         Junction *alt1, *alt2;
 915         set a, rk, fCurBlk;
 916         int savek;
 917         int p1, p2;
 918         require(j->ntype==nJunction, "First: non junction passed");
 919
 920         /* C o m p u t e  F I R S T  s e t  w i t h  k  l o o k a h e a d */
 921         fCurBlk = rk = empty;
 922         for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2)
 923         {
 924                 Junction *p = analysis_point((Junction *)alt1->p1);
 925                 REACH(p, k, &rk, alt1->fset[k]);
 926                 require(set_nil(rk), "rk != nil");
 927                 set_free(rk);
 928                 set_orin(&fCurBlk, alt1->fset[k]);
 929         }
 930
 931         /* D e t e c t  A m b i g u i t i e s */
 932         *max_k = 1;
 933         for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)
 934         {
 935                 for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)
 936                 {
 937                         savek = k;
 938                         a = set_and(alt1->fset[k], alt2->fset[k]);
 939                         while ( !set_nil(a) )
 940                         {
 941                                 /* if we have hit the max k requested, just give warning */
 942                                 if ( j->approx==k ) {
 943                                 }
 944
 945                                 if ( k==CLL_k )
 946                                 {
 947 #ifdef NOT_USED
 948                                         int save_LL_k = LL_k;
 949                                         int save_CLL_k = CLL_k;
 950                                         /* Get new LL_k from interactive feature if enabled */
 951                                         if ( AImode )
 952                                                 AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);
 953 #endif
 954                                         *max_k = CLL_k;
 955                                         HandleAmbiguity(j, alt1, alt2, jtype);
 956                                         break;
 957                                 }
 958                                 else
 959                                 {
 960                                         Junction *p = analysis_point((Junction *)alt1->p1);
 961                                         Junction *q = analysis_point((Junction *)alt2->p1);
 962                                         k++;    /* attempt ambig alts again with more lookahead */
 963                                         REACH(p, k, &rk, alt1->fset[k]);
 964                                         require(set_nil(rk), "rk != nil");
 965                                         REACH(q, k, &rk, alt2->fset[k]);
 966                                         require(set_nil(rk), "rk != nil");
 967                                         set_free(a);
 968                                         a = set_and(alt1->fset[k], alt2->fset[k]);
 969                                         if ( k > *max_k ) *max_k = k;
 970                                 }
 971                         }
 972                         set_free(a);
 973                         k = savek;
 974                 }
 975         }
 976
 977         return fCurBlk;
 978 }