diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-11 08:17:27 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-11 08:17:27 +0000 |
commit | f215e02bf85f68d3a6106c2a1f4f7f063f819064 (patch) | |
tree | 6bb5b92c046312c4e95ac2620b10ddf482d3fa8b /src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset2.c | |
parent | Initial commit. (diff) | |
download | virtualbox-f215e02bf85f68d3a6106c2a1f4f7f063f819064.tar.xz virtualbox-f215e02bf85f68d3a6106c2a1f4f7f063f819064.zip |
Adding upstream version 7.0.14-dfsg.upstream/7.0.14-dfsg
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset2.c')
-rw-r--r-- | src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset2.c | 2250 |
1 files changed, 2250 insertions, 0 deletions
diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset2.c b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset2.c new file mode 100644 index 00000000..273a25ba --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/VfrCompile/Pccts/antlr/fset2.c @@ -0,0 +1,2250 @@ +/* + * 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 <stdio.h> +#include "pcctscfg.h" +#include <stdlib.h> + +#ifdef PCCTS_USE_STDARG +#include <stdarg.h> +#else +#include <varargs.h> +#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 + +#ifdef TREE_DEBUG /* VBox: +def */ +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: <<p>>? r2 + guarded: r1: (A)? => <<p>>? r2 + ampersand style: r1: (A)? && <<p>>? 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)? && <<p>>? 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<max_k ) /* no permutation left below for k+1 tokens? */ + { + findex[k+1] = 0; + (findex[k])++; /* try next token at this k */ + return permute(k, max_k); + } + + u = tmake(tnode(ftbl[k][findex[k]]), t, NULL); + if ( k == max_k ) (findex[k])++; + return u; +} + +/* Compute LL(k) trees for alts alt1 and alt2 of p. + * function result is tree of ambiguous input permutations + * + * ALGORITHM may change to look for something other than LL_k size + * trees ==> 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<match) ,(Node *) MR_BackTraceStack.data[i]); + }; + fprintf(stdout,"\n"); + fflush(stdout); + + MR_pointerStackReset(&previousBackTrace); + + for (i=0; i < MR_BackTraceStack.count ; i++) { + MR_pointerStackPush(&previousBackTrace,MR_BackTraceStack.data[i]); + }; + + }; +} + +#ifdef __USE_PROTOS +void MR_setConstrainPointer(set * newConstrainValue) +#else +void MR_setConstrainPointer(newConstrainValue) + set * newConstrainValue; +#endif +{ + constrain=newConstrainValue; +} |