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