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