--- /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