/* * fset2.c * * Compute FIRST sets for full LL(k) * * SOFTWARE RIGHTS * * We reserve no LEGAL rights to the Purdue Compiler Construction Tool * Set (PCCTS) -- PCCTS is in the public domain. An individual or * company may do whatever they wish with source code distributed with * PCCTS or the code generated by PCCTS, including the incorporation of * PCCTS, or its output, into commerical software. * * We encourage users to develop software with PCCTS. However, we do ask * that credit is given to us for developing PCCTS. By "credit", * we mean that if you incorporate our source code into one of your * programs (commercial product, research project, or otherwise) that you * acknowledge this fact somewhere in the documentation, research report, * etc... If you like PCCTS and have developed a nice tool with the * output, please mention that you developed it using PCCTS. In * addition, we ask that this header remain intact in our source code. * As long as these guidelines are kept, we expect to continue enhancing * this system and expect to make other tools available as they are * completed. * * ANTLR 1.33 * Terence Parr * Parr Research Corporation * with Purdue University and AHPCRC, University of Minnesota * 1989-2001 */ #include #include "pcctscfg.h" #include #ifdef PCCTS_USE_STDARG #include #else #include #endif #include "set.h" #include "syn.h" #include "hash.h" #include "generic.h" #include "dlgdef.h" /* ick! globals. Used by permute() to track which elements of a set have been used */ static int *findex; set *fset; /* MR11 make global */ static unsigned **ftbl; static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */ int ConstrainSearch; int maxk; /* set to initial k upon tree construction request */ /* MR11 make global */ static Tree *FreeList = NULL; #ifdef __USE_PROTOS static int tmember_of_context(Tree *, Predicate *); #else static int tmember_of_context(); #endif #if TREE_DEBUG set set_of_tnodes_in_use; int stop_on_tnode_seq_number=(-1); /* (-1) to disable */ #endif /* Do root * Then each sibling */ void #ifdef __USE_PROTOS preorder( Tree *tree ) #else preorder( tree ) Tree *tree; #endif { if ( tree == NULL ) return; if ( tree->down != NULL ) fprintf(stderr, " ("); if ( tree->token == ALT ) fprintf(stderr, " ALT"); else fprintf(stderr, " %s", TerminalString(tree->token)); if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk); preorder(tree->down); if ( tree->down != NULL ) fprintf(stderr, " )"); preorder(tree->right); } #ifdef __USE_PROTOS int MR_tree_matches_constraints(int k,set * constrain,Tree *t) #else int MR_tree_matches_constraints(k,constrain,t) int k; set * constrain; Tree * t; #endif { int i; Tree *u; if (k == 0) return 1; /* for testing guard predicates: if the guard tree is shorter than the constraint then it is a match. The reason is that a guard of (A B) should be equivalent to a guard of (A B . . .) where "." matches every token. Thus a match which runs out of tree before constraint is a match. */ if (t == NULL) return 1; require (set_deg(constrain[0]) == 1, "MR_tree_matches_constraints: set_deg != 1"); i=set_int(constrain[0]); if (t->token != i) return 0; if (k-1 == 0) return 1; for (u=t->down; u != NULL; u=u->right) { if (MR_tree_matches_constraints(k-1,&constrain[1],u)) { return 1; }; }; return 0; } /* check the depth of each primary sibling to see that it is exactly * k deep. e.g.; * * ALT * | * A ------- B * | | * C -- D E * * Remove all branches <= k deep. * * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work. */ static int pruneCount=0; static int prunePeak=200; Tree * #ifdef __USE_PROTOS prune( Tree *t, int k ) #else prune( t, k ) Tree *t; int k; #endif { pruneCount++; if (pruneCount > prunePeak+100) { prunePeak=pruneCount; #if 0 *** fprintf(stderr,"pruneCount=%d\n",pruneCount); /*** preorder(t); ***/ *** fprintf(stderr,"\n",pruneCount); #endif }; if ( t == NULL ) { pruneCount--; return NULL; }; if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree"); if ( t->right!=NULL ) t->right = prune(t->right, k); if ( k>1 ) { if ( t->down!=NULL ) t->down = prune(t->down, k-1); if ( t->down == NULL ) { Tree *r = t->right; t->right = NULL; Tfree(t); pruneCount--; return r; } } pruneCount--; return t; } /* build a tree (root child1 child2 ... NULL) */ #ifdef PCCTS_USE_STDARG Tree *tmake(Tree *root, ...) #else Tree *tmake(va_alist) va_dcl #endif { Tree *w; va_list ap; Tree *child, *sibling=NULL, *tail=NULL; #ifndef PCCTS_USE_STDARG Tree *root; #endif #ifdef PCCTS_USE_STDARG va_start(ap, root); #else va_start(ap); root = va_arg(ap, Tree *); #endif child = va_arg(ap, Tree *); while ( child != NULL ) { #ifdef DUM /* added "find end of child" thing TJP March 1994 */ for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */ #else w = child; #endif if ( sibling == NULL ) {sibling = child; tail = w;} else {tail->right = child; tail = w;} child = va_arg(ap, Tree *); } /* was "root->down = sibling;" */ if ( root==NULL ) root = sibling; else root->down = sibling; va_end(ap); return root; } Tree * #ifdef __USE_PROTOS tnode( int tok ) #else tnode( tok ) int tok; #endif { Tree *p, *newblk; static int n=0; if ( FreeList == NULL ) { /*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/ if ( TreeResourceLimit > 0 ) { if ( (n+TreeBlockAllocSize) >= TreeResourceLimit ) { fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline); fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n", CurAmbigAlt1, CurAmbigAlt2, CurAmbigbtype); exit(PCCTS_EXIT_FAILURE); } } newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree)); if ( newblk == NULL ) { fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline); fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n", CurAmbigAlt1, CurAmbigAlt2, CurAmbigbtype); exit(PCCTS_EXIT_FAILURE); } n += TreeBlockAllocSize; for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++) { p->right = FreeList; /* add all new Tree nodes to Free List */ FreeList = p; } } p = FreeList; FreeList = FreeList->right; /* remove a tree node */ p->right = NULL; /* zero out ptrs */ p->down = NULL; p->token = tok; TnodesAllocated++; /* MR10 */ TnodesInUse++; /* MR10 */ if (TnodesInUse > TnodesPeak) TnodesPeak=TnodesInUse; /* MR10 */ #ifdef TREE_DEBUG require(!p->in_use, "tnode: node in use!"); p->in_use = 1; p->seq=TnodesAllocated; set_orel( (unsigned) TnodesAllocated,&set_of_tnodes_in_use); if (stop_on_tnode_seq_number == p->seq) { fprintf(stderr,"\n*** just allocated tnode #%d ***\n", stop_on_tnode_seq_number); }; #endif return p; } static Tree * #ifdef __USE_PROTOS eofnode( int k ) #else eofnode( k ) int k; #endif { Tree *t=NULL; int i; for (i=1; i<=k; i++) { t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL); } return t; } void #ifdef __USE_PROTOS _Tfree( Tree *t ) #else _Tfree( t ) Tree *t; #endif { if ( t!=NULL ) { #ifdef TREE_DEBUG if (t->seq == stop_on_tnode_seq_number) { fprintf(stderr,"\n*** just freed tnode #%d ***\n",t->seq); }; require(t->in_use, "_Tfree: node not in use!"); t->in_use = 0; set_rm( (unsigned) t->seq,set_of_tnodes_in_use); #endif t->right = FreeList; FreeList = t; TnodesInUse--; /* MR10 */ } } /* tree duplicate */ Tree * #ifdef __USE_PROTOS tdup( Tree *t ) #else tdup( t ) Tree *t; #endif { Tree *u; if ( t == NULL ) return NULL; u = tnode(t->token); u->v.rk = t->v.rk; u->right = tdup(t->right); u->down = tdup(t->down); return u; } /* tree duplicate (assume tree is a chain downwards) */ Tree * #ifdef __USE_PROTOS tdup_chain( Tree *t ) #else tdup_chain( t ) Tree *t; #endif { Tree *u; if ( t == NULL ) return NULL; u = tnode(t->token); u->v.rk = t->v.rk; u->down = tdup(t->down); return u; } Tree * #ifdef __USE_PROTOS tappend( Tree *t, Tree *u ) #else tappend( t, u ) Tree *t; Tree *u; #endif { Tree *w; /*** fprintf(stderr, "tappend("); *** preorder(t); fprintf(stderr, ","); *** preorder(u); fprintf(stderr, " )\n"); */ if ( t == NULL ) return u; if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u); for (w=t; w->right!=NULL; w=w->right) {;} w->right = u; return t; } /* dealloc all nodes in a tree */ void #ifdef __USE_PROTOS Tfree( Tree *t ) #else Tfree( t ) Tree *t; #endif { if ( t == NULL ) return; Tfree( t->down ); Tfree( t->right ); _Tfree( t ); } /* find all children (alts) of t that require remaining_k nodes to be LL_k * tokens long. * * t-->o * | * a1--a2--...--an <-- LL(1) tokens * | | | * b1 b2 ... bn <-- LL(2) tokens * | | | * . . . * . . . * z1 z2 ... zn <-- LL(LL_k) tokens * * We look for all [Ep] needing remaining_k nodes and replace with u. * u is not destroyed or actually used by the tree (a copy is made). */ Tree * #ifdef __USE_PROTOS tlink( Tree *t, Tree *u, int remaining_k ) #else tlink( t, u, remaining_k ) Tree *t; Tree *u; int remaining_k; #endif { Tree *p; require(remaining_k!=0, "tlink: bad tree"); if ( t==NULL ) return NULL; /*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/ if ( t->token == EpToken && t->v.rk == remaining_k ) { require(t->down==NULL, "tlink: invalid tree"); if ( u == NULL ) { /* MR10 */ Tree *tt=t->right; /* MR10 */ _Tfree(t); /* MR10 */ return tt; }; p = tdup( u ); p->right = t->right; _Tfree( t ); return p; } t->down = tlink(t->down, u, remaining_k); t->right = tlink(t->right, u, remaining_k); return t; } /* remove as many ALT nodes as possible while still maintaining semantics */ Tree * #ifdef __USE_PROTOS tshrink( Tree *t ) #else tshrink( t ) Tree *t; #endif { if ( t == NULL ) return NULL; t->down = tshrink( t->down ); t->right = tshrink( t->right ); if ( t->down == NULL ) { if ( t->token == ALT ) { Tree *u = t->right; _Tfree(t); return u; /* remove useless alts */ } return t; } /* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */ if ( t->token == ALT && t->down->right == NULL) { Tree *u = t->down; u->right = t->right; _Tfree( t ); return u; } /* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */ if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL ) { Tree *u = t->down->down; _Tfree( t->down ); t->down = u; return t; } return t; } Tree * #ifdef __USE_PROTOS tflatten( Tree *t ) #else tflatten( t ) Tree *t; #endif { if ( t == NULL ) return NULL; t->down = tflatten( t->down ); t->right = tflatten( t->right ); if ( t->down == NULL ) return t; if ( t->token == ALT ) { Tree *u; /* find tail of children */ for (u=t->down; u->right!=NULL; u=u->right) {;} u->right = t->right; u = t->down; _Tfree( t ); return u; } return t; } Tree * #ifdef __USE_PROTOS tJunc( Junction *p, int k, set *rk ) #else tJunc( p, k, rk ) Junction *p; int k; set *rk; #endif { Tree *t=NULL, *u=NULL; Junction *alt; Tree *tail=NULL, *r; #ifdef DBG_TRAV fprintf(stderr, "tJunc(%d): %s in rule %s\n", k, decodeJType[p->jtype], ((Junction *)p)->rname); #endif /* 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 */ return NULL; /* MR14 */ } if ( p->jtype==aLoopBlk || p->jtype==RuleBlk || p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk ) { if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) { require(p->lock!=NULL, "rJunc: lock array is NULL"); if ( p->lock[k] ) return NULL; p->lock[k] = TRUE; } /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p); /* MR10 */ }; TRAV(p->p1, k, rk, tail); /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack); /* MR10 */ }; if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;} r = tmake(tnode(ALT), tail, NULL); for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2) { /* if this is one of the added optional alts for (...)+ then break */ if ( alt->ignore ) break; if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;} else { /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p); /* MR10 */ }; TRAV(alt->p1, k, rk, tail->right); /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack); /* MR10 */ }; if ( tail->right != NULL ) tail = tail->right; } } if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE; #ifdef DBG_TREES fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n"); #endif if ( r->down == NULL ) {_Tfree(r); return NULL;} return r; } if ( p->jtype==EndRule ) { if ( p->halt ) /* don't want FOLLOW here? */ { /**** if ( ContextGuardTRAV ) return NULL; ****/ set_orel( (unsigned) k, rk); /* indicate this k value needed */ /* MR10 cast */ t = tnode(EpToken); t->v.rk = k; return t; } require(p->lock!=NULL, "rJunc: lock array is NULL"); if ( p->lock[k] ) return NULL; /* if no FOLLOW assume k EOF's */ if ( p->p1 == NULL ) return eofnode(k); p->lock[k] = TRUE; } /* MR14 */ if (p->p1 != NULL && p->guess && 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 */ } if ( p->p2 == NULL ) { /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p); /* MR10 */ }; /* M14 */ if (p->guess_analysis_point != NULL) { /* M14 */ TRAV(p->guess_analysis_point, k, rk,t); /* M14 */ } else { TRAV(p->p1, k, rk,t); /* M14 */ } /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack); /* MR10 */ }; if ( p->jtype==EndRule ) p->lock[k]=FALSE; return t; } /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p); /* MR10 */ }; /* M14 */ if (p->guess_analysis_point != NULL) { /* M14 */ TRAV(p->guess_analysis_point, k, rk,t); /* M14 */ } else { TRAV(p->p1, k, rk,t); /* M14 */ } /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack); /* MR10 */ }; if ( p->jtype!=RuleBlk && /* MR14 */ !p->guess) TRAV(p->p2, k, rk, u); if ( p->jtype==EndRule ) p->lock[k] = FALSE;/* unlock node */ if ( t==NULL ) return tmake(tnode(ALT), u, NULL); return tmake(tnode(ALT), t, u, NULL); } Tree * #ifdef __USE_PROTOS tRuleRef( RuleRefNode *p, int k, set *rk_out ) #else tRuleRef( p, k, rk_out ) RuleRefNode *p; int k; set *rk_out; #endif { int k2; Tree *t=NULL, *u=NULL; Junction *r; set rk, rk2; int save_halt; RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text); #ifdef DBG_TRAV fprintf(stderr, "tRuleRef: %s\n", p->text); #endif if ( q == NULL ) { TRAV(p->next, k, rk_out, t);/* ignore undefined rules */ return t; } rk = rk2 = empty; if (RulePtr == NULL) fatal("RulePtr==NULL"); r = RulePtr[q->rulenum]; if ( r->lock[k] ) return NULL; save_halt = r->end->halt; r->end->halt = TRUE; /* don't let reach fall off end of rule here */ /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p); /* MR10 */ }; TRAV(r, k, &rk, t); /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ MR_pointerStackPop(&MR_BackTraceStack); /* MR10 */ }; r->end->halt = save_halt; #ifdef DBG_TREES fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n"); #endif t = tshrink( t ); while ( !set_nil(rk) ) { /* any k left to do? if so, link onto tree */ k2 = set_int(rk); set_rm(k2, rk); /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p); /* MR10 */ }; TRAV(p->next, k2, &rk2, u); /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ MR_pointerStackPop(&MR_BackTraceStack); /* MR10 */ }; t = tlink(t, u, k2); /* any alts missing k2 toks, add u onto end */ Tfree(u); /* MR10 */ } set_free(rk); /* rk is empty, but free its memory */ set_orin(rk_out, rk2); /* remember what we couldn't do */ set_free(rk2); return t; } Tree * #ifdef __USE_PROTOS tToken( TokNode *p, int k, set *rk ) #else tToken( p, k, rk ) TokNode *p; int k; set *rk; #endif { Tree *t=NULL, *tset=NULL, *u; if (ConstrainSearch) { if (MR_AmbSourceSearch) { require(constrain>=fset&&constrain<=&(fset[CLL_k]),"tToken: constrain is not a valid set"); } else { require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set"); }; constrain = &fset[maxk-k+1]; } #ifdef DBG_TRAV fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token)); if ( ConstrainSearch ) { fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n"); } #endif /* is it a meta token (set of tokens)? */ if ( !set_nil(p->tset) ) { unsigned e=0; set a; Tree *n, *tail = NULL; if ( ConstrainSearch ) { a = set_and(p->tset, *constrain); if (set_nil(a)) { /* MR10 */ set_free(a); /* MR11 */ return NULL; /* MR10 */ }; /* MR10 */ } else { a = set_dup(p->tset); }; for (; !set_nil(a); set_rm(e, a)) { e = set_int(a); n = tnode(e); if ( tset==NULL ) { tset = n; tail = n; } else { tail->right = n; tail = n; } } set_free( a ); } else if ( ConstrainSearch && !set_el(p->token, *constrain) ) { /* fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token), k);*/ return NULL; } else { tset = tnode( p->token ); }; /* MR10 */ if (MR_MaintainBackTrace) { /* MR10 */ if (k == 1) { /* MR10 */ MR_pointerStackPush(&MR_BackTraceStack,p); /* MR13 */ if (MR_SuppressSearch) { /* MR13 */ MR_suppressSearchReport(); /* MR13 */ } else { /* MR10 */ MR_backTraceReport(); /* MR13 */ }; /* MR10 */ MR_pointerStackPop(&MR_BackTraceStack); /* MR11 */ Tfree(tset); /* MR11 */ return NULL; /* MR10 */ }; /* MR10 */ }; if ( k == 1 ) return tset; if (MR_MaintainBackTrace) { MR_pointerStackPush(&MR_BackTraceStack,p); }; TRAV(p->next, k-1, rk, t); if (MR_MaintainBackTrace) { Tfree(t); Tfree(tset); MR_pointerStackPop(&MR_BackTraceStack); return NULL; }; /* here, we are positive that, at least, this tree will not contribute * to the LL(2) tree since it will be too shallow, IF t==NULL. * If doing a context guard walk, then don't prune. */ if ( t == NULL && !ContextGuardTRAV ) /* tree will be too shallow */ { if ( tset!=NULL ) Tfree( tset ); return NULL; } #ifdef DBG_TREES fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n"); #endif /* if single token root, then just make new tree and return */ /* MR10 - set_nil(p->tset) isn't a good test because of ConstraintSearch */ if (tset->right == NULL) return tmake(tset, t, NULL); /* MR10 */ /* here we must make a copy of t as a child of each element of the tset; * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) ) */ for (u=tset; u!=NULL; u=u->right) { /* make a copy of t and hook it onto bottom of u */ u->down = tdup(t); } Tfree( t ); #ifdef DBG_TREES fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n"); #endif return tset; } Tree * #ifdef __USE_PROTOS tAction( ActionNode *p, int k, set *rk ) #else tAction( p, k, rk ) ActionNode *p; int k; set *rk; #endif { Tree *t=NULL; set *save_fset=NULL; int i; /* fprintf(stderr, "tAction\n"); */ /* An MR_SuppressSearch is looking for things that can be reached even when the predicate is false. There are three kinds of predicates: plain: r1: <

>? r2 guarded: r1: (A)? => <

>? r2 ampersand style: r1: (A)? && <

>? r2 Of the three kinds of predicates, only a guard predicate has things which are reachable even when the predicate is false. To be reachable the constraint must *not* match the guard. */ if (p->is_predicate && MR_SuppressSearch) { Predicate *pred=p->guardpred; if (pred == NULL) { t=NULL; goto EXIT; }; constrain = &fset[maxk-k+1]; if (pred->k == 1) { set dif; dif=set_dif(*constrain,pred->scontext[1]); if (set_nil(dif)) { set_free(dif); t=NULL; goto EXIT; }; set_free(dif); } else { if (MR_tree_matches_constraints(k,constrain,pred->tcontext)) { t=NULL; goto EXIT; }; } }; /* The ampersand predicate differs from the other predicates because its first set is a subset of the first set behind the predicate r1: (A)? && <

>? r2 ; r2: A | B; In this case first[1] of r1 is A, even though first[1] of r2 is {A B}. */ if (p->is_predicate && p->ampersandPred != NULL) { Predicate *pred=p->ampersandPred; Tree *tAND; Tree *tset; if (k <= pred->k) { if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p); TRAV(p->guardNodes,k,rk,t); if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack); return t; } else { require (k>1,"tAction for ampersandpred: k <= 1"); if (ConstrainSearch) { if (MR_AmbSourceSearch) { require(constrain>=fset&&constrain<=&(fset[CLL_k]), "tToken: constrain is not a valid set"); } else { require(constrain>=fset&&constrain<=&(fset[LL_k]), "tToken: constrain is not a valid set"); }; save_fset=(set *) calloc (CLL_k+1,sizeof(set)); require (save_fset != NULL,"tAction save_fset alloc"); for (i=1; i <= CLL_k ; i++) { save_fset[i]=set_dup(fset[i]); }; if (pred->k == 1) { constrain = &fset[maxk-k+1]; set_andin(constrain,pred->scontext[1]); if (set_nil(*constrain)) { t=NULL; goto EXIT; }; } else { constrain = &fset[maxk-k+1]; if (! MR_tree_matches_constraints(pred->k,constrain,pred->tcontext)) { t=NULL; goto EXIT; }; /* end loop on i */ }; /* end loop on pred scontext/tcontext */ }; /* end if on k > pred->k */ }; /* end if on constrain search */ TRAV(p->next,k,rk,t); if (t != NULL) { t=tshrink(t); t=tflatten(t); t=tleft_factor(t); if (pred->tcontext != NULL) { tAND=MR_computeTreeAND(t,pred->tcontext); } else { tset=MR_make_tree_from_set(pred->scontext[1]); tAND=MR_computeTreeAND(t,tset); Tfree(tset); }; Tfree(t); t=tAND; }; goto EXIT; }; /* end if on ampersand predicate */ TRAV(p->next,k,rk,t); EXIT: if (save_fset != NULL) { for (i=1 ; i <= CLL_k ; i++) { set_free(fset[i]); fset[i]=save_fset[i]; }; free ( (char *) save_fset); }; return t; } /* see if e exists in s as a possible input permutation (e is always a chain) */ int #ifdef __USE_PROTOS tmember( Tree *e, Tree *s ) #else tmember( e, s ) Tree *e; Tree *s; #endif { if ( e==NULL||s==NULL ) return 0; /** fprintf(stderr, "tmember("); *** preorder(e); fprintf(stderr, ","); *** preorder(s); fprintf(stderr, " )\n"); */ if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down); if ( e->token!=s->token ) { if ( s->right==NULL ) return 0; return tmember(e, s->right); } if ( e->down==NULL && s->down == NULL ) return 1; if ( tmember(e->down, s->down) ) return 1; if ( s->right==NULL ) return 0; return tmember(e, s->right); } /* see if e exists in s as a possible input permutation (e is always a chain); * Only check s to the depth of e. In other words, 'e' can be a shorter * sequence than s. */ int #ifdef __USE_PROTOS tmember_constrained( Tree *e, Tree *s) #else tmember_constrained( e, s ) Tree *e; Tree *s; #endif { if ( e==NULL||s==NULL ) return 0; /** fprintf(stderr, "tmember_constrained("); *** preorder(e); fprintf(stderr, ","); *** preorder(s); fprintf(stderr, " )\n"); **/ if ( s->token == ALT && s->right == NULL ) return tmember_constrained(e, s->down); if ( e->token!=s->token ) { if ( s->right==NULL ) return 0; return tmember_constrained(e, s->right); } if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */ if ( tmember_constrained(e->down, s->down) ) return 1; if ( s->right==NULL ) return 0; return tmember_constrained(e, s->right); } /* combine (? (A t) ... (A u) ...) into (? (A t u)) */ Tree * #ifdef __USE_PROTOS tleft_factor( Tree *t ) #else tleft_factor( t ) Tree *t; #endif { Tree *u, *v, *trail, *w; /* left-factor what is at this level */ if ( t == NULL ) return NULL; for (u=t; u!=NULL; u=u->right) { trail = u; v=u->right; while ( v!=NULL ) { if ( u->token == v->token ) { if ( u->down!=NULL ) { for (w=u->down; w->right!=NULL; w=w->right) {;} w->right = v->down; /* link children together */ } else u->down = v->down; trail->right = v->right; /* unlink factored node */ _Tfree( v ); v = trail->right; } else {trail = v; v=v->right;} } } /* left-factor what is below */ for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down ); return t; } /* remove the permutation p from t if present */ Tree * #ifdef __USE_PROTOS trm_perm( Tree *t, Tree *p ) #else trm_perm( t, p ) Tree *t; Tree *p; #endif { /* fprintf(stderr, "trm_perm("); preorder(t); fprintf(stderr, ","); preorder(p); fprintf(stderr, " )\n"); */ if ( t == NULL || p == NULL ) return NULL; if ( t->token == ALT ) { t->down = trm_perm(t->down, p); if ( t->down == NULL ) /* nothing left below, rm cur node */ { Tree *u = t->right; _Tfree( t ); return trm_perm(u, p); } t->right = trm_perm(t->right, p); /* look for more instances of p */ return t; } if ( p->token != t->token ) /* not found, try a sibling */ { t->right = trm_perm(t->right, p); return t; } t->down = trm_perm(t->down, p->down); if ( t->down == NULL ) /* nothing left below, rm cur node */ { Tree *u = t->right; _Tfree( t ); return trm_perm(u, p); } t->right = trm_perm(t->right, p); /* look for more instances of p */ return t; } /* add the permutation 'perm' to the LL_k sets in 'fset' */ void #ifdef __USE_PROTOS tcvt( set *fset, Tree *perm ) #else tcvt( fset, perm ) set *fset; Tree *perm; #endif { if ( perm==NULL ) return; set_orel(perm->token, fset); tcvt(fset+1, perm->down); } /* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1]) * as a child. */ Tree * #ifdef __USE_PROTOS permute( int k, int max_k ) #else permute( k, max_k ) int k, max_k; #endif { Tree *t, *u; if ( k>max_k ) return NULL; if ( ftbl[k][findex[k]] == nil ) return NULL; t = permute(k+1, max_k); if ( t==NULL&&k maxk will have to change. */ Tree * #ifdef __USE_PROTOS VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig ) #else VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig ) Junction *alt1; Junction *alt2; unsigned **ft; set *fs; Tree **t; Tree **u; int *numAmbig; #endif { set rk; Tree *perm, *ambig=NULL; Junction *p; int k; int tnodes_at_start=TnodesAllocated; int tnodes_at_end; int tnodes_used; set *save_fs; int j; save_fs=(set *) calloc(CLL_k+1,sizeof(set)); require(save_fs != NULL,"save_fs calloc"); for (j=0; j <= CLL_k ; j++) save_fs[j]=set_dup(fs[j]); maxk = LL_k; /* NOTE: for now, we look for LL_k */ ftbl = ft; fset = fs; constrain = &(fset[1]); findex = (int *) calloc(LL_k+1, sizeof(int)); if ( findex == NULL ) { fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline); fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n", CurAmbigAlt1, CurAmbigAlt2, CurAmbigbtype); exit(PCCTS_EXIT_FAILURE); } for (k=1; k<=LL_k; k++) findex[k] = 0; rk = empty; ConstrainSearch = 1; /* consider only tokens in ambig sets */ p = analysis_point((Junction *)alt1->p1); TRAV(p, LL_k, &rk, *t); *t = tshrink( *t ); *t = tflatten( *t ); *t = tleft_factor( *t ); /* MR10 */ *t = prune(*t, LL_k); *t = tleft_factor( *t ); /*** fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/ if ( *t == NULL ) { /*** fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/ Tfree( *t ); /* kill if impossible to have ambig */ *t = NULL; } p = analysis_point((Junction *)alt2->p1); TRAV(p, LL_k, &rk, *u); *u = tshrink( *u ); *u = tflatten( *u ); *t = tleft_factor( *t ); /* MR10 */ *u = prune(*u, LL_k); *u = tleft_factor( *u ); /* fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/ if ( *u == NULL ) { /* fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/ Tfree( *u ); *u = NULL; } for (k=1; k<=LL_k; k++) set_clr( fs[k] ); ambig = tnode(ALT); k = 0; if ( *t!=NULL && *u!=NULL ) { while ( (perm=permute(1,LL_k))!=NULL ) { /* fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/ if ( tmember(perm, *t) && tmember(perm, *u) ) { /* fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/ k++; perm->right = ambig->down; ambig->down = perm; tcvt(&(fs[1]), perm); } else Tfree( perm ); } } for (j=0; j <= CLL_k ; j++) fs[j]=save_fs[j]; free( (char *) save_fs); tnodes_at_end=TnodesAllocated; tnodes_used=tnodes_at_end - tnodes_at_start; if (TnodesReportThreshold > 0 && tnodes_used > TnodesReportThreshold) { fprintf(stdout,"There were %d tuples whose ambiguity could not be resolved by full lookahead\n",k); fprintf(stdout,"There were %d tnodes created to resolve ambiguity between:\n\n",tnodes_used); fprintf(stdout," Choice 1: %s line %d file %s\n", MR_ruleNamePlusOffset( (Node *) alt1),alt1->line,FileStr[alt1->file]); fprintf(stdout," Choice 2: %s line %d file %s\n", MR_ruleNamePlusOffset( (Node *) alt2),alt2->line,FileStr[alt2->file]); for (j=1; j <= CLL_k ; j++) { fprintf(stdout,"\n Intersection of lookahead[%d] sets:\n",j); MR_dumpTokenSet(stdout,2,fs[j]); }; fprintf(stdout,"\n"); }; *numAmbig = k; if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;} free( (char *)findex ); /* fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/ return ambig; } static Tree * #ifdef __USE_PROTOS bottom_of_chain( Tree *t ) #else bottom_of_chain( t ) Tree *t; #endif { if ( t==NULL ) return NULL; for (; t->down != NULL; t=t->down) {;} return t; } /* * Make a tree from k sets where the degree of the first k-1 sets is 1. */ Tree * #ifdef __USE_PROTOS make_tree_from_sets( set *fset1, set *fset2 ) #else make_tree_from_sets( fset1, fset2 ) set *fset1; set *fset2; #endif { set inter; int i; Tree *t=NULL, *n, *u; unsigned *p,*q; require(LL_k>1, "make_tree_from_sets: LL_k must be > 1"); /* do the degree 1 sets first */ for (i=1; i<=LL_k-1; i++) { inter = set_and(fset1[i], fset2[i]); require(set_deg(inter)==1, "invalid set to tree conversion"); n = tnode(set_int(inter)); if (t==NULL) t=n; else tmake(t, n, NULL); set_free(inter); } /* now add the chain of tokens at depth k */ u = bottom_of_chain(t); inter = set_and(fset1[LL_k], fset2[LL_k]); if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq"); /* first one is linked to bottom, then others are sibling linked */ n = tnode(*p++); u->down = n; u = u->down; while ( *p != nil ) { n = tnode(*p); u->right = n; u = u->right; p++; } free((char *)q); return t; } /* create and return the tree of lookahead k-sequences that are in t, but not * in the context of predicates in predicate list p. */ Tree * #ifdef __USE_PROTOS tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 ) #else tdif( ambig_tuples, p, fset1, fset2 ) Tree *ambig_tuples; Predicate *p; set *fset1; set *fset2; #endif { unsigned **ft; Tree *dif=NULL; Tree *perm; set b; int i,k; if ( p == NULL ) return tdup(ambig_tuples); ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *)); require(ft!=NULL, "cannot allocate ft"); for (i=1; i<=CLL_k; i++) { b = set_and(fset1[i], fset2[i]); ft[i] = set_pdq(b); set_free(b); } findex = (int *) calloc(LL_k+1, sizeof(int)); if ( findex == NULL ) { fatal_internal("out of memory in tdif while checking predicates"); } for (k=1; k<=LL_k; k++) findex[k] = 0; #ifdef DBG_TRAV fprintf(stderr, "tdif_%d[", p->k); preorder(ambig_tuples); fprintf(stderr, ","); preorder(p->tcontext); fprintf(stderr, "] ="); #endif ftbl = ft; while ( (perm=permute(1,p->k))!=NULL ) { #ifdef DBG_TRAV fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n"); #endif if ( tmember_constrained(perm, ambig_tuples) && !tmember_of_context(perm, p) ) { #ifdef DBG_TRAV fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n"); #endif k++; if ( dif==NULL ) dif = perm; else { perm->right = dif; dif = perm; } } else Tfree( perm ); } #ifdef DBG_TRAV preorder(dif); fprintf(stderr, "\n"); #endif for (i=1; i<=CLL_k; i++) free( (char *)ft[i] ); free((char *)ft); free((char *)findex); return dif; } /* is lookahead sequence t a member of any context tree for any * predicate in p? */ static int #ifdef __USE_PROTOS tmember_of_context( Tree *t, Predicate *p ) #else tmember_of_context( t, p ) Tree *t; Predicate *p; #endif { for (; p!=NULL; p=p->right) { if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST ) return tmember_of_context(t, p->down); if ( tmember_constrained(t, p->tcontext) ) return 1; if ( tmember_of_context(t, p->down) ) return 1; } return 0; } int #ifdef __USE_PROTOS is_single_tuple( Tree *t ) #else is_single_tuple( t ) Tree *t; #endif { if ( t == NULL ) return 0; if ( t->right != NULL ) return 0; if ( t->down == NULL ) return 1; return is_single_tuple(t->down); } /* MR10 Check that a context guard contains only allowed things */ /* MR10 (mainly token references). */ #ifdef __USE_PROTOS int contextGuardOK(Node *p,int h,int *hmax) #else int contextGuardOK(p,h,hmax) Node *p; int h; int *hmax; #endif { Junction *j; TokNode *tn; if (p == NULL) return 1; if (p->ntype == nToken) { h++; if (h > *hmax) *hmax=h; tn=(TokNode *)p; if (tn->el_label != NULL) { warnFL(eMsg1("a label (\"%s\") for a context guard element is meaningless",tn->el_label), FileStr[p->file],p->line); }; return contextGuardOK( ( (TokNode *) p)->next,h,hmax); } else if (p->ntype == nAction) { goto Fail; } else if (p->ntype == nRuleRef) { goto Fail; } else { require (p->ntype == nJunction,"Unexpected ntype"); j=(Junction *) p; if (j->jtype != Generic && j->jtype != aSubBlk && /* pretty sure this one is allowed */ /**** j->jtype != aOptBlk && ****/ /* pretty sure this one is allowed */ /* MR11 not any more ! */ j->jtype != EndBlk) { errFL("A context guard may not contain an option block: {...} or looping block: (...)* or (...)+", FileStr[p->file],p->line); contextGuardOK(j->p1,h,hmax); return 0; }; /* do both p1 and p2 so use | rather than || */ return contextGuardOK(j->p2,h,hmax) | contextGuardOK(j->p1,h,hmax); }; Fail: errFL("A context guard may contain only Token references - guard will be ignored", FileStr[p->file],p->line); contextGuardOK( ( (ActionNode *) p)->next,h,hmax); return 0; } /* * Look at a (...)? generalized-predicate context-guard and compute * either a lookahead set (k==1) or a lookahead tree for k>1. The * k level is determined by the guard itself rather than the LL_k * variable. For example, ( A B )? is an LL(2) guard and ( ID )? * is an LL(1) guard. For the moment, you can only have a single * tuple in the guard. Physically, the block must look like this * --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o-- * An error is printed for any other type. */ Predicate * #ifdef __USE_PROTOS computePredFromContextGuard(Graph blk,int *msgDone) /* MR10 */ #else computePredFromContextGuard(blk,msgDone) /* MR10 */ Graph blk; int *msgDone; /* MR10 */ #endif { Junction *junc = (Junction *)blk.left, *p; Tree *t=NULL; Predicate *pred = NULL; set scontext, rk; int ok; int hmax=0; require(junc!=NULL && junc->ntype == nJunction, "bad context guard"); /* MR10 Check for anything other than Tokens and generic junctions */ *msgDone=0; /* MR10 */ ok=contextGuardOK( (Node *)junc,0,&hmax); /* MR10 */ if (! ok) { /* MR10 */ *msgDone=1; /* MR10 */ return NULL; /* MR10 */ }; /* MR10 */ if (hmax == 0) { errFL("guard is 0 tokens long",FileStr[junc->file],junc->line); /* MR11 */ *msgDone=1; return NULL; }; if (hmax > CLL_k) { /* MR10 */ errFL(eMsgd2("guard is %d tokens long - lookahead is limited to max(k,ck)==%d", /* MR10 */ hmax,CLL_k), /* MR10 */ FileStr[junc->file],junc->line); /* MR10 */ *msgDone=1; /* MR10 */ return NULL; /* MR10 */ }; /* MR10 */ rk = empty; p = junc; pred = new_pred(); pred->k = hmax; /* MR10 should be CLL_k, not LLK ? */ if (hmax > 1 ) /* MR10 was LL_k */ { ConstrainSearch = 0; ContextGuardTRAV = 1; TRAV(p, hmax, &rk, t); /* MR10 was LL_k */ ContextGuardTRAV = 0; set_free(rk); t = tshrink( t ); t = tflatten( t ); t = tleft_factor( t ); /* fprintf(stderr, "ctx guard:"); preorder(t); fprintf(stderr, "\n"); */ pred->tcontext = t; } else { REACH(p, 1, &rk, scontext); require(set_nil(rk), "rk != nil"); set_free(rk); /* fprintf(stderr, "LL(1) ctx guard is:"); s_fprT(stderr, scontext); fprintf(stderr, "\n"); */ pred->scontext[1] = scontext; } list_add(&ContextGuardPredicateList,pred); /* MR13 */ return pred; } /* MR13 When the context guard is originally computed the meta-tokens are not known. */ #ifdef __USE_PROTOS void recomputeContextGuard(Predicate *pred) #else void recomputeContextGuard(pred) Predicate *pred; #endif { Tree * t=NULL; set scontext; set rk; ActionNode * actionNode; Junction * p; actionNode=pred->source; require (actionNode != NULL,"context predicate's source == NULL"); p=actionNode->guardNodes; require (p != NULL,"context predicate's guardNodes == NULL"); rk = empty; if (pred->k > 1 ) { ConstrainSearch = 0; ContextGuardTRAV = 1; TRAV(p, pred->k, &rk, t); ContextGuardTRAV = 0; set_free(rk); t = tshrink( t ); t = tflatten( t ); t = tleft_factor( t ); Tfree(pred->tcontext); pred->tcontext = t; } else { REACH(p, 1, &rk, scontext); require(set_nil(rk), "rk != nil"); set_free(rk); set_free(pred->scontext[1]); pred->scontext[1] = scontext; } } /* MR11 - had enough of flags yet ? */ int MR_AmbSourceSearch=0; int MR_AmbSourceSearchGroup=0; int MR_AmbSourceSearchChoice=0; int MR_AmbSourceSearchLimit=0; int MR_matched_AmbAidRule=0; static set *matchSets[2]={NULL,NULL}; static int *tokensInChain=NULL; static Junction *MR_AmbSourceSearchJ[2]; void MR_traceAmbSourceKclient() { int i; set *save_fset; int save_ConstrainSearch; set incomplete; Tree *t; if (matchSets[0] == NULL) { matchSets[0]=(set *) calloc (CLL_k+1,sizeof(set)); require (matchSets[0] != NULL,"matchSets[0] alloc"); matchSets[1]=(set *) calloc (CLL_k+1,sizeof(set)); require (matchSets[1] != NULL,"matchSets[1] alloc"); }; for (i=1 ; i <= MR_AmbSourceSearchLimit ; i++) { set_clr(matchSets[0][i]); set_orel( (unsigned) tokensInChain[i], &matchSets[0][i]); set_clr(matchSets[1][i]); set_orel( (unsigned) tokensInChain[i], &matchSets[1][i]); }; save_fset=fset; save_ConstrainSearch=ConstrainSearch; for (i=0 ; i < 2 ; i++) { #if 0 ** fprintf(stdout," Choice:%d Depth:%d ",i+1,MR_AmbSourceSearchLimit); ** fprintf(stdout,"("); ** for (j=1 ; j <= MR_AmbSourceSearchLimit ; j++) { ** if (j != 1) fprintf(stdout," "); ** fprintf(stdout,"%s",TerminalString(tokensInChain[j])); ** }; ** fprintf(stdout,")\n\n"); #endif fset=matchSets[i]; MR_AmbSourceSearch=1; MR_MaintainBackTrace=1; MR_AmbSourceSearchChoice=i; ConstrainSearch=1; maxk = MR_AmbSourceSearchLimit; incomplete=empty; t=NULL; constrain = &(fset[1]); MR_pointerStackReset(&MR_BackTraceStack); TRAV(MR_AmbSourceSearchJ[i],maxk,&incomplete,t); Tfree(t); require (set_nil(incomplete),"MR_traceAmbSourceK TRAV incomplete"); require (MR_BackTraceStack.count == 0,"K: MR_BackTraceStack.count != 0"); set_free(incomplete); }; ConstrainSearch=save_ConstrainSearch; fset=save_fset; MR_AmbSourceSearch=0; MR_MaintainBackTrace=0; MR_AmbSourceSearchChoice=0; } #ifdef __USE_PROTOS Tree *tTrunc(Tree *t,int depth) #else Tree *tTrunc(t,depth) Tree *t; #endif { Tree *u; require ( ! (t == NULL && depth > 0),"tree too short"); if (depth == 0) return NULL; if (t->token == ALT) { u=tTrunc(t->down,depth); } else { u=tnode(t->token); u->down=tTrunc(t->down,depth-1); }; if (t->right != NULL) u->right=tTrunc(t->right,depth); return u; } #ifdef __USE_PROTOS void MR_iterateOverTree(Tree *t,int chain[]) #else void MR_iterateOverTree(t,chain) Tree *t; int chain[]; #endif { if (t == NULL) return; chain[0]=t->token; if (t->down != NULL) { MR_iterateOverTree(t->down,&chain[1]); } else { MR_traceAmbSourceKclient(); }; MR_iterateOverTree(t->right,&chain[0]); chain[0]=0; } #ifdef __USE_PROTOS void MR_traceAmbSourceK(Tree *t,Junction *alt1,Junction *alt2) #else void MR_traceAmbSourceK(t,alt1,alt2) Tree *t; Junction *alt1; Junction *alt2; #endif { int i; int depth; int maxDepth; Tree *truncatedTree; if (MR_AmbAidRule == NULL) return; if ( ! ( strcmp(MR_AmbAidRule,alt1->rname) == 0 || strcmp(MR_AmbAidRule,alt2->rname) == 0 || MR_AmbAidLine==alt1->line || MR_AmbAidLine==alt2->line ) ) return; MR_matched_AmbAidRule++; /* there are no token sets in trees, only in TokNodes */ MR_AmbSourceSearchJ[0]=analysis_point( (Junction *) alt1->p1); MR_AmbSourceSearchJ[1]=analysis_point( (Junction *) alt2->p1); if (tokensInChain == NULL) { tokensInChain=(int *) calloc (CLL_k+1,sizeof(int)); require (tokensInChain != NULL,"tokensInChain alloc"); }; MR_AmbSourceSearchGroup=0; fprintf(stdout,"\n"); fprintf(stdout," Ambiguity Aid "); fprintf(stdout, (MR_AmbAidDepth <= LL_k ? "(-k %d -aa %s %s -aad %d)\n\n" : "(-k %d -aa %s %s [-k value limits -aad %d])\n\n"), LL_k, MR_AmbAidRule, (MR_AmbAidMultiple ? "-aam" : ""), MR_AmbAidDepth); for (i=0 ; i < 2 ; i++) { fprintf(stdout," Choice %d: %-25s line %d file %s\n", (i+1), MR_ruleNamePlusOffset( (Node *) MR_AmbSourceSearchJ[i]), MR_AmbSourceSearchJ[i]->line, FileStr[MR_AmbSourceSearchJ[i]->file]); }; fprintf(stdout,"\n"); if (MR_AmbAidDepth < LL_k) { maxDepth=MR_AmbAidDepth; } else { maxDepth=LL_k; }; for (depth=1 ; depth <= maxDepth; depth++) { MR_AmbSourceSearchLimit=depth; if (depth < LL_k) { truncatedTree=tTrunc(t,depth); truncatedTree=tleft_factor(truncatedTree); MR_iterateOverTree(truncatedTree,&tokensInChain[1]); /* <===== */ Tfree(truncatedTree); } else { MR_iterateOverTree(t,tokensInChain); /* <===== */ }; fflush(stdout); fflush(stderr); }; fprintf(stdout,"\n"); MR_AmbSourceSearch=0; MR_MaintainBackTrace=0; MR_AmbSourceSearchGroup=0; MR_AmbSourceSearchChoice=0; MR_AmbSourceSearchLimit=0; } /* this if for k=1 grammars only this is approximate only because of the limitations of linear approximation lookahead. Don't want to do a k=3 search when the user only specified a ck=3 grammar */ #ifdef __USE_PROTOS void MR_traceAmbSource(set *matchSets,Junction *alt1, Junction *alt2) #else void MR_traceAmbSource(matchSets,alt1,alt2) set *matchSets; Junction *alt1; Junction *alt2; #endif { set *save_fset; Junction *p[2]; int i; int j; set *dup_matchSets; set intersection; set incomplete; set tokensUsed; int depth; if (MR_AmbAidRule == NULL) return; if ( ! ( strcmp(MR_AmbAidRule,alt1->rname) == 0 || strcmp(MR_AmbAidRule,alt2->rname) == 0 || MR_AmbAidLine==alt1->line || MR_AmbAidLine==alt2->line ) ) return; MR_matched_AmbAidRule++; save_fset=fset; dup_matchSets=(set *) calloc(CLL_k+1,sizeof(set)); require (dup_matchSets != NULL,"Can't allocate dup_matchSets"); p[0]=analysis_point( (Junction *) alt1->p1); p[1]=analysis_point( (Junction *) alt2->p1); fprintf(stdout,"\n"); fprintf(stdout," Ambiguity Aid "); fprintf(stdout, (MR_AmbAidDepth <= CLL_k ? "(-ck %d -aa %s %s -aad %d)\n\n" : "(-ck %d -aa %s %s [-ck value limits -aad %d])\n\n"), CLL_k, MR_AmbAidRule, (MR_AmbAidMultiple ? "-aam" : ""), MR_AmbAidDepth); for (i=0 ; i < 2 ; i++) { fprintf(stdout," Choice %d: %-25s line %d file %s\n", (i+1), MR_ruleNamePlusOffset( (Node *) p[i]), p[i]->line,FileStr[p[i]->file]); }; for (j=1; j <= CLL_k ; j++) { fprintf(stdout,"\n Intersection of lookahead[%d] sets:\n",j); intersection=set_and(alt1->fset[j],alt2->fset[j]); MR_dumpTokenSet(stdout,2,intersection); set_free(intersection); }; fprintf(stdout,"\n"); require (1 <= MR_AmbAidDepth && MR_AmbAidDepth <= CLL_k, "illegal MR_AmbAidDepth"); MR_AmbSourceSearchGroup=0; for (depth=1; depth <= MR_AmbAidDepth; depth++) { MR_AmbSourceSearchLimit=depth; for (i=0 ; i < 2 ; i++) { /*** fprintf(stdout," Choice:%d Depth:%d\n\n",i+1,depth); ***/ for (j=0 ; j <= CLL_k ; j++) { dup_matchSets[j]=set_dup(matchSets[j]); }; fset=dup_matchSets; fflush(output); fflush(stdout); MR_AmbSourceSearch=1; MR_MaintainBackTrace=1; MR_AmbSourceSearchChoice=i; maxk = depth; tokensUsed=empty; incomplete=empty; constrain = &(fset[1]); MR_pointerStackReset(&MR_BackTraceStack); REACH(p[i],depth,&incomplete,tokensUsed); fflush(output); fflush(stdout); require (set_nil(incomplete),"MR_traceAmbSource REACH incomplete"); require (MR_BackTraceStack.count == 0,"1: MR_BackTraceStack.count != 0"); set_free(incomplete); set_free(tokensUsed); for (j=0 ; j <= CLL_k ; j++) { set_free(dup_matchSets[j]); }; }; }; fprintf(stdout,"\n"); MR_AmbSourceSearch=0; MR_MaintainBackTrace=0; MR_AmbSourceSearchGroup=0; MR_AmbSourceSearchChoice=0; MR_AmbSourceSearchLimit=0; fset=save_fset; free ( (char *) dup_matchSets); } static int itemCount; void MR_backTraceDumpItemReset() { itemCount=0; } #ifdef __USE_PROTOS void MR_backTraceDumpItem(FILE *f,int skip,Node *n) #else void MR_backTraceDumpItem(f,skip,n) FILE *f; int skip; Node *n; #endif { TokNode *tn; RuleRefNode *rrn; Junction *j; ActionNode *a; switch (n->ntype) { case nToken: itemCount++; if (skip) goto EXIT; tn=(TokNode *)n; if (set_nil(tn->tset)) { fprintf(f," %2d #token %-23s",itemCount,TerminalString(tn->token)); } else { fprintf(f," %2d #tokclass %-20s",itemCount,TerminalString(tn->token)); }; break; case nRuleRef: itemCount++; if (skip) goto EXIT; rrn=(RuleRefNode *)n; fprintf(f," %2d to %-27s",itemCount,rrn->text); break; case nAction: a=(ActionNode *)n; goto EXIT; case nJunction: j=(Junction *)n; switch (j->jtype) { case aSubBlk: if (j->guess) { itemCount++; if (skip) goto EXIT; fprintf(f," %2d %-30s",itemCount,"in (...)? block at"); break; }; /****** fprintf(f," %2d %-32s",itemCount,"in (...) block at"); *******/ /****** break; *******/ goto EXIT; case aOptBlk: itemCount++; if (skip) goto EXIT; fprintf(f," %2d %-30s",itemCount,"in {...} block"); break; case aLoopBlk: itemCount++; if (skip) goto EXIT; fprintf(f," %2d %-30s",itemCount,"in (...)* block"); break; case EndBlk: if (j->alpha_beta_guess_end) { itemCount++; if (skip) goto EXIT; fprintf(f," %2d %-30s",itemCount,"end (...)? block at"); break; }; goto EXIT; /****** fprintf(f," %2d %-32s",itemCount,"end of a block at"); *****/ /****** break; *****/ case RuleBlk: itemCount++; if (skip) goto EXIT; fprintf(f," %2d %-30s",itemCount,j->rname); break; case Generic: goto EXIT; case EndRule: itemCount++; if (skip) goto EXIT; fprintf (f," %2d end %-26s",itemCount,j->rname); break; case aPlusBlk: itemCount++; if (skip) goto EXIT; fprintf(f," %2d %-30s",itemCount,"in (...)+ block"); break; case aLoopBegin: goto EXIT; }; break; }; fprintf(f," %-23s line %-4d %s\n",MR_ruleNamePlusOffset(n),n->line,FileStr[n->file]); EXIT: return; } static PointerStack previousBackTrace={0,0,NULL}; #ifdef __USE_PROTOS void MR_backTraceReport(void) #else void MR_backTraceReport() #endif { int i; int match = 0; int limitMatch; Node *p; TokNode *tn; set remainder; int depth; /* Even when doing a k=2 search this routine can get called when there is only 1 token on the stack. This is because something like rRuleRef can change the search value of k from 2 to 1 temporarily. It does this because the it wants to know the k=1 first set before it does a k=2 search */ depth=0; for (i=0; i < MR_BackTraceStack.count ; i++) { p=(Node *) MR_BackTraceStack.data[i]; if (p->ntype == nToken) depth++; }; /* MR14 */ if (MR_AmbSourceSearch) { /* MR14 */ require (depth <= MR_AmbSourceSearchLimit,"depth > MR_AmbSourceSearchLimit"); /* MR14 */ } /* MR23 THM - Traceback report was being called at the wrong time for -alpha reports */ /* Reported by Arpad Beszedes (beszedes@inf.u-szeged.hu) */ if (MR_AmbSourceSearchLimit == 0 || depth < MR_AmbSourceSearchLimit) { return; }; MR_backTraceDumpItemReset(); limitMatch=MR_BackTraceStack.count; if (limitMatch > previousBackTrace.count) { limitMatch=previousBackTrace.count; }; for (match=0; match < limitMatch; match++) { if (MR_BackTraceStack.data[match] != previousBackTrace.data[match]) { break; }; }; /* not sure at the moment why there would be duplicates */ if (match != MR_BackTraceStack.count) { fprintf(stdout," Choice:%d Depth:%d Group:%d", (MR_AmbSourceSearchChoice+1), MR_AmbSourceSearchLimit, ++MR_AmbSourceSearchGroup); depth=0; fprintf(stdout," ("); for (i=0; i < MR_BackTraceStack.count ; i++) { p=(Node *) MR_BackTraceStack.data[i]; if (p->ntype != nToken) continue; tn=(TokNode *)p; if (depth != 0) fprintf(stdout," "); fprintf(stdout, "%s", TerminalString(tn->token)); depth++; if (! MR_AmbAidMultiple) { if (set_nil(tn->tset)) { set_rm( (unsigned) tn->token,fset[depth]); } else { remainder=set_dif(fset[depth],tn->tset); set_free(fset[depth]); fset[depth]=remainder; }; }; }; fprintf(stdout,")\n"); for (i=0; i < MR_BackTraceStack.count ; i++) { MR_backTraceDumpItem(stdout, (i