diff options
Diffstat (limited to 'src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset.c')
-rw-r--r-- | src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset.c | 1555 |
1 files changed, 1555 insertions, 0 deletions
diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset.c b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset.c new file mode 100644 index 00000000..2e013cc1 --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset.c @@ -0,0 +1,1555 @@ +/* + * fset.c + * + * Compute FIRST and FOLLOW sets. + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-2001 + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "pcctscfg.h" + +#include "set.h" +#include "syn.h" +#include "hash.h" +#include "generic.h" +#include "dlgdef.h" +#include "limits.h" + +#ifdef __USE_PROTOS +static void ensure_predicates_cover_ambiguous_lookahead_sequences + (Junction *, Junction *, char *, Tree *); +#else +static void ensure_predicates_cover_ambiguous_lookahead_sequences(); +#endif + +/* + * What tokens are k tokens away from junction q? + * + * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this + * node. + * We lock the junction according to k--the lookahead. If we have been at this + * junction before looking for the same, k, number of lookahead tokens, we will + * do it again and again...until we blow up the stack. Locks are only used on aLoopBlk, + * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from + * FIRST and FOLLOW calcs. + * + * If p->jtype == EndRule we are going to attempt a FOLLOW. (FOLLOWs are really defined + * in terms of FIRST's, however). To proceed with the FOLLOW, p->halt cannot be + * set. p->halt is set to indicate that a reference to the current rule is in progress + * and the FOLLOW is not desirable. + * + * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule + * junction yields an empty set, replace the empty set with EOF. No FOLLOW means that + * only EOF can follow the current rule. This normally occurs only on the start symbol + * since all other rules are referenced by another rule somewhere. + * + * Normally, both p1 and p2 are followed. However, checking p2 on a RuleBlk node is + * the same as checking the next rule which is clearly incorrect. + * + * Cycles in the FOLLOW sense are possible. e.g. Fo(c) requires Fo(b) which requires + * Fo(c). Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c). Let's say + * Fo(c) is attempted first. It finds all of the FOLLOW symbols and then attempts + * to do Fo(b) which finds of its FOLLOW symbols. So, we have: + * + * Fo(c) + * / \ + * a set Fo(b) + * / \ + * a set Fo(c) .....Hmmmm..... Infinite recursion! + * + * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now + * correctly Fo(c) union Fo(b). We wish to pick up where we left off, so the fact + * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already + * laying around. SOOOOoooo, we track FOLLOW cycles. All FOLLOW computations are + * cached in a hash table. After the sequence of FOLLOWs finish, we reconcile all + * cycles --> correct all Fo(rule) sets in the cache. + * + * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30]. + * TJP 8/93 -- can now read PhD thesis from Purdue. + * + * Also, FIRST sets are cached in the hash table. Keys are (rulename,Fi/Fo,k). + * Only FIRST sets, for which the FOLLOW is not included, are stored. + * + * SPECIAL CASE of (...)+ blocks: + * I added an optional alt so that the alts could see what + * was behind the (...)+ block--thus using enough lookahead + * to branch out rather than just enough to distinguish + * between alts in the (...)+. However, when the FIRST("(...)+") is + * is needed, must not use this last "optional" alt. This routine + * turns off this path by setting a new 'ignore' flag for + * the alt and then resetting it afterwards. + */ + +set +#ifdef __USE_PROTOS +rJunc( Junction *p, int k, set *rk ) +#else +rJunc( p, k, rk ) +Junction *p; +int k; +set *rk; +#endif +{ + set a, b; + + require(p!=NULL, "rJunc: NULL node"); + require(p->ntype==nJunction, "rJunc: not junction"); + +#ifdef DBG_LL1 + if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k); + else fprintf(stderr, "rJunc: %s in rule %s\n", + decodeJType[p->jtype], ((Junction *)p)->rname); +#endif + /* if this is one of the added optional alts for (...)+ then return */ + + /* no need to pop backtrace - hasn't been pushed */ + + if ( p->ignore ) return empty; + + if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); + +/* MR14 */ if (AlphaBetaTrace && p->alpha_beta_guess_end) { +/* MR14 */ warnFL( +/* MR14 */ "not possible to compute follow set for alpha in an \"(alpha)? beta\" block. ", +/* MR14 */ FileStr[p->file],p->line); +/* MR14 */ MR_alphaBetaTraceReport(); +/* MR14 */ }; + +/* MR14 */ if (p->alpha_beta_guess_end) { +/* MR14 */ if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); +/* MR14 */ return empty; +/* MR14 */ } + + /* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */ + if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || + p->jtype==aPlusBlk || p->jtype==EndRule ) + { + require(p->lock!=NULL, "rJunc: lock array is NULL"); + if ( p->lock[k] ) + { + if ( p->jtype == EndRule ) /* FOLLOW cycle? */ + { +#ifdef DBG_LL1 + fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname); +#endif + if (! MR_AmbSourceSearch) RegisterCycle(p->rname, k); + } + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return empty; + } + if ( p->jtype == RuleBlk && + p->end->halt && + ! MR_AmbSourceSearch) /* check for FIRST cache */ + { + CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k)); + if ( q != NULL ) + { + set_orin(rk, q->rk); + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return set_dup( q->fset ); + } + } + if ( p->jtype == EndRule && + !p->halt && /* MR11 was using cache even when halt set */ + ! MR_AmbSourceSearch) /* FOLLOW set cached already? */ + { + CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k)); + if ( q != NULL ) + { +#ifdef DBG_LL1 + fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k); + s_fprT(stderr, q->fset); + if ( q->incomplete ) fprintf(stderr, " (incomplete)"); + fprintf(stderr, "\n"); +#endif + if ( !q->incomplete ) + { + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return set_dup( q->fset ); + } + } + } + p->lock[k] = TRUE; /* This rule is busy */ + } + + a = b = empty; + + if ( p->jtype == EndRule ) + { + if (p->halt ) /* don't want FOLLOW here? */ /* unless MR10 hoisting */ + { + p->lock[k] = FALSE; + set_orel(k, rk); /* indicate this k value needed */ + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return empty; + } + if (! MR_AmbSourceSearch) FoPush(p->rname, k); /* Attempting FOLLOW */ + if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */ +#ifdef DBG_LL1 + fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k); +#endif + } + + if ( p->p1 != NULL ) { +/* MR14 */ if (p->guess) { +/* MR14 */ if (p->guess_analysis_point == NULL) { +/* MR14 */ Node * guess_point; +/* MR14 */ guess_point=(Node *)analysis_point(p); +/* MR14 */ if (guess_point == (Node *)p) { +/* MR14 */ guess_point=p->p1; +/* MR14 */ } +/* MR14 */ p->guess_analysis_point=guess_point; +/* MR14 */ } +/* MR14 */ REACH(p->guess_analysis_point, k, rk, a); + } else { + REACH(p->p1, k, rk, a); + } + } + + /* C a c h e R e s u l t s */ + + if ( p->jtype == RuleBlk && p->end->halt && ! MR_AmbSourceSearch) /* can save FIRST set? */ + { + CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) ); + /*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/ + hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q); + q->fset = set_dup( a ); + q->rk = set_dup( *rk ); + } + + if ( p->jtype == EndRule && + !p->halt && /* MR11 was using cache even with halt set */ + ! MR_AmbSourceSearch) /* just completed FOLLOW? */ + { + /* Cache Follow set */ + CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k)); + if ( q==NULL ) + { + q = newCacheEntry( Fkey(p->rname,'o',k) ); + hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q); + } + /*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/ + if ( set_nil(a) && !q->incomplete ) + { + /* Don't ever save a nil set as complete. + * Turn it into an eof set. + */ + set_orel(EofToken, &a); + } + set_orin(&(q->fset), a); + FoPop( k ); + if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k); +#ifdef DBG_LL1 + fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k); + s_fprT(stderr, q->fset); + if ( q->incomplete ) fprintf(stderr, " (incomplete)"); + fprintf(stderr, "\n"); +#endif + } + + if (p->jtype != RuleBlk && p->p2 != NULL && /* MR14 */ ! p->guess) { + REACH(p->p2, k, rk, b); + } + + if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || + p->jtype==aPlusBlk || p->jtype==EndRule ) + p->lock[k] = FALSE; /* unlock node */ + + set_orin(&a, b); + set_free(b); + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return a; +} + +set +#ifdef __USE_PROTOS +rRuleRef( RuleRefNode *p, int k, set *rk_out ) +#else +rRuleRef( p, k, rk_out ) +RuleRefNode *p; +int k; +set *rk_out; +#endif +{ + set rk; + Junction *r; + int k2; + set a, rk2, b; + int save_halt; + RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text); + require(p!=NULL, "rRuleRef: NULL node"); + require(p->ntype==nRuleRef, "rRuleRef: not rule ref"); + +#ifdef DBG_LL1 + fprintf(stderr, "rRuleRef: %s\n", p->text); +#endif + + if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); + + if ( q == NULL ) + { + warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line ); + REACH(p->next, k, rk_out, a); + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return a; + } + rk2 = empty; + +/* MR9 Problems with rule references in guarded predicates */ +/* MR9 Perhaps can use hash table to find rule ? */ + +/* MR9 */ if (RulePtr == NULL) { +/* MR9 */ fatalFL(eMsg2("Rule %s uses rule %s via RulePtr before it has been initialized", +/* MR9 */ p->rname,q->str),FileStr[p->file],p->line); +/* MR9 */ }; + + r = RulePtr[q->rulenum]; + if ( r->lock[k] ) + { + errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s", + r->rname, p->rname) ); + + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + + return empty; + } + + save_halt = r->end->halt; + r->end->halt = TRUE; /* don't let reach fall off end of rule here */ + rk = empty; + REACH(r, k, &rk, a); + r->end->halt = save_halt; + while ( !set_nil(rk) ) { + k2 = set_int(rk); /* MR11 this messes up the ambiguity search routine */ + set_rm(k2, rk); + REACH(p->next, k2, &rk2, b); /* MR11 by changing the value of k */ + set_orin(&a, b); + set_free(b); + } + set_free(rk); /* this has no members, but free its memory */ + set_orin(rk_out, rk2); /* remember what we couldn't do */ + set_free(rk2); + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + return a; +} + +/* + * Return FIRST sub k ( token_node ) + * + * TJP 10/11/93 modified this so that token nodes that are actually + * ranges (T1..T2) work. + */ +set +#ifdef __USE_PROTOS +rToken( TokNode *p, int k, set *rk ) +#else +rToken( p, k, rk ) +TokNode *p; +int k; +set *rk; +#endif +{ + set a; + + require(p!=NULL, "rToken: NULL node"); + require(p->ntype==nToken, "rToken: not token node"); + +#ifdef DBG_LL1 + fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token): + ExprString(p->token)); +#endif + + + if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); + + if (MR_AmbSourceSearch && (k-1) == 0) { + + set localConstrain; + set intersection; + + localConstrain=fset[maxk-k+1]; + + if (! set_nil(p->tset)) { + intersection=set_and(localConstrain,p->tset); + if (! set_nil(intersection)) { + MR_backTraceReport(); + }; + set_free(intersection); + } else { + if (set_el( (unsigned) p->token,localConstrain)) { + MR_backTraceReport(); + } + }; + }; + + if ( k-1 == 0 ) { + + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + + if ( !set_nil(p->tset) ) { + return set_dup(p->tset); + } else { + return set_of(p->token); + }; + } + + REACH(p->next, k-1, rk, a); + + if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); + + return a; +} + +set +#ifdef __USE_PROTOS +rAction( ActionNode *p, int k, set *rk ) +#else +rAction( p, k, rk ) +ActionNode *p; +int k; +set *rk; +#endif +{ + set a; + + require(p!=NULL, "rJunc: NULL node"); + require(p->ntype==nAction, "rJunc: not action"); + +/* MR11 */ if (p->is_predicate && p->ampersandPred != NULL) { +/* MR11 */ Predicate *pred=p->ampersandPred; +/* MR11 */ if (k <= pred->k) { +/* MR11 */ REACH(p->guardNodes,k,rk,a); +/* MR11 */ return a; +/* MR11 */ }; +/* MR11 */ }; + + /* it might be a good idea when doing an MR_AmbSourceSearch + to *not* look behind predicates under some circumstances + we'll look into that later + */ + + REACH(p->next, k, rk, a); /* ignore actions */ + return a; +} + + /* A m b i g u i t y R e s o l u t i o n */ + + +void +#ifdef __USE_PROTOS +dumpAmbigMsg( set *fset, FILE *f, int want_nls ) +#else +dumpAmbigMsg( fset, f, want_nls ) +set *fset; +FILE *f; +int want_nls; +#endif +{ + int i; + + set copy; /* MR11 */ + + if ( want_nls ) fprintf(f, "\n\t"); + else fprintf(f, " "); + + for (i=1; i<=CLL_k; i++) + { + copy=set_dup(fset[i]); /* MR11 */ + + if ( i>1 ) + { + if ( !want_nls ) fprintf(f, ", "); + } + if ( set_deg(copy) > 3 && elevel == 1 ) + { + int e,m; + fprintf(f, "{"); + for (m=1; m<=3; m++) + { + e=set_int(copy); + fprintf(f, " %s", TerminalString(e)); + set_rm(e, copy); + } + fprintf(f, " ... }"); + } + else s_fprT(f, copy); + if ( want_nls ) fprintf(f, "\n\t"); + set_free(copy); + } + fprintf(f, "\n"); + +} + +static void +#ifdef __USE_PROTOS +verify_context(Predicate *predicate) +#else +verify_context(predicate) +Predicate *predicate; +#endif +{ + if ( predicate == NULL ) return; + + if ( predicate->expr == PRED_OR_LIST || + predicate->expr == PRED_AND_LIST ) + { + verify_context(predicate->down); + verify_context(predicate->right); /* MR10 */ + return; + } + + if ( !predicate->source->ctxwarned && predicate->source->guardpred==NULL && + ((predicate->k > 1 && + !is_single_tuple(predicate->tcontext)) || + ( predicate->k == 1 && + set_deg(predicate->scontext[1])>1 )) ) + { + +/* MR9 Suppress annoying messages caused by our own clever(?) fix */ + + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate->k); + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " predicate text: \"%s\"\n", + (predicate->expr == NULL ? "(null)" : predicate->expr) ); + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " You may only want one lookahead %d-sequence to apply\n", predicate->k); + fprintf(stderr, ErrHdr, FileStr[predicate->source->file], + predicate->source->line); + fprintf(stderr, " Try using a context guard '(...)? =>'\n"); + predicate->source->ctxwarned = 1; + } + verify_context(predicate->right); /* MR10 */ +} + +/* + * If delta is the set of ambiguous lookahead sequences, then make sure that + * the predicate(s) for productions alt1,alt2 cover the sequences in delta. + * + * For example, + * a : <<PRED1>>? (A B|A C) + * | b + * ; + * b : <<PRED2>>? A B + * | A C + * ; + * + * This should give a warning that (A C) predicts both productions and alt2 + * does not have a predicate in the production that generates (A C). + * + * The warning detection is simple. Let delta = LOOK(alt1) intersection LOOK(alt2). + * Now, if ( delta set-difference context(predicates-for-alt1) != empty then + * alt1 does not "cover" all ambiguous sequences. + * + * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset + * info. Actually, sets are used only if k=1 for this grammar. + */ +static void +#ifdef __USE_PROTOS +ensure_predicates_cover_ambiguous_lookahead_sequences + ( Junction *alt1, Junction *alt2, char *sub, Tree *ambig ) +#else +ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig ) +Junction *alt1; +Junction *alt2; +char *sub; +Tree *ambig; +#endif +{ + if ( !ParseWithPredicates ) return; + + if ( ambig!=NULL ) + { + Tree *non_covered = NULL; + if ( alt1->predicate!=NULL ) + non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset); + if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt1->altnum, sub); + if ( alt1->predicate!=NULL && non_covered!=NULL ) + { + fprintf(stderr, " upon"); + preorder(non_covered); + } + else if ( alt1->predicate==NULL ) + { + fprintf(stderr, " upon"); + preorder(ambig->down); + } + fprintf(stderr, "\n"); + } + Tfree(non_covered); + non_covered = NULL; + if ( alt2->predicate!=NULL ) + non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset); + if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt2->altnum, sub); + if ( alt2->predicate!=NULL && non_covered!=NULL ) + { + fprintf(stderr, " upon"); + preorder(non_covered); + } + else if ( alt2->predicate==NULL ) + { + fprintf(stderr, " upon"); + preorder(ambig->down); + } + fprintf(stderr, "\n"); + } + Tfree(non_covered); + } + else if ( !set_nil(alt1->fset[1]) ) + { + set delta, non_covered; + delta = set_and(alt1->fset[1], alt2->fset[1]); + non_covered = set_dif(delta, covered_set(alt1->predicate)); + if ( set_deg(non_covered)>0 && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt1->altnum, sub); + if ( alt1->predicate!=NULL ) + { + fprintf(stderr, " upon "); + s_fprT(stderr, non_covered); + } + fprintf(stderr, "\n"); + } + set_free( non_covered ); + non_covered = set_dif(delta, covered_set(alt2->predicate)); + if ( set_deg(non_covered)>0 && WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line); + fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity", + alt2->altnum, sub); + if ( alt2->predicate!=NULL ) + { + fprintf(stderr, " upon "); + s_fprT(stderr, non_covered); + } + fprintf(stderr, "\n"); + } + set_free( non_covered ); + set_free( delta ); + } + else fatal_internal("productions have no lookahead in predicate checking routine"); +} + +#ifdef __USE_PROTOS +void MR_doPredicatesHelp(int inGuessBlock,Junction *alt1,Junction *alt2,int jtype,char *sub) +#else +void MR_doPredicatesHelp(inGuessBlock,alt1,alt2,jtype,sub) + int inGuessBlock; + Junction *alt1; + Junction *alt2; + int jtype; + char *sub; +#endif +{ + Predicate *p1; + Predicate *p2; + + Junction *parentRule=MR_nameToRuleBlk(alt1->rname); + + if (inGuessBlock && WarningLevel <= 1) return; + + /* let antlr give the usual error message */ + + if (alt1->predicate == NULL && alt2->predicate == NULL) return; + + if ( (jtype == RuleBlk || jtype == aSubBlk) + && (alt1->predicate == NULL && alt2->predicate != NULL)) { + fprintf(stderr, ErrHdr, FileStr[parentRule->file],parentRule->line); + fprintf(stderr," warning: alt %d line %d and alt %d line %d of %s\n%s%s%s", + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + sub, + " These alts have ambig lookahead sequences resolved by a predicate for\n", + " the second choice. The second choice may not be reachable.\n", + " You may want to use a complementary predicate or rearrange the alts\n" + ); + return; + }; + + /* first do the easy comparison. then do the hard one */ + + if (MR_comparePredicates(alt1->predicate,alt2->predicate)) { + + if (jtype == aLoopBegin || jtype == aPlusBlk ) { + + /* I'm not sure this code is reachable. + Predicates following a (...)+ or (...)* block are probably + considered validation predicates and therefore not + participate in the predication expression + */ + + fprintf(stderr, ErrHdr,FileStr[parentRule->file],parentRule->line); + fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s", + "the predicates used to disambiguate optional/exit paths of ", + sub, + CurRule, + FileStr[alt1->file], + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + " are identical and have no resolving power\n"); + } else { + fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); + fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s", + "the predicates used to disambiguate", + CurRule, + FileStr[alt1->file], + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + " are identical and have no resolving power\n"); + }; + } else { + p1=predicate_dup_without_context(alt1->predicate); + p1=MR_unfold(p1); + MR_clearPredEntry(p1); + MR_simplifyInverted(p1,0); + p1=MR_predSimplifyALL(p1); + p2=predicate_dup_without_context(alt2->predicate); + p2=MR_unfold(p2); + MR_clearPredEntry(p2); + MR_simplifyInverted(p2,0); + p2=MR_predSimplifyALL(p2); + if (MR_comparePredicates(p1,p2)) { + if (jtype == aLoopBegin || jtype == aPlusBlk ) { + fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); + fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", + "the predicates used to disambiguate optional/exit paths of ", + sub, + CurRule, + FileStr[alt1->file], + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + " are identical when compared without context and may have no\n", + " resolving power for some lookahead sequences.\n"); + } else { + fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); + fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", + "the predicates used to disambiguate", + CurRule, + FileStr[alt1->file], + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + " are identical when compared without context and may have no\n", + " resolving power for some lookahead sequences.\n"); + }; + if (InfoP) { + fprintf(output,"\n#if 0\n\n"); + fprintf(output,"The following predicates are identical when compared without\n"); + fprintf(output," lookahead context information. For some ambiguous lookahead\n"); + fprintf(output," sequences they may not have any power to resolve the ambiguity.\n"); + fprintf(output,"\n"); + + fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n", + MR_ruleNamePlusOffset( (Node *) alt1), + alt1->altnum, + alt1->line, + FileStr[alt1->file]); + fprintf(output," The original predicate for choice 1 with available context information:\n\n"); + MR_dumpPred1(2,alt1->predicate,1); + fprintf(output," The predicate for choice 1 after expansion (but without context information):\n\n"); + MR_dumpPred1(2,p1,0); + if (p1 == NULL) { + Predicate *phelp; + fprintf(output," The predicate for choice 1 after expansion (but before simplification)\n\n"); + phelp=predicate_dup_without_context(alt1->predicate); + phelp=MR_unfold(phelp); + MR_clearPredEntry(phelp); + MR_simplifyInverted(phelp,0); + phelp=MR_predSimplifyALLX(phelp,1); + MR_dumpPred1(2,phelp,0); + predicate_free(phelp); + }; + fprintf(output,"\n"); + + fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n", + MR_ruleNamePlusOffset( (Node *) alt2), + alt2->altnum, + alt2->line, + FileStr[alt2->file]); + fprintf(output," The original predicate for choice 2 with available context information:\n\n"); + MR_dumpPred1(1,alt2->predicate,1); + fprintf(output," The predicate for choice 2 after expansion (but without context information):\n\n"); + MR_dumpPred1(1,p2,0); + if (p2 == NULL) { + Predicate *phelp; + fprintf(output," The predicate for choice 2 after expansion (but before simplification)\n\n"); + phelp=predicate_dup_without_context(alt2->predicate); + phelp=MR_unfold(phelp); + MR_clearPredEntry(phelp); + MR_simplifyInverted(phelp,0); + phelp=MR_predSimplifyALLX(phelp,1); + MR_dumpPred1(2,phelp,0); + predicate_free(phelp); + }; + fprintf(output,"\n#endif\n"); + }; + } else if (MR_secondPredicateUnreachable(p1,p2)) { + if (jtype == aLoopBegin || jtype == aPlusBlk ) { + fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); + fprintf(stderr," warning: %s of %s in rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", + "the predicate used to disambiguate the first choice of the optional/exit paths of ", + sub, + CurRule, + FileStr[alt1->file], + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + " appears to \"cover\" the second predicate when compared without context.\n", + " The second predicate may have no resolving power for some lookahead sequences.\n"); + } else { + fprintf(stderr, ErrHdr, FileStr[parentRule->file], parentRule->line); + fprintf(stderr," warning: %s rule %s\n (file %s alt %d line %d and alt %d line %d)\n%s%s", + "the predicate used to disambiguate the first choice of", + CurRule, + FileStr[alt1->file], + alt1->altnum, + alt1->line, + alt2->altnum, + alt2->line, + " appears to \"cover\" the second predicate when compared without context.\n", + " The second predicate may have no resolving power for some lookahead sequences.\n"); + }; + if (InfoP) { + fprintf(output,"\n#if 0\n\n"); + fprintf(output,"The first predicate appears to \"cover\" the second predicate when they\n"); + fprintf(output," are compared without lookahead context information. For some ambiguous\n"); + fprintf(output," lookahead sequences the second predicate may not have any power to\n"); + fprintf(output," resolve the ambiguity.\n"); + fprintf(output,"\n"); + fprintf(output,"Choice 1: %s alt %d line %d file %s\n\n", + MR_ruleNamePlusOffset( (Node *) alt1), + alt1->altnum, + alt1->line, + FileStr[alt1->file]); + fprintf(output," The original predicate for choice 1 with available context information:\n\n"); + MR_dumpPred1(2,alt1->predicate,1); + fprintf(output," The predicate for choice 1 after expansion (but without context information):\n\n"); + MR_dumpPred1(2,p1,0); + if (p1 == NULL) { + Predicate *phelp; + fprintf(output," The predicate for choice 1 after expansion (but before simplification)\n\n"); + phelp=predicate_dup_without_context(alt1->predicate); + phelp=MR_unfold(phelp); + MR_clearPredEntry(phelp); + MR_simplifyInverted(phelp,0); + phelp=MR_predSimplifyALLX(phelp,1); + MR_dumpPred1(2,phelp,0); + predicate_free(phelp); + }; + fprintf(output,"\n"); + + fprintf(output,"Choice 2: %s alt %d line %d file %s\n\n", + MR_ruleNamePlusOffset( (Node *) alt2), + alt2->altnum, + alt2->line, + FileStr[alt2->file]); + fprintf(output," The original predicate for choice 2 with available context information:\n\n"); + MR_dumpPred1(1,alt2->predicate,1); + fprintf(output," The predicate for choice 2 after expansion (but without context information):\n\n"); + MR_dumpPred1(1,p2,0); + if (p2 == NULL) { + Predicate *phelp; + fprintf(output," The predicate for choice 2 after expansion (but before simplification)\n\n"); + phelp=predicate_dup_without_context(alt2->predicate); + phelp=MR_unfold(phelp); + MR_clearPredEntry(phelp); + MR_simplifyInverted(phelp,0); + phelp=MR_predSimplifyALLX(phelp,1); + MR_dumpPred1(2,phelp,0); + predicate_free(phelp); + }; + fprintf(output,"\n#endif\n"); + }; + }; + predicate_free(p1); + predicate_free(p2); + }; +} + +static int totalOverflow=0; /* MR9 */ + +void +#ifdef __USE_PROTOS +HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype ) +#else +HandleAmbiguity( block, alt1, alt2, jtype ) +Junction *block; +Junction *alt1; +Junction *alt2; +int jtype; +#endif +{ + unsigned **ftbl; + set *fset, b; + int i, numAmbig,n2; + Tree *ambig=NULL, *t, *u; + char *sub = ""; + long n; + int thisOverflow=0; /* MR9 */ + long set_deg_value; /* MR10 */ + long threshold; /* MR10 */ + + require(block!=NULL, "NULL block"); + require(block->ntype==nJunction, "invalid block"); + + /* These sets are used to constrain LL_k set, but are made CLL_k long anyway */ + fset = (set *) calloc(CLL_k+1, sizeof(set)); + require(fset!=NULL, "cannot allocate fset"); + ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *)); + require(ftbl!=NULL, "cannot allocate ftbl"); + + /* create constraint table and count number of possible ambiguities (use<=LL_k) */ + for (n=1,i=1; i<=CLL_k; i++) + { + b = set_and(alt1->fset[i], alt2->fset[i]); +/* MR9 */ set_deg_value = set_deg(b); +/* MR10 */ if (n > 0) { +/* MR10 */ threshold = LONG_MAX / n; +/* MR10 */ if (set_deg_value <= threshold) { +/* MR10 */ n *= set_deg_value; +/* MR10 */ } else { +/* MR10 */ n=LONG_MAX; +/* MR9 */ if (totalOverflow == 0) { +#if 0 + /* MR10 comment this out because it just makes users worry */ + +/* MR9 */ warnNoFL("Overflow in computing number of possible ambiguities in HandleAmbiguity\n"); +#endif +/* MR9 */ }; +/* MR9 */ thisOverflow++; +/* MR9 */ totalOverflow++; +/* MR9 */ }; +/* MR10 */ } else { +/* MR10 */ n *= set_deg_value; +/* MR9 */ }; + fset[i] = set_dup(b); + ftbl[i] = set_pdq(b); + set_free(b); + } + + switch ( jtype ) + { + case aSubBlk: sub = "of (..) "; break; + case aOptBlk: sub = "of {..} "; break; + case aLoopBegin: sub = "of (..)* "; break; + case aLoopBlk: sub = "of (..)* "; break; + case aPlusBlk: sub = "of (..)+ "; break; + case RuleBlk: sub = "of the rule itself "; break; + default : sub = ""; break; + } + + /* If the block is marked as a compressed lookahead only block, then + * simply return; ambiguity warning is given only at warning level 2. + */ + if ( block->approx>0 ) + { + if ( ParseWithPredicates ) + { + if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ + if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ + + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); + alt1->predicate=MR_predSimplifyALL(alt1->predicate); + + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); + alt2->predicate=MR_predSimplifyALL(alt2->predicate); + + MR_doPredicatesHelp(0,alt1,alt2,jtype,sub); + + if ( HoistPredicateContext + && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + + if ( HoistPredicateContext + && (alt1->predicate!=NULL||alt2->predicate!=NULL) + && WarningLevel>1 ) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + } + + if ( WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + dumpAmbigMsg(fset, stderr, 0); + MR_traceAmbSource(fset,alt1,alt2); + } + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + /* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation; + * don't bother doing full LL(k) analysis. + * (This "if" block handles the LL(1) case) + */ + + n2 = 0; + for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]); + + /* here STARTS the special case in which the lookahead sets for alt1 and alt2 + all have degree 1 for k<LL_k (including LL_k=1) + */ + + if ( n2==2*(LL_k-1) ) + { + + /* TJP: added to fix the case where LL(1) and syntactic predicates didn't + * work. It now recognizes syntactic predicates, but does not like combo: + * LL(1)/syn/sem predicates. (10/24/93) + */ + + if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL ) + { + if ( WarningLevel==1 ) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + dumpAmbigMsg(fset, stderr, 0); + MR_traceAmbSource(fset,alt1,alt2); + } + + ambig = NULL; + if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset); + if ( ParseWithPredicates ) + { + if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ + if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ + + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); + alt1->predicate=MR_predSimplifyALL(alt1->predicate); + + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); + alt2->predicate=MR_predSimplifyALL(alt2->predicate); + + MR_doPredicatesHelp(0,alt1,alt2,jtype,sub); + + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + if ( WarningLevel == 1 && + (alt1->predicate!=NULL||alt2->predicate!=NULL)) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + Tfree(ambig); + return; + } + } +/* end TJP (10/24/93) */ + + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + if ( elevel == 3 && LL_k>1 ) + { + preorder(ambig); + fprintf(stderr, "\n"); + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + Tfree(ambig); + return; + }; + + Tfree(ambig); + dumpAmbigMsg(fset, stderr, 0); + + /* because this is a special case in which both alt1 and alt2 have + lookahead sets of degree 1 for k<LL_k (including k=1) the linear + lookahead style search is adequate + */ + + MR_traceAmbSource(fset,alt1,alt2); + + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + /* here ENDS the special case in which the lookahead sets for alt1 and alt2 + all have degree 1 for k<LL_k (including LL_k=1) + */ + + /* in case tree construction runs out of memory, set info to make good err msg */ + + CurAmbigAlt1 = alt1->altnum; + CurAmbigAlt2 = alt2->altnum; + CurAmbigbtype = sub; + CurAmbigfile = alt1->file; + CurAmbigline = alt1->line; + + /* Don't do full LL(n) analysis if (...)? block because the block, + by definition, defies LL(n) analysis. + If guess (...)? block and ambiguous then don't remove anything from + 2nd alt to resolve ambig. + Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block + since it is much cheaper than LL(n). LL sup 1 ( n ) "covers" the LL(n) + lookahead information. + + Note: LL(n) context cannot be computed for semantic predicates when + followed by (..)?. + + If (..)? then we scream "AAAHHHH! No LL(n) analysis will help" + + Is 'ambig' always defined if we enter this if? I hope so + because the 'ensure...()' func references it. TJP Nov 1993. + */ + + /* THM MR30: Instead of using first_item_is_guss_block we use + first_item_is_guess_block_extra which will look inside a + loop block for a guess block. In other words ( (...)? )*. + It there is an ambiguity in this circumstance then we suppress + the normal methods of resolving ambiguities. + */ + + if ( first_item_is_guess_block_extra((Junction *)alt1->p1)!=NULL ) + { + if ( ParseWithPredicates ) + { + if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ + if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); + alt1->predicate=MR_predSimplifyALL(alt1->predicate); + + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); + alt2->predicate=MR_predSimplifyALL(alt2->predicate); + + MR_doPredicatesHelp(1,alt1,alt2,jtype,sub); + + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + if ( WarningLevel==1 && + (alt1->predicate!=NULL||alt2->predicate!=NULL)) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + } + + if ( WarningLevel>1 ) + { + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + dumpAmbigMsg(fset, stderr, 0); + MR_traceAmbSource(fset,alt1,alt2); + } + + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + /* Not resolved with (..)? block. Do full LL(n) analysis */ + + /* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */ + /* MR11 VerifyAmbig once used fset destructively */ + + ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig); + + /* are all things in intersection really ambigs? */ + + if (thisOverflow || numAmbig < n ) /* MR9 */ + { + Tree *v; + + /* remove ambig permutation from 2nd alternative to resolve ambig; + * We want to compute the set of artificial tuples, arising from + * LL sup 1 (n) compression, that collide with real tuples from the + * 2nd alternative. This is the set of "special case" tuples that + * the LL sup 1 (n) decision template maps incorrectly. + */ + + /* when generating code in genExpr() it does + * + * if ( genExprSets(j->fset) && !genExprTree(j->ftree)) {... + * + * Sooooo the j->ftree is the tree of alt2 + * after removal of conflicts, not alt1 ! + */ + + if ( ambig!=NULL ) + { + /* at the top of ambig is an ALT node */ + + for (v=ambig->down; v!=NULL; v=v->right) + { + u = trm_perm(u, v); /* remove v FROM u */ + } +/* fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/ + } + Tfree( t ); + alt1->ftree = tappend(alt1->ftree, u); + alt1->ftree = tleft_factor(alt1->ftree); + } + + if ( ambig==NULL ) + { + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + + ambig = tleft_factor(ambig); + +/* TJP: + * At this point, we surely have an LL(k) ambiguity. Check for predicates + */ + if ( ParseWithPredicates ) + { + if (alt1->predicate != NULL) predicate_free(alt1->predicate); /* MR12 */ + if (alt2->predicate != NULL) predicate_free(alt2->predicate); /* MR12 */ + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed"); + alt1->predicate=MR_predSimplifyALL(alt1->predicate); + + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1); + require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty"); + require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed"); + alt2->predicate=MR_predSimplifyALL(alt2->predicate); + + MR_doPredicatesHelp(0,alt1,alt2,jtype,sub); + + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) ) + { + verify_context(alt1->predicate); + verify_context(alt2->predicate); + } + if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 ) + ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig); + if ( WarningLevel==1 && + (alt1->predicate!=NULL||alt2->predicate!=NULL)) + { + + /* We found at least one pred for at least one of the alts; + * If warnings are low, just return. + */ + + Tfree(ambig); + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); + return; + } + /* else we're gonna give a warning */ + } +/* end TJP addition */ + + fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line); + if ( jtype == aLoopBegin || jtype == aPlusBlk ) + fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub); + else + fprintf(stderr, " warning: alts %d and %d %sambiguous upon", + alt1->altnum, alt2->altnum, sub); + if ( elevel == 3 ) + { + preorder(ambig->down); /* <===== k>1 ambiguity message data */ + fprintf(stderr, "\n"); + } else { + MR_skipped_e3_report=1; + dumpAmbigMsg(fset, stderr, 0); + }; + + MR_traceAmbSourceK(ambig,alt1,alt2); /* <====== k>1 ambiguity aid */ + + Tfree(ambig); + + for (i=1; i<=CLL_k; i++) set_free( fset[i] ); + free((char *)fset); + for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] ); + free((char *)ftbl); +} + +/* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze + * Return the 1st node of the beta block if present else return j. + */ +Junction * +#ifdef __USE_PROTOS +analysis_point( Junction *j ) +#else +analysis_point( j ) +Junction *j; +#endif +{ + Junction *gblock; + + /* MR13b When there was an action/predicate preceding a guess block + the guess block became invisible at the analysis_point. + + first_item_is_guess_block accepts any kind of node, + despite the fact that the formal is a junction. But + I don't want to have to change it all over the place + until I know it works. + */ + + if ( j->ntype != nJunction && j->ntype != nAction) return j; + + gblock = first_item_is_guess_block((Junction *)j); + + if ( gblock!=NULL ) + { + Junction *past = gblock->end; + Junction *p; + require(past!=NULL, "analysis_point: no end block on (...)? block"); + + for (p=(Junction *)past->p1; p!=NULL; ) + { + if ( p->ntype==nAction ) + { + p=(Junction *)((ActionNode *)p)->next; + continue; + } + if ( p->ntype!=nJunction ) + { + past->alpha_beta_guess_end=1; /* MR14 */ + return (Junction *)past->p1; + } + if ( p->jtype==EndBlk || p->jtype==EndRule ) + { + return j; + } +/* MR6 */ +/* MR6 A guess block is of the form "(alpha)? beta" or "(alpha)?". */ +/* MR6 When beta is omitted (second form) this means "(alpha)? alpha". */ +/* MR6 The program does not store another copy of alpha in this case. */ +/* MR6 During analysis when the program needs to know what follows the */ +/* MR6 guess clause. It calls this routine. */ +/* MR6 */ +/* MR6 If it is of the form "(alpha)? beta" it returns a pointer to beta.*/ +/* MR6 */ +/* MR6 If it is of the form "(alpha)?" it returns a pointer to the guess */ +/* MR6 block itself thereby reusing the junction tree. */ +/* MR6 */ +/* MR6 It works by searching the "next in sequence" chain (skipping actions) */ +/* MR6 searching for a RuleRef or Token node. (Those are the only 4 kinds */ +/* MR6 of nodes: Junctions, RuleRef, Token, and Action.) */ +/* MR6 */ +/* MR6 This won't work for the special case "(alpha)? ()" because it has no */ +/* MR6 rule references or token nodes. It eventually encounters a */ +/* MR6 junction of type EndBlk or EndRule and says to its caller: nothing */ +/* MR6 more here to analyze - must be of the form "(alpha)?". */ +/* MR6 */ +/* MR6 In the case of "(alpha)? ()" it should return a pointer to "()" */ +/* MR6 */ +/* MR6 I think. */ +/* MR6 */ + if ( p->jtype!=Generic) { /* MR6 */ + past->alpha_beta_guess_end=1; /* MR14 */ + return (Junction *)past->p1; /* MR6 */ + }; /* MR6 */ + p=(Junction *)p->p1; + } + } + return j; +} + +set +#ifdef __USE_PROTOS +First( Junction *j, int k, int jtype, int *max_k ) +#else +First( j, k, jtype, max_k ) +Junction *j; +int k; +int jtype; +int *max_k; +#endif +{ + Junction *alt1, *alt2; + set a, rk, fCurBlk; + int savek; + int p1, p2; + + int save_maintainBackTrace; + + require(j->ntype==nJunction, "First: non junction passed"); + + /* 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 */ + fCurBlk = rk = empty; + for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2 ) + { + Junction * p = NULL; + Junction * p1junction = NULL; + p = analysis_point((Junction *)alt1->p1); + p1junction = (Junction *) (alt1->p1); +#if 0 + if (p != p1junction) { + fprintf(stdout,"Analysis point for #%d is #%d", p1junction->seq, p->seq); /* debug */ + } +#endif + REACH(p, k, &rk, alt1->fset[k]); + require(set_nil(rk), "rk != nil"); + set_free(rk); + set_orin(&fCurBlk, alt1->fset[k]); + } + + /* D e t e c t A m b i g u i t i e s */ + *max_k = 1; + for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++) + { + for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++) + { + savek = k; + a = set_and(alt1->fset[k], alt2->fset[k]); + while ( !set_nil(a) ) + { + /* if we have hit the max k requested, just give warning */ + if ( j->approx==k ) { + } + + if ( k==CLL_k ) + { +#ifdef NOT_USED +*** int save_LL_k = LL_k; +*** int save_CLL_k = CLL_k; +*** /* Get new LL_k from interactive feature if enabled */ +*** if ( AImode ) +*** AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k); +#endif + *max_k = CLL_k; + save_maintainBackTrace=MR_MaintainBackTrace; + if (AlphaBetaTrace) MR_MaintainBackTrace=0; + HandleAmbiguity(j, alt1, alt2, jtype); + MR_MaintainBackTrace=save_maintainBackTrace; + break; + } + else + { + Junction *p = analysis_point((Junction *)alt1->p1); + Junction *q = analysis_point((Junction *)alt2->p1); + k++; /* attempt ambig alts again with more lookahead */ + + REACH(p, k, &rk, alt1->fset[k]); + require(set_nil(rk), "rk != nil"); + REACH(q, k, &rk, alt2->fset[k]); + require(set_nil(rk), "rk != nil"); + set_free(a); + a = set_and(alt1->fset[k], alt2->fset[k]); + if ( k > *max_k ) *max_k = k; + } + } + set_free(a); + k = savek; + } + } + + return fCurBlk; +} |