X-Git-Url: https://git.proxmox.com/?p=mirror_edk2.git;a=blobdiff_plain;f=Tools%2FSource%2FTianoTools%2FPccts%2Fantlr%2Ffset.c;fp=Tools%2FSource%2FTianoTools%2FPccts%2Fantlr%2Ffset.c;h=0000000000000000000000000000000000000000;hp=e1a76ec62060327d78833aff63e01bd7eabda29f;hb=feccee87a78e68d575dbdf44b34ca0cb5a21ea8d;hpb=214b0d1914b48d651b25e58f321ddb77a46903b8 diff --git a/Tools/Source/TianoTools/Pccts/antlr/fset.c b/Tools/Source/TianoTools/Pccts/antlr/fset.c deleted file mode 100644 index e1a76ec620..0000000000 --- a/Tools/Source/TianoTools/Pccts/antlr/fset.c +++ /dev/null @@ -1,1555 +0,0 @@ -/* - * 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 -#include - -#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 it's 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 : <>? (A B|A C) - * | b - * ; - * b : <>? 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 threshhold; /* 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 */ threshhold = LONG_MAX / n; -/* MR10 */ if (set_deg_value <= threshhold) { -/* 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=1 permutation; - * don't bother doing full LL(k) analysis. - * (This "if" block handles the LL(1) case) - */ - - n2 = 0; - for (i=1; ifset[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 kp1)!=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 kaltnum; - 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; -}