1 /* 2 * fset.c 3 * 4 * Compute FIRST and FOLLOW sets. 5 * 6 * SOFTWARE RIGHTS 7 * 8 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool 9 * Set (PCCTS) -- PCCTS is in the public domain. An individual or 10 * company may do whatever they wish with source code distributed with 11 * PCCTS or the code generated by PCCTS, including the incorporation of 12 * PCCTS, or its output, into commerical software. 13 * 14 * We encourage users to develop software with PCCTS. However, we do ask 15 * that credit is given to us for developing PCCTS. By "credit", 16 * we mean that if you incorporate our source code into one of your 17 * programs (commercial product, research project, or otherwise) that you 18 * acknowledge this fact somewhere in the documentation, research report, 19 * etc... If you like PCCTS and have developed a nice tool with the 20 * output, please mention that you developed it using PCCTS. In 21 * addition, we ask that this header remain intact in our source code. 22 * As long as these guidelines are kept, we expect to continue enhancing 23 * this system and expect to make other tools available as they are 24 * completed. 25 * 26 * ANTLR 1.33 27 * Terence Parr 28 * Parr Research Corporation 29 * with Purdue University and AHPCRC, University of Minnesota 30 * 1989-2001 31 */ 32 33 #include <stdio.h> 34 #include <stdlib.h> 35 36 #include "pcctscfg.h" 37 38 #include "set.h" 39 #include "syn.h" 40 #include "hash.h" 41 #include "generic.h" 42 #include "dlgdef.h" 43 #include "limits.h" 44 45 #ifdef __USE_PROTOS 46 static void ensure_predicates_cover_ambiguous_lookahead_sequences 47 (Junction *, Junction *, char *, Tree *); 48 #else 49 static void ensure_predicates_cover_ambiguous_lookahead_sequences(); 50 #endif 51 52 /* 53 * What tokens are k tokens away from junction q? 54 * 55 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this 56 * node. 57 * We lock the junction according to k--the lookahead. If we have been at this 58 * junction before looking for the same, k, number of lookahead tokens, we will 59 * do it again and again...until we blow up the stack. Locks are only used on aLoopBlk, 60 * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from 61 * FIRST and FOLLOW calcs. 62 * 63 * If p->jtype == EndRule we are going to attempt a FOLLOW. (FOLLOWs are really defined 64 * in terms of FIRST's, however). To proceed with the FOLLOW, p->halt cannot be 65 * set. p->halt is set to indicate that a reference to the current rule is in progress 66 * and the FOLLOW is not desirable. 67 * 68 * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule 69 * junction yields an empty set, replace the empty set with EOF. No FOLLOW means that 70 * only EOF can follow the current rule. This normally occurs only on the start symbol 71 * since all other rules are referenced by another rule somewhere. 72 * 73 * Normally, both p1 and p2 are followed. However, checking p2 on a RuleBlk node is 74 * the same as checking the next rule which is clearly incorrect. 75 * 76 * Cycles in the FOLLOW sense are possible. e.g. Fo(c) requires Fo(b) which requires 77 * Fo(c). Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c). Let's say 78 * Fo(c) is attempted first. It finds all of the FOLLOW symbols and then attempts 79 * to do Fo(b) which finds of its FOLLOW symbols. So, we have: 80 * 81 * Fo(c) 82 * / \ 83 * a set Fo(b) 84 * / \ 85 * a set Fo(c) .....Hmmmm..... Infinite recursion! 86 * 87 * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now 88 * correctly Fo(c) union Fo(b). We wish to pick up where we left off, so the fact 89 * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already 90 * laying around. SOOOOoooo, we track FOLLOW cycles. All FOLLOW computations are 91 * cached in a hash table. After the sequence of FOLLOWs finish, we reconcile all 92 * cycles --> correct all Fo(rule) sets in the cache. 93 * 94 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30]. 95 * TJP 8/93 -- can now read PhD thesis from Purdue. 96 * 97 * Also, FIRST sets are cached in the hash table. Keys are (rulename,Fi/Fo,k). 98 * Only FIRST sets, for which the FOLLOW is not included, are stored. 99 * 100 * SPECIAL CASE of (...)+ blocks: 101 * I added an optional alt so that the alts could see what 102 * was behind the (...)+ block--thus using enough lookahead 103 * to branch out rather than just enough to distinguish 104 * between alts in the (...)+. However, when the FIRST("(...)+") is 105 * is needed, must not use this last "optional" alt. This routine 106 * turns off this path by setting a new 'ignore' flag for 107 * the alt and then resetting it afterwards. 108 */ 109 110 set 111 #ifdef __USE_PROTOS 112 rJunc( Junction *p, int k, set *rk ) 113 #else 114 rJunc( p, k, rk ) 115 Junction *p; 116 int k; 117 set *rk; 118 #endif 119 { 120 set a, b; 121 122 require(p!=NULL, "rJunc: NULL node"); 123 require(p->ntype==nJunction, "rJunc: not junction"); 124 125 #ifdef DBG_LL1 126 if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k); 127 else fprintf(stderr, "rJunc: %s in rule %s\n", 128 decodeJType[p->jtype], ((Junction *)p)->rname); 129 #endif 130 /* if this is one of the added optional alts for (...)+ then return */ 131 132 /* no need to pop backtrace - hasn't been pushed */ 133 134 if ( p->ignore ) return empty; 135 136 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); 137 138 /* MR14 */ if (AlphaBetaTrace && p->alpha_beta_guess_end) { 139 /* MR14 */ warnFL( 140 /* MR14 */ "not possible to compute follow set for alpha in an \"(alpha)? beta\" block. ", 141 /* MR14 */ FileStr[p->file],p->line); 142 /* MR14 */ MR_alphaBetaTraceReport(); 143 /* MR14 */ }; 144 145 /* MR14 */ if (p->alpha_beta_guess_end) { 146 /* MR14 */ if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 147 /* MR14 */ return empty; 148 /* MR14 */ } 149 150 /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */ 151 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || 152 p->jtype==aPlusBlk || p->jtype==EndRule ) 153 { 154 require(p->lock!=NULL, "rJunc: lock array is NULL"); 155 if ( p->lock[k] ) 156 { 157 if ( p->jtype == EndRule ) /* FOLLOW cycle? */ 158 { 159 #ifdef DBG_LL1 160 fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname); 161 #endif 162 if (! MR_AmbSourceSearch) RegisterCycle(p->rname, k); 163 } 164 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 165 return empty; 166 } 167 if ( p->jtype == RuleBlk && 168 p->end->halt && 169 ! MR_AmbSourceSearch) /* check for FIRST cache */ 170 { 171 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k)); 172 if ( q != NULL ) 173 { 174 set_orin(rk, q->rk); 175 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 176 return set_dup( q->fset ); 177 } 178 } 179 if ( p->jtype == EndRule && 180 !p->halt && /* MR11 was using cache even when halt set */ 181 ! MR_AmbSourceSearch) /* FOLLOW set cached already? */ 182 { 183 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k)); 184 if ( q != NULL ) 185 { 186 #ifdef DBG_LL1 187 fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k); 188 s_fprT(stderr, q->fset); 189 if ( q->incomplete ) fprintf(stderr, " (incomplete)"); 190 fprintf(stderr, "\n"); 191 #endif 192 if ( !q->incomplete ) 193 { 194 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 195 return set_dup( q->fset ); 196 } 197 } 198 } 199 p->lock[k] = TRUE; /* This rule is busy */ 200 } 201 202 a = b = empty; 203 204 if ( p->jtype == EndRule ) 205 { 206 if (p->halt ) /* don't want FOLLOW here? */ /* unless MR10 hoisting */ 207 { 208 p->lock[k] = FALSE; 209 set_orel(k, rk); /* indicate this k value needed */ 210 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 211 return empty; 212 } 213 if (! MR_AmbSourceSearch) FoPush(p->rname, k); /* Attempting FOLLOW */ 214 if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */ 215 #ifdef DBG_LL1 216 fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k); 217 #endif 218 } 219 220 if ( p->p1 != NULL ) { 221 /* MR14 */ if (p->guess) { 222 /* MR14 */ if (p->guess_analysis_point == NULL) { 223 /* MR14 */ Node * guess_point; 224 /* MR14 */ guess_point=(Node *)analysis_point(p); 225 /* MR14 */ if (guess_point == (Node *)p) { 226 /* MR14 */ guess_point=p->p1; 227 /* MR14 */ } 228 /* MR14 */ p->guess_analysis_point=guess_point; 229 /* MR14 */ } 230 /* MR14 */ REACH(p->guess_analysis_point, k, rk, a); 231 } else { 232 REACH(p->p1, k, rk, a); 233 } 234 } 235 236 /* C a c h e R e s u l t s */ 237 238 if ( p->jtype == RuleBlk && p->end->halt && ! MR_AmbSourceSearch) /* can save FIRST set? */ 239 { 240 CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) ); 241 /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/ 242 hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q); 243 q->fset = set_dup( a ); 244 q->rk = set_dup( *rk ); 245 } 246 247 if ( p->jtype == EndRule && 248 !p->halt && /* MR11 was using cache even with halt set */ 249 ! MR_AmbSourceSearch) /* just completed FOLLOW? */ 250 { 251 /* Cache Follow set */ 252 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k)); 253 if ( q==NULL ) 254 { 255 q = newCacheEntry( Fkey(p->rname,'o',k) ); 256 hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q); 257 } 258 /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/ 259 if ( set_nil(a) && !q->incomplete ) 260 { 261 /* Don't ever save a nil set as complete. 262 * Turn it into an eof set. 263 */ 264 set_orel(EofToken, &a); 265 } 266 set_orin(&(q->fset), a); 267 FoPop( k ); 268 if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k); 269 #ifdef DBG_LL1 270 fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k); 271 s_fprT(stderr, q->fset); 272 if ( q->incomplete ) fprintf(stderr, " (incomplete)"); 273 fprintf(stderr, "\n"); 274 #endif 275 } 276 277 if (p->jtype != RuleBlk && p->p2 != NULL && /* MR14 */ ! p->guess) { 278 REACH(p->p2, k, rk, b); 279 } 280 281 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || 282 p->jtype==aPlusBlk || p->jtype==EndRule ) 283 p->lock[k] = FALSE; /* unlock node */ 284 285 set_orin(&a, b); 286 set_free(b); 287 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 288 return a; 289 } 290 291 set 292 #ifdef __USE_PROTOS 293 rRuleRef( RuleRefNode *p, int k, set *rk_out ) 294 #else 295 rRuleRef( p, k, rk_out ) 296 RuleRefNode *p; 297 int k; 298 set *rk_out; 299 #endif 300 { 301 set rk; 302 Junction *r; 303 int k2; 304 set a, rk2, b; 305 int save_halt; 306 RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text); 307 require(p!=NULL, "rRuleRef: NULL node"); 308 require(p->ntype==nRuleRef, "rRuleRef: not rule ref"); 309 310 #ifdef DBG_LL1 311 fprintf(stderr, "rRuleRef: %s\n", p->text); 312 #endif 313 314 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); 315 316 if ( q == NULL ) 317 { 318 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line ); 319 REACH(p->next, k, rk_out, a); 320 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 321 return a; 322 } 323 rk2 = empty; 324 325 /* MR9 Problems with rule references in guarded predicates */ 326 /* MR9 Perhaps can use hash table to find rule ? */ 327 328 /* MR9 */ if (RulePtr == NULL) { 329 /* MR9 */ fatalFL(eMsg2("Rule %s uses rule %s via RulePtr before it has been initialized", 330 /* MR9 */ p->rname,q->str),FileStr[p->file],p->line); 331 /* MR9 */ }; 332 333 r = RulePtr[q->rulenum]; 334 if ( r->lock[k] ) 335 { 336 errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s", 337 r->rname, p->rname) ); 338 339 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 340 341 return empty; 342 } 343 344 save_halt = r->end->halt; 345 r->end->halt = TRUE; /* don't let reach fall off end of rule here */ 346 rk = empty; 347 REACH(r, k, &rk, a); 348 r->end->halt = save_halt; 349 while ( !set_nil(rk) ) { 350 k2 = set_int(rk); /* MR11 this messes up the ambiguity search routine */ 351 set_rm(k2, rk); 352 REACH(p->next, k2, &rk2, b); /* MR11 by changing the value of k */ 353 set_orin(&a, b); 354 set_free(b); 355 } 356 set_free(rk); /* this has no members, but free it's memory */ 357 set_orin(rk_out, rk2); /* remember what we couldn't do */ 358 set_free(rk2); 359 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 360 return a; 361 } 362 363 /* 364 * Return FIRST sub k ( token_node ) 365 * 366 * TJP 10/11/93 modified this so that token nodes that are actually 367 * ranges (T1..T2) work. 368 */ 369 set 370 #ifdef __USE_PROTOS 371 rToken( TokNode *p, int k, set *rk ) 372 #else 373 rToken( p, k, rk ) 374 TokNode *p; 375 int k; 376 set *rk; 377 #endif 378 { 379 set a; 380 381 require(p!=NULL, "rToken: NULL node"); 382 require(p->ntype==nToken, "rToken: not token node"); 383 384 #ifdef DBG_LL1 385 fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token): 386 ExprString(p->token)); 387 #endif 388 389 390 if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); 391 392 if (MR_AmbSourceSearch && (k-1) == 0) { 393 394 set localConstrain; 395 set intersection; 396 397 localConstrain=fset[maxk-k+1]; 398 399 if (! set_nil(p->tset)) { 400 intersection=set_and(localConstrain,p->tset); 401 if (! set_nil(intersection)) { 402 MR_backTraceReport(); 403 }; 404 set_free(intersection); 405 } else { 406 if (set_el( (unsigned) p->token,localConstrain)) { 407 MR_backTraceReport(); 408 } 409 }; 410 }; 411 412 if ( k-1 == 0 ) { 413 414 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 415 416 if ( !set_nil(p->tset) ) { 417 return set_dup(p->tset); 418 } else { 419 return set_of(p->token); 420 }; 421 } 422 423 REACH(p->next, k-1, rk, a); 424 425 if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); 426 427 return a; 428 } 429 430 set 431 #ifdef __USE_PROTOS 432 rAction( ActionNode *p, int k, set *rk ) 433 #else 434 rAction( p, k, rk ) 435 ActionNode *p; 436 int k; 437 set *rk; 438 #endif 439 { 440 set a; 441 442 require(p!=NULL, "rJunc: NULL node"); 443 require(p->ntype==nAction, "rJunc: not action"); 444 445 /* MR11 */ if (p->is_predicate && p->ampersandPred != NULL) { 446 /* MR11 */ Predicate *pred=p->ampersandPred; 447 /* MR11 */ if (k <= pred->k) { 448 /* MR11 */ REACH(p->guardNodes,k,rk,a); 449 /* MR11 */ return a; 450 /* MR11 */ }; 451 /* MR11 */ }; 452 453 /* it might be a good idea when doing an MR_AmbSourceSearch 454 to *not* look behind predicates under some circumstances 455 we'll look into that later 456 */ 457 458 REACH(p->next, k, rk, a); /* ignore actions */ 459 return a; 460 } 461 462 /* A m b i g u i t y R e s o l u t i o n */ 463 464 465 void 466 #ifdef __USE_PROTOS 467 dumpAmbigMsg( set *fset, FILE *f, int want_nls ) 468 #else 469 dumpAmbigMsg( fset, f, want_nls ) 470 set *fset; 471 FILE *f; 472 int want_nls; 473 #endif 474 { 475 int i; 476 477 set copy; /* MR11 */ 478 479 if ( want_nls ) fprintf(f, "\n\t"); 480 else fprintf(f, " "); 481 482 for (i=1; i<=CLL_k; i++) 483 { 484 copy=set_dup(fset[i]); /* MR11 */ 485 486 if ( i>1 ) 487 { 488 if ( !want_nls ) fprintf(f, ", "); 489 } 490 if ( set_deg(copy) > 3 && elevel == 1 ) 491 { 492 int e,m; 493 fprintf(f, "{"); 494 for (m=1; m<=3; m++) 495 { 496 e=set_int(copy); 497 fprintf(f, " %s", TerminalString(e)); 498 set_rm(e, copy); 499 } 500 fprintf(f, " ... }"); 501 } 502 else s_fprT(f, copy); 503 if ( want_nls ) fprintf(f, "\n\t"); 504 set_free(copy); 505 } 506 fprintf(f, "\n"); 507 508 } 509 510 static void 511 #ifdef __USE_PROTOS 512 verify_context(Predicate *predicate) 513 #else 514 verify_context(predicate) 515 Predicate *predicate; 516 #endif 517 { 518 if ( predicate == NULL ) return; 519 520 if ( predicate->expr == PRED_OR_LIST || 521 predicate->expr == PRED_AND_LIST ) 522 { 523 verify_context(predicate->down); 524 verify_context(predicate->right); /* MR10 */ 525 return; 526 } 527 528 if ( !predicate->source->ctxwarned && predicate->source->guardpred==NULL && 529 ((predicate->k > 1 && 530 !is_single_tuple(predicate->tcontext)) || 531 ( predicate->k == 1 && 532 set_deg(predicate->scontext[1])>1 )) ) 533 { 534 535 /* MR9 Suppress annoying messages caused by our own clever(?) fix */ 536 537 fprintf(stderr, ErrHdr, FileStr[predicate->source->file], 538 predicate->source->line); 539 fprintf(stderr, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate->k); 540 fprintf(stderr, ErrHdr, FileStr[predicate->source->file], 541 predicate->source->line); 542 fprintf(stderr, " predicate text: \"%s\"\n", 543 (predicate->expr == NULL ? "(null)" : predicate->expr) ); 544 fprintf(stderr, ErrHdr, FileStr[predicate->source->file], 545 predicate->source->line); 546 fprintf(stderr, " You may only want one lookahead %d-sequence to apply\n", predicate->k); 547 fprintf(stderr, ErrHdr, FileStr[predicate->source->file], 548 predicate->source->line); 549 fprintf(stderr, " Try using a context guard '(...)? =>'\n"); 550 predicate->source->ctxwarned = 1; 551 } 552 verify_context(predicate->right); /* MR10 */ 553 } 554 555 /* 556 * If delta is the set of ambiguous lookahead sequences, then make sure that 557 * the predicate(s) for productions alt1,alt2 cover the sequences in delta. 558 * 559 * For example, 560 * a : <<PRED1>>? (A B|A C) 561 * | b 562 * ; 563 * b : <<PRED2>>? A B 564 * | A C 565 * ; 566 * 567 * This should give a warning that (A C) predicts both productions and alt2 568 * does not have a predicate in the production that generates (A C). 569 * 570 * The warning detection is simple. Let delta = LOOK(alt1) intersection LOOK(alt2). 571 * Now, if ( delta set-difference context(predicates-for-alt1) != empty then 572 * alt1 does not "cover" all ambiguous sequences. 573 * 574 * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset 575 * info. Actually, sets are used only if k=1 for this grammar. 576 */ 577 static void 578 #ifdef __USE_PROTOS 579 ensure_predicates_cover_ambiguous_lookahead_sequences 580 ( Junction *alt1, Junction *alt2, char *sub, Tree *ambig ) 581 #else 582 ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig ) 583 Junction *alt1; 584 Junction *alt2; 585 char *sub; 586 Tree *ambig; 587 #endif 588 { 589 if ( !ParseWithPredicates ) return; 590 591 if ( ambig!=NULL ) 592 { 593 Tree *non_covered = NULL; 594 if ( alt1->predicate!=NULL ) 595 non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset); 596 if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 ) 597 { 598 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 599 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", 600 alt1->altnum, sub); 601 if ( alt1->predicate!=NULL && non_covered!=NULL ) 602 { 603 fprintf(stderr, " upon"); 604 preorder(non_covered); 605 } 606 else if ( alt1->predicate==NULL ) 607 { 608 fprintf(stderr, " upon"); 609 preorder(ambig->down); 610 } 611 fprintf(stderr, "\n"); 612 } 613 Tfree(non_covered); 614 non_covered = NULL; 615 if ( alt2->predicate!=NULL ) 616 non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset); 617 if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 ) 618 { 619 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line); 620 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", 621 alt2->altnum, sub); 622 if ( alt2->predicate!=NULL && non_covered!=NULL ) 623 { 624 fprintf(stderr, " upon"); 625 preorder(non_covered); 626 } 627 else if ( alt2->predicate==NULL ) 628 { 629 fprintf(stderr, " upon"); 630 preorder(ambig->down); 631 } 632 fprintf(stderr, "\n"); 633 } 634 Tfree(non_covered); 635 } 636 else if ( !set_nil(alt1->fset[1]) ) 637 { 638 set delta, non_covered; 639 delta = set_and(alt1->fset[1], alt2->fset[1]); 640 non_covered = set_dif(delta, covered_set(alt1->predicate)); 641 if ( set_deg(non_covered)>0 && WarningLevel>1 ) 642 { 643 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 644 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", 645 alt1->altnum, sub); 646 if ( alt1->predicate!=NULL ) 647 { 648 fprintf(stderr, " upon "); 649 s_fprT(stderr, non_covered); 650 } 651 fprintf(stderr, "\n"); 652 } 653 set_free( non_covered ); 654 non_covered = set_dif(delta, covered_set(alt2->predicate)); 655 if ( set_deg(non_covered)>0 && WarningLevel>1 ) 656 { 657 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line); 658 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", 659 alt2->altnum, sub); 660 if ( alt2->predicate!=NULL ) 661 { 662 fprintf(stderr, " upon "); 663 s_fprT(stderr, non_covered); 664 } 665 fprintf(stderr, "\n"); 666 } 667 set_free( non_covered ); 668 set_free( delta ); 669 } 670 else fatal_internal("productions have no lookahead in predicate checking routine"); 671 } 672 673 #ifdef __USE_PROTOS 674 void MR_doPredicatesHelp(int inGuessBlock,Junction *alt1,Junction *alt2,int jtype,char *sub) 675 #else 676 void MR_doPredicatesHelp(inGuessBlock,alt1,alt2,jtype,sub) 677 int inGuessBlock; 678 Junction *alt1; 679 Junction *alt2; 680 int jtype; 681 char *sub; 682 #endif 683 { 684 Predicate *p1; 685 Predicate *p2; 686 687 Junction *parentRule=MR_nameToRuleBlk(alt1->rname); 688 689 if (inGuessBlock && WarningLevel <= 1) return; 690 691 /* let antlr give the usual error message */ 692 693 if (alt1->predicate == NULL && alt2->predicate == NULL) return; 694 695 if ( (jtype == RuleBlk || jtype == aSubBlk) 696 && (alt1->predicate == NULL && alt2->predicate != NULL)) { 697 fprintf(stderr, ErrHdr, FileStr[parentRule->file],parentRule->line); 698 fprintf(stderr," warning: alt %d line %d and alt %d line %d of %s\n%s%s%s", 699 alt1->altnum, 700 alt1->line, 701 alt2->altnum, 702 alt2->line, 703 sub, 704 " These alts have ambig lookahead sequences resolved by a predicate for\n", 705 " the second choice. The second choice may not be reachable.\n", 706 " You may want to use a complementary predicate or rearrange the alts\n" 707 ); 708 return; 709 }; 710 711 /* first do the easy comparison. then do the hard one */ 712 713 if (MR_comparePredicates(alt1->predicate,alt2->predicate)) { 714 715 if (jtype == aLoopBegin || jtype == aPlusBlk ) { 716 717 /* I'm not sure this code is reachable. 718 Predicates following a (...)+ or (...)* block are probably 719 considered validation predicates and therefore not 720 participate in the predication expression 721 */ 722 723 fprintf(stderr, ErrHdr,FileStr[parentRule->file],parentRule->line); 724 fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s", 725 "the predicates used to disambiguate optional/exit paths of ", 726 sub, 727 CurRule, 728 FileStr[alt1->file], 729 alt1->altnum, 730 alt1->line, 731 alt2->altnum, 732 alt2->line, 733 " are identical and have no resolving power\n"); 734 } else { 735 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); 736 fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s", 737 "the predicates used to disambiguate", 738 CurRule, 739 FileStr[alt1->file], 740 alt1->altnum, 741 alt1->line, 742 alt2->altnum, 743 alt2->line, 744 " are identical and have no resolving power\n"); 745 }; 746 } else { 747 p1=predicate_dup_without_context(alt1->predicate); 748 p1=MR_unfold(p1); 749 MR_clearPredEntry(p1); 750 MR_simplifyInverted(p1,0); 751 p1=MR_predSimplifyALL(p1); 752 p2=predicate_dup_without_context(alt2->predicate); 753 p2=MR_unfold(p2); 754 MR_clearPredEntry(p2); 755 MR_simplifyInverted(p2,0); 756 p2=MR_predSimplifyALL(p2); 757 if (MR_comparePredicates(p1,p2)) { 758 if (jtype == aLoopBegin || jtype == aPlusBlk ) { 759 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); 760 fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", 761 "the predicates used to disambiguate optional/exit paths of ", 762 sub, 763 CurRule, 764 FileStr[alt1->file], 765 alt1->altnum, 766 alt1->line, 767 alt2->altnum, 768 alt2->line, 769 " are identical when compared without context and may have no\n", 770 " resolving power for some lookahead sequences.\n"); 771 } else { 772 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); 773 fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", 774 "the predicates used to disambiguate", 775 CurRule, 776 FileStr[alt1->file], 777 alt1->altnum, 778 alt1->line, 779 alt2->altnum, 780 alt2->line, 781 " are identical when compared without context and may have no\n", 782 " resolving power for some lookahead sequences.\n"); 783 }; 784 if (InfoP) { 785 fprintf(output,"\n#if 0\n\n"); 786 fprintf(output,"The following predicates are identical when compared without\n"); 787 fprintf(output," lookahead context information. For some ambiguous lookahead\n"); 788 fprintf(output," sequences they may not have any power to resolve the ambiguity.\n"); 789 fprintf(output,"\n"); 790 791 fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n", 792 MR_ruleNamePlusOffset( (Node *) alt1), 793 alt1->altnum, 794 alt1->line, 795 FileStr[alt1->file]); 796 fprintf(output," The original predicate for choice 1 with available context information:\n\n"); 797 MR_dumpPred1(2,alt1->predicate,1); 798 fprintf(output," The predicate for choice 1 after expansion (but without context information):\n\n"); 799 MR_dumpPred1(2,p1,0); 800 if (p1 == NULL) { 801 Predicate *phelp; 802 fprintf(output," The predicate for choice 1 after expansion (but before simplification)\n\n"); 803 phelp=predicate_dup_without_context(alt1->predicate); 804 phelp=MR_unfold(phelp); 805 MR_clearPredEntry(phelp); 806 MR_simplifyInverted(phelp,0); 807 phelp=MR_predSimplifyALLX(phelp,1); 808 MR_dumpPred1(2,phelp,0); 809 predicate_free(phelp); 810 }; 811 fprintf(output,"\n"); 812 813 fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n", 814 MR_ruleNamePlusOffset( (Node *) alt2), 815 alt2->altnum, 816 alt2->line, 817 FileStr[alt2->file]); 818 fprintf(output," The original predicate for choice 2 with available context information:\n\n"); 819 MR_dumpPred1(1,alt2->predicate,1); 820 fprintf(output," The predicate for choice 2 after expansion (but without context information):\n\n"); 821 MR_dumpPred1(1,p2,0); 822 if (p2 == NULL) { 823 Predicate *phelp; 824 fprintf(output," The predicate for choice 2 after expansion (but before simplification)\n\n"); 825 phelp=predicate_dup_without_context(alt2->predicate); 826 phelp=MR_unfold(phelp); 827 MR_clearPredEntry(phelp); 828 MR_simplifyInverted(phelp,0); 829 phelp=MR_predSimplifyALLX(phelp,1); 830 MR_dumpPred1(2,phelp,0); 831 predicate_free(phelp); 832 }; 833 fprintf(output,"\n#endif\n"); 834 }; 835 } else if (MR_secondPredicateUnreachable(p1,p2)) { 836 if (jtype == aLoopBegin || jtype == aPlusBlk ) { 837 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); 838 fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", 839 "the predicate used to disambiguate the first choice of the optional/exit paths of ", 840 sub, 841 CurRule, 842 FileStr[alt1->file], 843 alt1->altnum, 844 alt1->line, 845 alt2->altnum, 846 alt2->line, 847 " appears to \"cover\" the second predicate when compared without context.\n", 848 " The second predicate may have no resolving power for some lookahead sequences.\n"); 849 } else { 850 fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); 851 fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", 852 "the predicate used to disambiguate the first choice of", 853 CurRule, 854 FileStr[alt1->file], 855 alt1->altnum, 856 alt1->line, 857 alt2->altnum, 858 alt2->line, 859 " appears to \"cover\" the second predicate when compared without context.\n", 860 " The second predicate may have no resolving power for some lookahead sequences.\n"); 861 }; 862 if (InfoP) { 863 fprintf(output,"\n#if 0\n\n"); 864 fprintf(output,"The first predicate appears to \"cover\" the second predicate when they\n"); 865 fprintf(output," are compared without lookahead context information. For some ambiguous\n"); 866 fprintf(output," lookahead sequences the second predicate may not have any power to\n"); 867 fprintf(output," resolve the ambiguity.\n"); 868 fprintf(output,"\n"); 869 fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n", 870 MR_ruleNamePlusOffset( (Node *) alt1), 871 alt1->altnum, 872 alt1->line, 873 FileStr[alt1->file]); 874 fprintf(output," The original predicate for choice 1 with available context information:\n\n"); 875 MR_dumpPred1(2,alt1->predicate,1); 876 fprintf(output," The predicate for choice 1 after expansion (but without context information):\n\n"); 877 MR_dumpPred1(2,p1,0); 878 if (p1 == NULL) { 879 Predicate *phelp; 880 fprintf(output," The predicate for choice 1 after expansion (but before simplification)\n\n"); 881 phelp=predicate_dup_without_context(alt1->predicate); 882 phelp=MR_unfold(phelp); 883 MR_clearPredEntry(phelp); 884 MR_simplifyInverted(phelp,0); 885 phelp=MR_predSimplifyALLX(phelp,1); 886 MR_dumpPred1(2,phelp,0); 887 predicate_free(phelp); 888 }; 889 fprintf(output,"\n"); 890 891 fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n", 892 MR_ruleNamePlusOffset( (Node *) alt2), 893 alt2->altnum, 894 alt2->line, 895 FileStr[alt2->file]); 896 fprintf(output," The original predicate for choice 2 with available context information:\n\n"); 897 MR_dumpPred1(1,alt2->predicate,1); 898 fprintf(output," The predicate for choice 2 after expansion (but without context information):\n\n"); 899 MR_dumpPred1(1,p2,0); 900 if (p2 == NULL) { 901 Predicate *phelp; 902 fprintf(output," The predicate for choice 2 after expansion (but before simplification)\n\n"); 903 phelp=predicate_dup_without_context(alt2->predicate); 904 phelp=MR_unfold(phelp); 905 MR_clearPredEntry(phelp); 906 MR_simplifyInverted(phelp,0); 907 phelp=MR_predSimplifyALLX(phelp,1); 908 MR_dumpPred1(2,phelp,0); 909 predicate_free(phelp); 910 }; 911 fprintf(output,"\n#endif\n"); 912 }; 913 }; 914 predicate_free(p1); 915 predicate_free(p2); 916 }; 917 } 918 919 static int totalOverflow=0; /* MR9 */ 920 921 void 922 #ifdef __USE_PROTOS 923 HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype ) 924 #else 925 HandleAmbiguity( block, alt1, alt2, jtype ) 926 Junction *block; 927 Junction *alt1; 928 Junction *alt2; 929 int jtype; 930 #endif 931 { 932 unsigned **ftbl; 933 set *fset, b; 934 int i, numAmbig,n2; 935 Tree *ambig=NULL, *t, *u; 936 char *sub = ""; 937 long n; 938 int thisOverflow=0; /* MR9 */ 939 long set_deg_value; /* MR10 */ 940 long threshhold; /* MR10 */ 941 942 require(block!=NULL, "NULL block"); 943 require(block->ntype==nJunction, "invalid block"); 944 945 /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */ 946 fset = (set *) calloc(CLL_k+1, sizeof(set)); 947 require(fset!=NULL, "cannot allocate fset"); 948 ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *)); 949 require(ftbl!=NULL, "cannot allocate ftbl"); 950 951 /* create constraint table and count number of possible ambiguities (use<=LL_k) */ 952 for (n=1,i=1; i<=CLL_k; i++) 953 { 954 b = set_and(alt1->fset[i], alt2->fset[i]); 955 /* MR9 */ set_deg_value = set_deg(b); 956 /* MR10 */ if (n > 0) { 957 /* MR10 */ threshhold = LONG_MAX / n; 958 /* MR10 */ if (set_deg_value <= threshhold) { 959 /* MR10 */ n *= set_deg_value; 960 /* MR10 */ } else { 961 /* MR10 */ n=LONG_MAX; 962 /* MR9 */ if (totalOverflow == 0) { 963 #if 0 964 /* MR10 comment this out because it just makes users worry */ 965 966 /* MR9 */ warnNoFL("Overflow in computing number of possible ambiguities in HandleAmbiguity\n"); 967 #endif 968 /* MR9 */ }; 969 /* MR9 */ thisOverflow++; 970 /* MR9 */ totalOverflow++; 971 /* MR9 */ }; 972 /* MR10 */ } else { 973 /* MR10 */ n *= set_deg_value; 974 /* MR9 */ }; 975 fset[i] = set_dup(b); 976 ftbl[i] = set_pdq(b); 977 set_free(b); 978 } 979 980 switch ( jtype ) 981 { 982 case aSubBlk: sub = "of (..) "; break; 983 case aOptBlk: sub = "of {..} "; break; 984 case aLoopBegin: sub = "of (..)* "; break; 985 case aLoopBlk: sub = "of (..)* "; break; 986 case aPlusBlk: sub = "of (..)+ "; break; 987 case RuleBlk: sub = "of the rule itself "; break; 988 default : sub = ""; break; 989 } 990 991 /* If the block is marked as a compressed lookahead only block, then 992 * simply return; ambiguity warning is given only at warning level 2. 993 */ 994 if ( block->approx>0 ) 995 { 996 if ( ParseWithPredicates ) 997 { 998 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ 999 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ 1000 1001 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1002 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); 1003 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1004 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); 1005 alt1->predicate=MR_predSimplifyALL(alt1->predicate); 1006 1007 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1008 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); 1009 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1010 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); 1011 alt2->predicate=MR_predSimplifyALL(alt2->predicate); 1012 1013 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub); 1014 1015 if ( HoistPredicateContext 1016 && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) 1017 { 1018 verify_context(alt1->predicate); 1019 verify_context(alt2->predicate); 1020 } 1021 1022 if ( HoistPredicateContext 1023 && (alt1->predicate!=NULL||alt2->predicate!=NULL) 1024 && WarningLevel>1 ) 1025 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); 1026 } 1027 1028 if ( WarningLevel>1 ) 1029 { 1030 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 1031 if ( jtype == aLoopBegin || jtype == aPlusBlk ) 1032 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); 1033 else 1034 fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon", 1035 alt1->altnum, alt2->altnum, sub); 1036 dumpAmbigMsg(fset, stderr, 0); 1037 MR_traceAmbSource(fset,alt1,alt2); 1038 } 1039 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1040 free((char *)fset); 1041 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1042 free((char *)ftbl); 1043 return; 1044 } 1045 1046 /* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation; 1047 * don't bother doing full LL(k) analysis. 1048 * (This "if" block handles the LL(1) case) 1049 */ 1050 1051 n2 = 0; 1052 for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]); 1053 1054 /* here STARTS the special case in which the lookahead sets for alt1 and alt2 1055 all have degree 1 for k<LL_k (including LL_k=1) 1056 */ 1057 1058 if ( n2==2*(LL_k-1) ) 1059 { 1060 1061 /* TJP: added to fix the case where LL(1) and syntactic predicates didn't 1062 * work. It now recognizes syntactic predicates, but does not like combo: 1063 * LL(1)/syn/sem predicates. (10/24/93) 1064 */ 1065 1066 if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL ) 1067 { 1068 if ( WarningLevel==1 ) 1069 { 1070 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1071 free((char *)fset); 1072 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1073 free((char *)ftbl); 1074 return; 1075 } 1076 1077 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 1078 if ( jtype == aLoopBegin || jtype == aPlusBlk ) 1079 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); 1080 else 1081 fprintf(stderr, " warning: alts %d and %d %sambiguous upon", 1082 alt1->altnum, alt2->altnum, sub); 1083 dumpAmbigMsg(fset, stderr, 0); 1084 MR_traceAmbSource(fset,alt1,alt2); 1085 } 1086 1087 ambig = NULL; 1088 if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset); 1089 if ( ParseWithPredicates ) 1090 { 1091 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ 1092 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ 1093 1094 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1095 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); 1096 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1097 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); 1098 alt1->predicate=MR_predSimplifyALL(alt1->predicate); 1099 1100 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1101 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); 1102 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1103 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); 1104 alt2->predicate=MR_predSimplifyALL(alt2->predicate); 1105 1106 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub); 1107 1108 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) 1109 { 1110 verify_context(alt1->predicate); 1111 verify_context(alt2->predicate); 1112 } 1113 if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1) 1114 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); 1115 if ( WarningLevel == 1 && 1116 (alt1->predicate!=NULL||alt2->predicate!=NULL)) 1117 { 1118 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1119 free((char *)fset); 1120 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1121 free((char *)ftbl); 1122 Tfree(ambig); 1123 return; 1124 } 1125 } 1126 /* end TJP (10/24/93) */ 1127 1128 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 1129 if ( jtype == aLoopBegin || jtype == aPlusBlk ) 1130 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); 1131 else 1132 fprintf(stderr, " warning: alts %d and %d %sambiguous upon", 1133 alt1->altnum, alt2->altnum, sub); 1134 if ( elevel == 3 && LL_k>1 ) 1135 { 1136 preorder(ambig); 1137 fprintf(stderr, "\n"); 1138 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1139 free((char *)fset); 1140 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1141 free((char *)ftbl); 1142 Tfree(ambig); 1143 return; 1144 }; 1145 1146 Tfree(ambig); 1147 dumpAmbigMsg(fset, stderr, 0); 1148 1149 /* because this is a special case in which both alt1 and alt2 have 1150 lookahead sets of degree 1 for k<LL_k (including k=1) the linear 1151 lookahead style search is adequate 1152 */ 1153 1154 MR_traceAmbSource(fset,alt1,alt2); 1155 1156 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1157 free((char *)fset); 1158 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1159 free((char *)ftbl); 1160 return; 1161 } 1162 1163 /* here ENDS the special case in which the lookahead sets for alt1 and alt2 1164 all have degree 1 for k<LL_k (including LL_k=1) 1165 */ 1166 1167 /* in case tree construction runs out of memory, set info to make good err msg */ 1168 1169 CurAmbigAlt1 = alt1->altnum; 1170 CurAmbigAlt2 = alt2->altnum; 1171 CurAmbigbtype = sub; 1172 CurAmbigfile = alt1->file; 1173 CurAmbigline = alt1->line; 1174 1175 /* Don't do full LL(n) analysis if (...)? block because the block, 1176 by definition, defies LL(n) analysis. 1177 If guess (...)? block and ambiguous then don't remove anything from 1178 2nd alt to resolve ambig. 1179 Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block 1180 since it is much cheaper than LL(n). LL sup 1 ( n ) "covers" the LL(n) 1181 lookahead information. 1182 1183 Note: LL(n) context cannot be computed for semantic predicates when 1184 followed by (..)?. 1185 1186 If (..)? then we scream "AAAHHHH! No LL(n) analysis will help" 1187 1188 Is 'ambig' always defined if we enter this if? I hope so 1189 because the 'ensure...()' func references it. TJP Nov 1993. 1190 */ 1191 1192 /* THM MR30: Instead of using first_item_is_guss_block we use 1193 first_item_is_guess_block_extra which will look inside a 1194 loop block for a guess block. In other words ( (...)? )*. 1195 It there is an ambiguity in this circumstance then we suppress 1196 the normal methods of resolving ambiguities. 1197 */ 1198 1199 if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL ) 1200 { 1201 if ( ParseWithPredicates ) 1202 { 1203 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ 1204 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ 1205 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1206 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); 1207 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1208 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); 1209 alt1->predicate=MR_predSimplifyALL(alt1->predicate); 1210 1211 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1212 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); 1213 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1214 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); 1215 alt2->predicate=MR_predSimplifyALL(alt2->predicate); 1216 1217 MR_doPredicatesHelp(1,alt1,alt2,jtype,sub); 1218 1219 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) 1220 { 1221 verify_context(alt1->predicate); 1222 verify_context(alt2->predicate); 1223 } 1224 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) 1225 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); 1226 if ( WarningLevel==1 && 1227 (alt1->predicate!=NULL||alt2->predicate!=NULL)) 1228 { 1229 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1230 free((char *)fset); 1231 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1232 free((char *)ftbl); 1233 return; 1234 } 1235 } 1236 1237 if ( WarningLevel>1 ) 1238 { 1239 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 1240 if ( jtype == aLoopBegin || jtype == aPlusBlk ) 1241 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); 1242 else 1243 fprintf(stderr, " warning: alts %d and %d %sambiguous upon", 1244 alt1->altnum, alt2->altnum, sub); 1245 dumpAmbigMsg(fset, stderr, 0); 1246 MR_traceAmbSource(fset,alt1,alt2); 1247 } 1248 1249 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1250 free((char *)fset); 1251 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1252 free((char *)ftbl); 1253 return; 1254 } 1255 1256 /* Not resolved with (..)? block. Do full LL(n) analysis */ 1257 1258 /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */ 1259 /* MR11 VerifyAmbig once used fset destructively */ 1260 1261 ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig); 1262 1263 /* are all things in intersection really ambigs? */ 1264 1265 if (thisOverflow || numAmbig < n ) /* MR9 */ 1266 { 1267 Tree *v; 1268 1269 /* remove ambig permutation from 2nd alternative to resolve ambig; 1270 * We want to compute the set of artificial tuples, arising from 1271 * LL sup 1 (n) compression, that collide with real tuples from the 1272 * 2nd alternative. This is the set of "special case" tuples that 1273 * the LL sup 1 (n) decision template maps incorrectly. 1274 */ 1275 1276 /* when generating code in genExpr() it does 1277 * 1278 * if ( genExprSets(j->fset) && !genExprTree(j->ftree)) {... 1279 * 1280 * Sooooo the j->ftree is the tree of alt2 1281 * after removal of conflicts, not alt1 ! 1282 */ 1283 1284 if ( ambig!=NULL ) 1285 { 1286 /* at the top of ambig is an ALT node */ 1287 1288 for (v=ambig->down; v!=NULL; v=v->right) 1289 { 1290 u = trm_perm(u, v); /* remove v FROM u */ 1291 } 1292 /* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/ 1293 } 1294 Tfree( t ); 1295 alt1->ftree = tappend(alt1->ftree, u); 1296 alt1->ftree = tleft_factor(alt1->ftree); 1297 } 1298 1299 if ( ambig==NULL ) 1300 { 1301 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1302 free((char *)fset); 1303 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1304 free((char *)ftbl); 1305 return; 1306 } 1307 1308 ambig = tleft_factor(ambig); 1309 1310 /* TJP: 1311 * At this point, we surely have an LL(k) ambiguity. Check for predicates 1312 */ 1313 if ( ParseWithPredicates ) 1314 { 1315 if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ 1316 if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ 1317 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1318 alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); 1319 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1320 require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); 1321 alt1->predicate=MR_predSimplifyALL(alt1->predicate); 1322 1323 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1324 alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); 1325 require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); 1326 require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); 1327 alt2->predicate=MR_predSimplifyALL(alt2->predicate); 1328 1329 MR_doPredicatesHelp(0,alt1,alt2,jtype,sub); 1330 1331 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) 1332 { 1333 verify_context(alt1->predicate); 1334 verify_context(alt2->predicate); 1335 } 1336 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) 1337 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); 1338 if ( WarningLevel==1 && 1339 (alt1->predicate!=NULL||alt2->predicate!=NULL)) 1340 { 1341 1342 /* We found at least one pred for at least one of the alts; 1343 * If warnings are low, just return. 1344 */ 1345 1346 Tfree(ambig); 1347 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1348 free((char *)fset); 1349 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1350 free((char *)ftbl); 1351 return; 1352 } 1353 /* else we're gonna give a warning */ 1354 } 1355 /* end TJP addition */ 1356 1357 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); 1358 if ( jtype == aLoopBegin || jtype == aPlusBlk ) 1359 fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); 1360 else 1361 fprintf(stderr, " warning: alts %d and %d %sambiguous upon", 1362 alt1->altnum, alt2->altnum, sub); 1363 if ( elevel == 3 ) 1364 { 1365 preorder(ambig->down); /* <===== k>1 ambiguity message data */ 1366 fprintf(stderr, "\n"); 1367 } else { 1368 MR_skipped_e3_report=1; 1369 dumpAmbigMsg(fset, stderr, 0); 1370 }; 1371 1372 MR_traceAmbSourceK(ambig,alt1,alt2); /* <====== k>1 ambiguity aid */ 1373 1374 Tfree(ambig); 1375 1376 for (i=1; i<=CLL_k; i++) set_free( fset[i] ); 1377 free((char *)fset); 1378 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); 1379 free((char *)ftbl); 1380 } 1381 1382 /* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze 1383 * Return the 1st node of the beta block if present else return j. 1384 */ 1385 Junction * 1386 #ifdef __USE_PROTOS 1387 analysis_point( Junction *j ) 1388 #else 1389 analysis_point( j ) 1390 Junction *j; 1391 #endif 1392 { 1393 Junction *gblock; 1394 1395 /* MR13b When there was an action/predicate preceding a guess block 1396 the guess block became invisible at the analysis_point. 1397 1398 first_item_is_guess_block accepts any kind of node, 1399 despite the fact that the formal is a junction. But 1400 I don't want to have to change it all over the place 1401 until I know it works. 1402 */ 1403 1404 if ( j->ntype != nJunction && j->ntype != nAction) return j; 1405 1406 gblock = first_item_is_guess_block((Junction *)j); 1407 1408 if ( gblock!=NULL ) 1409 { 1410 Junction *past = gblock->end; 1411 Junction *p; 1412 require(past!=NULL, "analysis_point: no end block on (...)? block"); 1413 1414 for (p=(Junction *)past->p1; p!=NULL; ) 1415 { 1416 if ( p->ntype==nAction ) 1417 { 1418 p=(Junction *)((ActionNode *)p)->next; 1419 continue; 1420 } 1421 if ( p->ntype!=nJunction ) 1422 { 1423 past->alpha_beta_guess_end=1; /* MR14 */ 1424 return (Junction *)past->p1; 1425 } 1426 if ( p->jtype==EndBlk || p->jtype==EndRule ) 1427 { 1428 return j; 1429 } 1430 /* MR6 */ 1431 /* MR6 A guess block is of the form "(alpha)? beta" or "(alpha)?". */ 1432 /* MR6 When beta is omitted (second form) this means "(alpha)? alpha". */ 1433 /* MR6 The program does not store another copy of alpha in this case. */ 1434 /* MR6 During analysis when the program needs to know what follows the */ 1435 /* MR6 guess clause. It calls this routine. */ 1436 /* MR6 */ 1437 /* MR6 If it is of the form "(alpha)? beta" it returns a pointer to beta.*/ 1438 /* MR6 */ 1439 /* MR6 If it is of the form "(alpha)?" it returns a pointer to the guess */ 1440 /* MR6 block itself thereby reusing the junction tree. */ 1441 /* MR6 */ 1442 /* MR6 It works by searching the "next in sequence" chain (skipping actions) */ 1443 /* MR6 searching for a RuleRef or Token node. (Those are the only 4 kinds */ 1444 /* MR6 of nodes: Junctions, RuleRef, Token, and Action.) */ 1445 /* MR6 */ 1446 /* MR6 This won't work for the special case "(alpha)? ()" because it has no */ 1447 /* MR6 rule references or token nodes. It eventually encounters a */ 1448 /* MR6 junction of type EndBlk or EndRule and says to its caller: nothing */ 1449 /* MR6 more here to analyze - must be of the form "(alpha)?". */ 1450 /* MR6 */ 1451 /* MR6 In the case of "(alpha)? ()" it should return a pointer to "()" */ 1452 /* MR6 */ 1453 /* MR6 I think. */ 1454 /* MR6 */ 1455 if ( p->jtype!=Generic) { /* MR6 */ 1456 past->alpha_beta_guess_end=1; /* MR14 */ 1457 return (Junction *)past->p1; /* MR6 */ 1458 }; /* MR6 */ 1459 p=(Junction *)p->p1; 1460 } 1461 } 1462 return j; 1463 } 1464 1465 set 1466 #ifdef __USE_PROTOS 1467 First( Junction *j, int k, int jtype, int *max_k ) 1468 #else 1469 First( j, k, jtype, max_k ) 1470 Junction *j; 1471 int k; 1472 int jtype; 1473 int *max_k; 1474 #endif 1475 { 1476 Junction *alt1, *alt2; 1477 set a, rk, fCurBlk; 1478 int savek; 1479 int p1, p2; 1480 1481 int save_maintainBackTrace; 1482 1483 require(j->ntype==nJunction, "First: non junction passed"); 1484 1485 /* 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 */ 1486 fCurBlk = rk = empty; 1487 for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2 ) 1488 { 1489 Junction * p = NULL; 1490 Junction * p1junction = NULL; 1491 p = analysis_point((Junction *)alt1->p1); 1492 p1junction = (Junction *) (alt1->p1); 1493 #if 0 1494 if (p != p1junction) { 1495 fprintf(stdout,"Analysis point for #%d is #%d", p1junction->seq, p->seq); /* debug */ 1496 } 1497 #endif 1498 REACH(p, k, &rk, alt1->fset[k]); 1499 require(set_nil(rk), "rk != nil"); 1500 set_free(rk); 1501 set_orin(&fCurBlk, alt1->fset[k]); 1502 } 1503 1504 /* D e t e c t A m b i g u i t i e s */ 1505 *max_k = 1; 1506 for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++) 1507 { 1508 for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++) 1509 { 1510 savek = k; 1511 a = set_and(alt1->fset[k], alt2->fset[k]); 1512 while ( !set_nil(a) ) 1513 { 1514 /* if we have hit the max k requested, just give warning */ 1515 if ( j->approx==k ) { 1516 } 1517 1518 if ( k==CLL_k ) 1519 { 1520 #ifdef NOT_USED 1521 *** int save_LL_k = LL_k; 1522 *** int save_CLL_k = CLL_k; 1523 *** /* Get new LL_k from interactive feature if enabled */ 1524 *** if ( AImode ) 1525 *** AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k); 1526 #endif 1527 *max_k = CLL_k; 1528 save_maintainBackTrace=MR_MaintainBackTrace; 1529 if (AlphaBetaTrace) MR_MaintainBackTrace=0; 1530 HandleAmbiguity(j, alt1, alt2, jtype); 1531 MR_MaintainBackTrace=save_maintainBackTrace; 1532 break; 1533 } 1534 else 1535 { 1536 Junction *p = analysis_point((Junction *)alt1->p1); 1537 Junction *q = analysis_point((Junction *)alt2->p1); 1538 k++; /* attempt ambig alts again with more lookahead */ 1539 1540 REACH(p, k, &rk, alt1->fset[k]); 1541 require(set_nil(rk), "rk != nil"); 1542 REACH(q, k, &rk, alt2->fset[k]); 1543 require(set_nil(rk), "rk != nil"); 1544 set_free(a); 1545 a = set_and(alt1->fset[k], alt2->fset[k]); 1546 if ( k > *max_k ) *max_k = k; 1547 } 1548 } 1549 set_free(a); 1550 k = savek; 1551 } 1552 } 1553 1554 return fCurBlk; 1555 } 1556
