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