From 808def96aa4589fba9c2d0ea55837754a3b7a4f7 Mon Sep 17 00:00:00 2001 From: lhauch Date: Wed, 31 Dec 2008 16:26:40 +0000 Subject: Retiring the ANT/JAVA build and removing the older EDK II packages that required ANT/JAVA. Last Ant/Java build was r7166 Developers requiring the Java/Ant packages should checkout the branch from: https://edk2.tianocore.org/svn/edk2/branches/AntJava git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@7168 6f19259b-4bc3-4df7-8a09-765794883524 --- Tools/CCode/Source/Pccts/antlr/fset2.c | 2250 -------------------------------- 1 file changed, 2250 deletions(-) delete mode 100644 Tools/CCode/Source/Pccts/antlr/fset2.c (limited to 'Tools/CCode/Source/Pccts/antlr/fset2.c') diff --git a/Tools/CCode/Source/Pccts/antlr/fset2.c b/Tools/CCode/Source/Pccts/antlr/fset2.c deleted file mode 100644 index 7f686a53d5..0000000000 --- a/Tools/CCode/Source/Pccts/antlr/fset2.c +++ /dev/null @@ -1,2250 +0,0 @@ -/* - * 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 it's 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,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