#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"

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

#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

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;

}

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);

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

}

#ifdef PCCTS_USE_STDARG

Tree *tmake(Tree *root, ...)

#else

Tree *tmake(va_alist)

#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;

}

#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 *

#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 *

#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;

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;

}

#ifdef __USE_PROTOS

Tfree( Tree *t )

#else

Tfree( t )

Tree *t;

#endif

{

if ( t == NULL ) return;

Tfree( t->down );

Tfree( t->right );

_Tfree( t );

}

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;

}

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? */

{

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) )

{

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

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;

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"); */

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

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;

}

#ifdef __USE_PROTOS

tmember( Tree *e, Tree *s )

#else

tmember( e, s )

Tree *e;

Tree *s;

#endif

{

if ( e==NULL||s==NULL ) return 0;

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);

}

#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;

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);

}

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;

}

Tree *

#ifdef __USE_PROTOS

trm_perm( Tree *t, Tree *p )

#else

trm_perm( t, p )

Tree *t;

Tree *p;

#endif

{

/*

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;

}

#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);

}

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;

}

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 );

if ( *t == NULL )

{

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 );

if ( *u == NULL )

{

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 )

{

if ( tmember(perm, *t) && tmember(perm, *u) )

{

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 );

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;

}

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;

}

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;

}

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;

}

#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);

}

#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;

}

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");

*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 );

pred->tcontext = t;

}

else

{

REACH(p, 1, &rk, scontext);

require(set_nil(rk), "rk != nil");

set_free(rk);

pred->scontext[1] = scontext;

}

list_add(&ContextGuardPredicateList,pred); /* MR13 */

return pred;

}

#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;

}

}

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;

}

#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++) {

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;

};

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;

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

depth=0;

for (i=0; i < MR_BackTraceStack.count ; i++) {

p=(Node *) MR_BackTraceStack.data[i];

if (p->ntype == nToken) depth++;

};

/* MR14 */ if (MR_AmbSourceSearch) {

/* MR14 */ require (depth <= MR_AmbSourceSearchLimit,"depth > MR_AmbSourceSearchLimit");

/* MR14 */ }

/* MR23 THM - Traceback report was being called at the wrong time for -alpha reports */

/* Reported by Arpad Beszedes (beszedes@inf.u-szeged.hu) */

if (MR_AmbSourceSearchLimit == 0 || depth < MR_AmbSourceSearchLimit) {

return;

};

MR_backTraceDumpItemReset();

limitMatch=MR_BackTraceStack.count;

if (limitMatch > previousBackTrace.count) {

limitMatch=previousBackTrace.count;

};

for (match=0; match < limitMatch; match++) {

if (MR_BackTraceStack.data[match] !=

previousBackTrace.data[match]) {

break;

};

};

/* not sure at the moment why there would be duplicates */

if (match != MR_BackTraceStack.count) {

fprintf(stdout," Choice:%d Depth:%d Group:%d",

(MR_AmbSourceSearchChoice+1),

MR_AmbSourceSearchLimit,

++MR_AmbSourceSearchGroup);

depth=0;

fprintf(stdout," (");

for (i=0; i < MR_BackTraceStack.count ; i++) {

p=(Node *) MR_BackTraceStack.data[i];

if (p->ntype != nToken) continue;

tn=(TokNode *)p;

if (depth != 0) fprintf(stdout," ");

fprintf(stdout,TerminalString(tn->token));

depth++;

if (! MR_AmbAidMultiple) {

if (set_nil(tn->tset)) {

set_rm( (unsigned) tn->token,fset[depth]);

} else {

remainder=set_dif(fset[depth],tn->tset);

set_free(fset[depth]);

fset[depth]=remainder;

};

};

};

fprintf(stdout,")\n");

for (i=0; i < MR_BackTraceStack.count ; i++) {

MR_backTraceDumpItem(stdout, (i<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;

}