4 * $Id: fset.c,v 1.6 95/06/15 18:07:09 parrt Exp $
7 * Compute FIRST and FOLLOW sets.
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.
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
31 * Parr Research Corporation
32 * with Purdue University and AHPCRC, University of Minnesota
47 extern char *PRED_AND_LIST;
48 extern char *PRED_OR_LIST;
51 static void ensure_predicates_cover_ambiguous_lookahead_sequences(Junction *, Junction *, char *, Tree *);
53 static void ensure_predicates_cover_ambiguous_lookahead_sequences();
57 * What tokens are k tokens away from junction q?
59 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
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.
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.
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.
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.
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:
89 * a set Fo(c) .....Hmmmm..... Infinite recursion!
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.
98 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
99 * TJP 8/93 -- can now read PhD thesis from Purdue.
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.
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.
115 rJunc( Junction *p, int k, set *rk )
124 require(p!=NULL, "rJunc: NULL node");
125 require(p->ntype==nJunction, "rJunc: not junction");
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);
132 /* if this is one of the added optional alts for (...)+ then return */
133 if ( p->ignore ) return empty;
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 )
139 require(p->lock!=NULL, "rJunc: lock array is NULL");
142 if ( p->jtype == EndRule ) /* FOLLOW cycle? */
145 fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);
147 RegisterCycle(p->rname, k);
151 if ( p->jtype == RuleBlk && p->end->halt ) /* check for FIRST cache */
153 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
157 return set_dup( q->fset );
160 if ( p->jtype == EndRule ) /* FOLLOW set cached already? */
162 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
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");
171 if ( !q->incomplete )
173 return set_dup( q->fset );
177 p->lock[k] = TRUE; /* This rule is busy */
182 if ( p->jtype == EndRule )
184 if ( p->halt ) /* don't want FOLLOW here? */
187 set_orel(k, rk); /* indicate this k value needed */
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 */
193 fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);
197 if ( p->p1 != NULL ) REACH(p->p1, k, rk, a);
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? */
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 );
209 if ( p->jtype == EndRule ) /* just completed FOLLOW? */
211 /* Cache Follow set */
212 CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
215 q = newCacheEntry( Fkey(p->rname,'o',k) );
216 hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
218 /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
219 if ( set_nil(a) && !q->incomplete )
221 /* Don't ever save a nil set as complete.
222 * Turn it into an eof set.
224 set_orel(EofToken, &a);
226 set_orin(&(q->fset), a);
228 if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
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");
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 */
249 rRuleRef( RuleRefNode *p, int k, set *rk_out )
251 rRuleRef( p, k, rk_out )
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");
267 fprintf(stderr, "rRuleRef: %s\n", p->text);
271 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
272 REACH(p->next, k, rk_out, a);
276 r = RulePtr[q->rulenum];
279 errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
280 r->rname, p->rname) );
283 save_halt = r->end->halt;
284 r->end->halt = TRUE; /* don't let reach fall off end of rule here */
287 r->end->halt = save_halt;
288 while ( !set_nil(rk) ) {
291 REACH(p->next, k2, &rk2, b);
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 */
302 * Return FIRST sub k ( token_node )
304 * TJP 10/11/93 modified this so that token nodes that are actually
305 * ranges (T1..T2) work.
309 rToken( TokNode *p, int k, set *rk )
318 require(p!=NULL, "rToken: NULL node");
319 require(p->ntype==nToken, "rToken: not token node");
322 fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):
323 ExprString(p->token));
327 if ( !set_nil(p->tset) ) return set_dup(p->tset);
328 return set_of(p->token);
330 REACH(p->next, k-1, rk, a);
337 rAction( ActionNode *p, int k, set *rk )
346 require(p!=NULL, "rJunc: NULL node");
347 require(p->ntype==nAction, "rJunc: not action");
349 REACH(p->next, k, rk, a); /* ignore actions */
353 /* A m b i g u i t y R e s o l u t i o n */
358 dumpAmbigMsg( set *fset, FILE *f, int want_nls )
360 dumpAmbigMsg( fset, f, want_nls )
368 if ( want_nls ) fprintf(f, "\n\t");
369 else fprintf(f, " ");
370 for (i=1; i<=CLL_k; i++)
374 if ( !want_nls ) fprintf(f, ", ");
376 if ( set_deg(fset[i]) > 3 && elevel == 1 )
383 fprintf(f, " %s", TerminalString(e));
386 fprintf(f, " ... }");
388 else s_fprT(f, fset[i]);
389 if ( want_nls ) fprintf(f, "\n\t");
396 verify_context(Predicate *predicate)
398 verify_context(predicate)
399 Predicate *predicate;
402 if ( predicate == NULL ) return;
404 if ( predicate->expr == PRED_OR_LIST ||
405 predicate->expr == PRED_AND_LIST )
407 verify_context(predicate->down);
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 )) )
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;
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.
435 * a : <<PRED1>>? (A B|A C)
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).
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.
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.
454 ensure_predicates_cover_ambiguous_lookahead_sequences( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )
456 ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )
463 if ( !ParseWithPredicates ) return;
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 )
472 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
473 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
475 if ( alt1->predicate!=NULL && non_covered!=NULL )
477 fprintf(stderr, " upon");
478 preorder(non_covered);
480 else if ( alt1->predicate==NULL )
482 fprintf(stderr, " upon");
483 preorder(ambig->down);
485 fprintf(stderr, "\n");
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 )
493 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
494 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
496 if ( alt2->predicate!=NULL && non_covered!=NULL )
498 fprintf(stderr, " upon");
499 preorder(non_covered);
501 else if ( alt2->predicate==NULL )
503 fprintf(stderr, " upon");
504 preorder(ambig->down);
506 fprintf(stderr, "\n");
510 else if ( !set_nil(alt1->fset[1]) )
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 )
517 fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
518 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
520 if ( alt1->predicate!=NULL )
522 fprintf(stderr, " upon ");
523 s_fprT(stderr, non_covered);
525 fprintf(stderr, "\n");
527 set_free( non_covered );
528 non_covered = set_dif(delta, covered_set(alt2->predicate));
529 if ( set_deg(non_covered)>0 && WarningLevel>1 )
531 fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
532 fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
534 if ( alt2->predicate!=NULL )
536 fprintf(stderr, " upon ");
537 s_fprT(stderr, non_covered);
539 fprintf(stderr, "\n");
541 set_free( non_covered );
544 else fatal_internal("productions have no lookahead in predicate checking routine");
549 HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )
551 HandleAmbiguity( block, alt1, alt2, jtype )
560 int i, numAmbig, n, n2;
561 Tree *ambig=NULL, *t, *u;
563 require(block!=NULL, "NULL block");
564 require(block->ntype==nJunction, "invalid block");
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++)
574 b = set_and(alt1->fset[i], alt2->fset[i]);
576 fset[i] = set_dup(b);
577 ftbl[i] = set_pdq(b);
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;
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.
595 if ( block->approx>0 )
597 if ( ParseWithPredicates )
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) )
603 verify_context(alt1->predicate);
604 verify_context(alt2->predicate);
607 if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
608 ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
611 if ( WarningLevel>1 )
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);
617 fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon",
618 alt1->altnum, alt2->altnum, sub);
619 dumpAmbigMsg(fset, stderr, 0);
621 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
623 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
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)
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) )
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)
640 if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
642 if ( WarningLevel==1 )
644 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
646 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
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);
655 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
656 alt1->altnum, alt2->altnum, sub);
657 dumpAmbigMsg(fset, stderr, 0);
661 if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset);
662 if ( ParseWithPredicates )
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) )
668 verify_context(alt1->predicate);
669 verify_context(alt2->predicate);
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))
676 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
678 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
684 /* end TJP (10/24/93) */
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);
690 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
691 alt1->altnum, alt2->altnum, sub);
692 if ( elevel == 3 && LL_k>1 )
695 fprintf(stderr, "\n");
700 dumpAmbigMsg(fset, stderr, 0);
702 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
704 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
709 /* in case tree construction runs out of memory, set info to make good err msg */
710 CurAmbigAlt1 = alt1->altnum;
711 CurAmbigAlt2 = alt2->altnum;
713 CurAmbigfile = alt1->file;
714 CurAmbigline = alt1->line;
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.
724 Note: LL(n) context cannot be computed for semantic predicates when
727 If (..)? then we scream "AAAHHHH! No LL(n) analysis will help"
729 Is 'ambig' always defined if we enter this if? I hope so
730 because the 'ensure...()' func references it. TJP Nov 1993.
732 if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
734 if ( ParseWithPredicates )
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) )
740 verify_context(alt1->predicate);
741 verify_context(alt2->predicate);
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))
748 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
750 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
756 if ( WarningLevel>1 )
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);
762 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
763 alt1->altnum, alt2->altnum, sub);
764 dumpAmbigMsg(fset, stderr, 0);
767 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
769 for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
774 /* Not resolved with (..)? block. Do full LL(n) analysis */
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] );
781 /* are all things in intersection really ambigs? */
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.
794 for (v=ambig->down; v!=NULL; v=v->right)
798 /* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
801 alt1->ftree = tappend(alt1->ftree, u);
802 alt1->ftree = tleft_factor(alt1->ftree);
807 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
812 ambig = tleft_factor(ambig);
815 * At this point, we surely have an LL(k) ambiguity. Check for predicates
817 if ( ParseWithPredicates )
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) )
823 verify_context(alt1->predicate);
824 verify_context(alt2->predicate);
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))
831 /* We found at least one pred for at least one of the alts;
832 * If warnings are low, just return.
837 /* else we're gonna give a warning */
839 /* end TJP addition */
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);
845 fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
846 alt1->altnum, alt2->altnum, sub);
849 preorder(ambig->down);
850 fprintf(stderr, "\n");
855 dumpAmbigMsg(fset, stderr, 0);
856 for (i=1; i<=CLL_k; i++) set_free( fset[i] );
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.
865 analysis_point( Junction *j )
873 if ( j->ntype!=nJunction ) return j;
874 gblock = first_item_is_guess_block((Junction *)j);
878 Junction *past = gblock->end;
880 require(past!=NULL, "analysis_point: no end block on (...)? block");
882 for (p=(Junction *)past->p1; p!=NULL; )
884 if ( p->ntype==nAction )
886 p=(Junction *)((ActionNode *)p)->next;
889 if ( p->ntype!=nJunction )
891 return (Junction *)past->p1;
893 if ( p->jtype==EndBlk || p->jtype==EndRule )
905 First( Junction *j, int k, int jtype, int *max_k )
907 First( j, k, jtype, max_k )
914 Junction *alt1, *alt2;
918 require(j->ntype==nJunction, "First: non junction passed");
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)
924 Junction *p = analysis_point((Junction *)alt1->p1);
925 REACH(p, k, &rk, alt1->fset[k]);
926 require(set_nil(rk), "rk != nil");
928 set_orin(&fCurBlk, alt1->fset[k]);
931 /* D e t e c t A m b i g u i t i e s */
933 for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)
935 for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)
938 a = set_and(alt1->fset[k], alt2->fset[k]);
939 while ( !set_nil(a) )
941 /* if we have hit the max k requested, just give warning */
942 if ( j->approx==k ) {
948 int save_LL_k = LL_k;
949 int save_CLL_k = CLL_k;
950 /* Get new LL_k from interactive feature if enabled */
952 AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);
955 HandleAmbiguity(j, alt1, alt2, jtype);
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");
968 a = set_and(alt1->fset[k], alt2->fset[k]);
969 if ( k > *max_k ) *max_k = k;