Pccts/antlr/fset2.c

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