/* | |
* 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; | |
} |