libpccts_133MR33/antlr/fset.c

/*
 * fset.c
 *
 * $Id: fset.c,v 1.6 95/06/15 18:07:09 parrt Exp $
 * $Revision: 1.6 $
 *
 * Compute FIRST and FOLLOW sets.
 *
 * 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-1995
 */
#include <stdio.h>
#ifdef __cplusplus
#ifndef __STDC__
#define __STDC__
#endif
#endif
#include "set.h"
#include "syn.h"
#include "hash.h"
#include "generic.h"
#include "dlgdef.h"

extern char *PRED_AND_LIST;
extern char *PRED_OR_LIST;

#ifdef __STDC__
static void ensure_predicates_cover_ambiguous_lookahead_sequences(Junction *, Junction *, char *, Tree *);
#else
static void ensure_predicates_cover_ambiguous_lookahead_sequences();
#endif

/*
 * What tokens are k tokens away from junction q?
 *
 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
 * node.
 * We lock the junction according to k--the lookahead.  If we have been at this
 * junction before looking for the same, k, number of lookahead tokens, we will
 * do it again and again...until we blow up the stack.  Locks are only used on aLoopBlk,
 * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from
 * FIRST and FOLLOW calcs.
 *
 * If p->jtype == EndRule we are going to attempt a FOLLOW.  (FOLLOWs are really defined
 * in terms of FIRST's, however).  To proceed with the FOLLOW, p->halt cannot be
 * set.  p->halt is set to indicate that a reference to the current rule is in progress
 * and the FOLLOW is not desirable.
 *
 * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule
 * junction yields an empty set, replace the empty set with EOF.  No FOLLOW means that
 * only EOF can follow the current rule.  This normally occurs only on the start symbol
 * since all other rules are referenced by another rule somewhere.
 *
 * Normally, both p1 and p2 are followed.  However, checking p2 on a RuleBlk node is
 * the same as checking the next rule which is clearly incorrect.
 *
 * Cycles in the FOLLOW sense are possible.  e.g. Fo(c) requires Fo(b) which requires
 * Fo(c).  Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c).  Let's say
 * Fo(c) is attempted first.  It finds all of the FOLLOW symbols and then attempts
 * to do Fo(b) which finds of its FOLLOW symbols.  So, we have:
 *
 *                  Fo(c)
 *                 /     \
 *              a set    Fo(b)
 *                      /     \
 *                   a set    Fo(c) .....Hmmmm..... Infinite recursion!
 *
 * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now
 * correctly Fo(c) union Fo(b).  We wish to pick up where we left off, so the fact
 * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already
 * laying around.  SOOOOoooo, we track FOLLOW cycles.  All FOLLOW computations are
 * cached in a hash table.  After the sequence of FOLLOWs finish, we reconcile all
 * cycles --> correct all Fo(rule) sets in the cache.
 *
 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
 * TJP 8/93 -- can now read PhD thesis from Purdue.
 *
 * Also, FIRST sets are cached in the hash table.  Keys are (rulename,Fi/Fo,k).
 * Only FIRST sets, for which the FOLLOW is not included, are stored.
 *
 * SPECIAL CASE of (...)+ blocks:
 * I added an optional alt so that the alts could see what
 * was behind the (...)+ block--thus using enough lookahead
 * to branch out rather than just enough to distinguish
 * between alts in the (...)+.  However, when the FIRST("(...)+") is
 * is needed, must not use this last "optional" alt.  This routine
 * turns off this path by setting a new 'ignore' flag for
 * the alt and then resetting it afterwards.
 */
set
#ifdef __STDC__
rJunc( Junction *p, int k, set *rk )
#else
rJunc( p, k, rk )
Junction *p;
int k;
set *rk;
#endif
{
	set a, b;
	require(p!=NULL,				"rJunc: NULL node");
	require(p->ntype==nJunction,	"rJunc: not junction");

#ifdef DBG_LL1
	if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k);
	else fprintf(stderr, "rJunc: %s in rule %s\n",
			decodeJType[p->jtype], ((Junction *)p)->rname);
#endif
	/* if this is one of the added optional alts for (...)+ then return */
	if ( p->ignore ) return empty;

	/* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */
	if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
		 p->jtype==aPlusBlk || p->jtype==EndRule )
	{
		require(p->lock!=NULL, "rJunc: lock array is NULL");
		if ( p->lock[k] )
		{
			if ( p->jtype == EndRule )	/* FOLLOW cycle? */
			{
#ifdef DBG_LL1
				fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);
#endif
				RegisterCycle(p->rname, k);
			}
			return empty;
		}
		if ( p->jtype == RuleBlk && p->end->halt )	/* check for FIRST cache */
		{
			CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
			if ( q != NULL )
			{
				set_orin(rk, q->rk);
				return set_dup( q->fset );
			}
		}
		if ( p->jtype == EndRule )		/* FOLLOW set cached already? */
		{
			CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
			if ( q != NULL )
			{
#ifdef DBG_LL1
				fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k);
				s_fprT(stderr, q->fset);
				if ( q->incomplete ) fprintf(stderr, " (incomplete)");
				fprintf(stderr, "\n");
#endif
				if ( !q->incomplete )
				{
					return set_dup( q->fset );
				}
			}
		}
		p->lock[k] = TRUE;	/* This rule is busy */
	}

	a = b = empty;

	if ( p->jtype == EndRule )
	{
		if ( p->halt )								/* don't want FOLLOW here? */
		{
			p->lock[k] = FALSE;
			set_orel(k, rk);						/* indicate this k value needed */
			return empty;
		}
		FoPush(p->rname, k);						/* Attempting FOLLOW */
		if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */
#ifdef DBG_LL1
		fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);
#endif
	}

	if ( p->p1 != NULL ) REACH(p->p1, k, rk, a);
	
	/* C a c h e  R e s u l t s */
	if ( p->jtype == RuleBlk && p->end->halt )		/* can save FIRST set? */
	{
		CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) );
		/*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/
		hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q);
		q->fset = set_dup( a );
		q->rk = set_dup( *rk );
	}

	if ( p->jtype == EndRule )						/* just completed FOLLOW? */
	{
		/* Cache Follow set */
		CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
		if ( q==NULL )
		{
			q = newCacheEntry( Fkey(p->rname,'o',k) );
			hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
		}
		/*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
		if ( set_nil(a) && !q->incomplete )
		{
			/* Don't ever save a nil set as complete.
			 * Turn it into an eof set.
			 */
			set_orel(EofToken, &a);
		}
		set_orin(&(q->fset), a);
		FoPop( k );
		if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
#ifdef DBG_LL1
		fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k);
		s_fprT(stderr, q->fset);
		if ( q->incomplete ) fprintf(stderr, " (incomplete)");
		fprintf(stderr, "\n");
#endif
	}
	
	if ( p->jtype != RuleBlk && p->p2 != NULL ) REACH(p->p2, k, rk, b);
	if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
		 p->jtype==aPlusBlk || p->jtype==EndRule )
		p->lock[k] = FALSE;							/* unlock node */

	set_orin(&a, b);
	set_free(b);
	return a;
}

set
#ifdef __STDC__
rRuleRef( RuleRefNode *p, int k, set *rk_out )
#else
rRuleRef( p, k, rk_out )
RuleRefNode *p;
int k;
set *rk_out;
#endif
{
	set rk;
	Junction *r;
	int k2;
	set a, rk2, b;
	int save_halt;
	RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
	require(p!=NULL,			"rRuleRef: NULL node");
	require(p->ntype==nRuleRef,	"rRuleRef: not rule ref");

#ifdef DBG_LL1
	fprintf(stderr, "rRuleRef: %s\n", p->text);
#endif
	if ( q == NULL )
	{
		warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
		REACH(p->next, k, rk_out, a);
		return a;
	}
	rk2 = empty;
	r = RulePtr[q->rulenum];
	if ( r->lock[k] )
	{
		errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
						r->rname, p->rname) );
		return empty;
	}
	save_halt = r->end->halt;
	r->end->halt = TRUE;		/* don't let reach fall off end of rule here */
	rk = empty;
	REACH(r, k, &rk, a);
	r->end->halt = save_halt;
	while ( !set_nil(rk) ) {
		k2 = set_int(rk);
		set_rm(k2, rk);
		REACH(p->next, k2, &rk2, b);
		set_orin(&a, b);
		set_free(b);
	}
	set_free(rk);				/* this has no members, but free it's memory */
	set_orin(rk_out, rk2);		/* remember what we couldn't do */
	set_free(rk2);
	return a;
}

/*
 * Return FIRST sub k ( token_node )
 *
 * TJP 10/11/93 modified this so that token nodes that are actually
 * ranges (T1..T2) work.
 */
set
#ifdef __STDC__
rToken( TokNode *p, int k, set *rk )
#else
rToken( p, k, rk )
TokNode *p;
int k;
set *rk;
#endif
{
	set a;
	require(p!=NULL,			"rToken: NULL node");
	require(p->ntype==nToken,	"rToken: not token node");

#ifdef DBG_LL1
	fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):
									ExprString(p->token));
#endif
	if ( k-1 == 0 )
	{
		if ( !set_nil(p->tset) ) return set_dup(p->tset);
		return set_of(p->token);
	}
	REACH(p->next, k-1, rk, a);
	
	return a;
}

set
#ifdef __STDC__
rAction( ActionNode *p, int k, set *rk )
#else
rAction( p, k, rk )
ActionNode *p;
int k;
set *rk;
#endif
{
	set a;
	require(p!=NULL,			"rJunc: NULL node");
	require(p->ntype==nAction,	"rJunc: not action");
	
	REACH(p->next, k, rk, a);	/* ignore actions */
	return a;
}

				/* A m b i g u i t y  R e s o l u t i o n */


void
#ifdef __STDC__
dumpAmbigMsg( set *fset, FILE *f, int want_nls )
#else
dumpAmbigMsg( fset, f, want_nls )
set *fset;
FILE *f;
int want_nls;
#endif
{
	int i;

	if ( want_nls ) fprintf(f, "\n\t");
	else fprintf(f, " ");
	for (i=1; i<=CLL_k; i++)
	{
		if ( i>1 )
		{
			if ( !want_nls ) fprintf(f, ", ");
		}
		if ( set_deg(fset[i]) > 3 && elevel == 1 )
		{
			int e,m;
			fprintf(f, "{");
			for (m=1; m<=3; m++)
			{
				e=set_int(fset[i]);
				fprintf(f, " %s", TerminalString(e));
				set_rm(e, fset[i]);
			}
			fprintf(f, " ... }");
		}
		else s_fprT(f, fset[i]);
		if ( want_nls ) fprintf(f, "\n\t");
	}
	fprintf(f, "\n");
}

static void
#ifdef __USE_PROTOS
verify_context(Predicate *predicate)
#else
verify_context(predicate)
Predicate *predicate;
#endif
{
	if ( predicate == NULL ) return;

	if ( predicate->expr == PRED_OR_LIST ||
		 predicate->expr == PRED_AND_LIST )
	{
		verify_context(predicate->down);
		return;
	}

	if ( !predicate->source->ctxwarned && predicate->source->guardpred==NULL &&
		 ((predicate->k > 1 &&
		 !is_single_tuple(predicate->tcontext)) ||
		 ( predicate->k == 1 &&
			  set_deg(predicate->scontext[1])>1 )) )
	{
		fprintf(stderr, ErrHdr, FileStr[predicate->source->file],
				predicate->source->line);
		fprintf(stderr, " warning: predicate applied for >1 lookahead %d-sequences\n", predicate->k);
		fprintf(stderr, ErrHdr, FileStr[predicate->source->file],
				predicate->source->line);
		fprintf(stderr, " [you may only want one lookahead %d-sequence to apply.\n", predicate->k);
		fprintf(stderr, ErrHdr, FileStr[predicate->source->file],
				predicate->source->line);
		fprintf(stderr, "  Try using a context guard '(...)? =>'.]\n");
		predicate->source->ctxwarned = 1;
	}
}

/*
 * If delta is the set of ambiguous lookahead sequences, then make sure that
 * the predicate(s) for productions alt1,alt2 cover the sequences in delta.
 *
 * For example,
 *	a : <<PRED1>>? (A B|A C)
 *	  | b
 *    ;
 *	b : <<PRED2>>? A B
 *	  | A C
 *	  ;
 *
 * This should give a warning that (A C) predicts both productions and alt2
 * does not have a predicate in the production that generates (A C).
 *
 * The warning detection is simple.  Let delta = LOOK(alt1) intersection LOOK(alt2).
 * Now, if ( delta set-difference context(predicates-for-alt1) != empty then
 * alt1 does not "cover" all ambiguous sequences.
 *
 * If ambig is nonempty, then ambig in LL(k) sense -> use tree info; else use fset
 * info.  Actually, sets are used only if k=1 for this grammar.
 */
static void
#ifdef __USE_PROTOS
ensure_predicates_cover_ambiguous_lookahead_sequences( Junction *alt1, Junction *alt2, char *sub, Tree *ambig )
#else
ensure_predicates_cover_ambiguous_lookahead_sequences( alt1, alt2, sub, ambig )
Junction *alt1;
Junction *alt2;
char *sub;
Tree *ambig;
#endif
{
	if ( !ParseWithPredicates ) return;

	if ( ambig!=NULL )
	{
		Tree *non_covered = NULL;
		if ( alt1->predicate!=NULL )
			non_covered = tdif(ambig, alt1->predicate, alt1->fset, alt2->fset);
		if ( (non_covered!=NULL || alt1->predicate==NULL) && WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
			fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
							alt1->altnum, sub);
			if ( alt1->predicate!=NULL && non_covered!=NULL )
			{
				fprintf(stderr, " upon");
				preorder(non_covered);
			}
			else if ( alt1->predicate==NULL )
			{
				fprintf(stderr, " upon");
				preorder(ambig->down);
			}
			fprintf(stderr, "\n");
		}
		Tfree(non_covered);
		non_covered = NULL;
		if ( alt2->predicate!=NULL )
			non_covered = tdif(ambig, alt2->predicate, alt1->fset, alt2->fset);
		if ( (non_covered!=NULL || alt2->predicate==NULL) && WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
			fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
							alt2->altnum, sub);
			if ( alt2->predicate!=NULL && non_covered!=NULL )
			{
				fprintf(stderr, " upon");
				preorder(non_covered);
			}
			else if ( alt2->predicate==NULL )
			{
				fprintf(stderr, " upon");
				preorder(ambig->down);
			}
			fprintf(stderr, "\n");
		}
		Tfree(non_covered);
	}
	else if ( !set_nil(alt1->fset[1]) )
	{
		set delta, non_covered;
		delta = set_and(alt1->fset[1], alt2->fset[1]);
		non_covered = set_dif(delta, covered_set(alt1->predicate));
		if ( set_deg(non_covered)>0 && WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
			fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
							alt1->altnum, sub);
			if ( alt1->predicate!=NULL )
			{
				fprintf(stderr, " upon ");
				s_fprT(stderr, non_covered);
			}
			fprintf(stderr, "\n");
		}
		set_free( non_covered );
		non_covered = set_dif(delta, covered_set(alt2->predicate));
		if ( set_deg(non_covered)>0 && WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt2->file], alt2->line);
			fprintf(stderr, " warning: alt %d %shas no predicate to resolve ambiguity",
							alt2->altnum, sub);
			if ( alt2->predicate!=NULL )
			{
				fprintf(stderr, " upon ");
				s_fprT(stderr, non_covered);
			}
			fprintf(stderr, "\n");
		}
		set_free( non_covered );
		set_free( delta );
	}
	else fatal_internal("productions have no lookahead in predicate checking routine");
}

void
#ifdef __STDC__
HandleAmbiguity( Junction *block, Junction *alt1, Junction *alt2, int jtype )
#else
HandleAmbiguity( block, alt1, alt2, jtype )
Junction *block;
Junction *alt1;
Junction *alt2;
int jtype;
#endif
{
	unsigned **ftbl;
	set *fset, b;
	int i, numAmbig, n, n2;
	Tree *ambig=NULL, *t, *u;
	char *sub = "";
	require(block!=NULL, "NULL block");
	require(block->ntype==nJunction, "invalid block");

	/* These sets are used to constrain LL_k set, but are made CLL_k long anyway */
	fset = (set *) calloc(CLL_k+1, sizeof(set));
	require(fset!=NULL, "cannot allocate fset");
	ftbl = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
	require(ftbl!=NULL, "cannot allocate ftbl");
	/* create constraint table and count number of possible ambiguities (use<=LL_k) */
	for (n=1,i=1; i<=CLL_k; i++)
	{
		b = set_and(alt1->fset[i], alt2->fset[i]);
		n *= set_deg(b);
		fset[i] = set_dup(b);
		ftbl[i] = set_pdq(b);
		set_free(b);
	}

	switch ( jtype )
	{
		case aSubBlk: sub = "of (..) "; break;
		case aOptBlk: sub = "of {..} "; break;
		case aLoopBegin: sub = "of (..)* "; break;
		case aLoopBlk: sub = "of (..)* "; break;
		case aPlusBlk: sub = "of (..)+ "; break;
		case RuleBlk: sub = "of the rule itself "; break;
		default : sub = ""; break;
	}

	/* If the block is marked as a compressed lookahead only block, then
	 * simply return; ambiguity warning is given only at warning level 2.
	 */
	if ( block->approx>0 )
	{
		if ( ParseWithPredicates )
		{
			alt1->predicate = find_predicates((Node *)alt1->p1);
			alt2->predicate = find_predicates((Node *)alt2->p1);
			if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
			{
				verify_context(alt1->predicate);
				verify_context(alt2->predicate);
			}

			if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
			ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
		}

		if ( WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
			if ( jtype == aLoopBegin || jtype == aPlusBlk )
				fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
			else
				fprintf(stderr, " warning(approx): alts %d and %d %sambiguous upon",
						alt1->altnum, alt2->altnum, sub);
			dumpAmbigMsg(fset, stderr, 0);
		}
		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
		free((char *)ftbl);
		return;
    }

	/* if all sets have degree 1 for k<LL_k, then must be ambig upon >=1 permutation;
	 * don't bother doing full LL(k) analysis.
	 * (This "if" block handles the LL(1) case)
	 */
	n2 = 0;
	for (i=1; i<LL_k; i++) n2 += set_deg(alt1->fset[i])+set_deg(alt2->fset[i]);
	if ( n2==2*(LL_k-1) )
	{
/* TJP: added to fix the case where LL(1) and syntactic predicates didn't
 * work.  It now recognizes syntactic predicates, but does not like combo:
 * LL(1)/syn/sem predicates. (10/24/93)
 */
		if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
		{
			if ( WarningLevel==1 )
			{
				for (i=1; i<=CLL_k; i++) set_free( fset[i] );
				free((char *)fset);
				for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
				free((char *)ftbl);
				return;
			}

			fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
			if ( jtype == aLoopBegin || jtype == aPlusBlk )
			   fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
			else
			   fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
					   alt1->altnum, alt2->altnum, sub);
			dumpAmbigMsg(fset, stderr, 0);
		}

		ambig = NULL;
		if ( LL_k>1 ) ambig = make_tree_from_sets(alt1->fset, alt2->fset);
		if ( ParseWithPredicates )
		{
		   alt1->predicate = find_predicates((Node *)alt1->p1);
		   alt2->predicate = find_predicates((Node *)alt2->p1);
		   if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
		   {
				verify_context(alt1->predicate);
				verify_context(alt2->predicate);
		   }
		   if (HoistPredicateContext&&(alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1)
			  ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
		   if ( WarningLevel == 1 &&
			   (alt1->predicate!=NULL||alt2->predicate!=NULL))
		   {
			  for (i=1; i<=CLL_k; i++) set_free( fset[i] );
			  free((char *)fset);
			  for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
			  free((char *)ftbl);
			  Tfree(ambig);
			  return;
		   }
		}
/* end TJP (10/24/93) */

		fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
		if ( jtype == aLoopBegin || jtype == aPlusBlk )
			fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
		else
		   fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
				   alt1->altnum, alt2->altnum, sub);
		if ( elevel == 3 && LL_k>1 )
		{
		   preorder(ambig);
		   fprintf(stderr, "\n");
		   Tfree(ambig);
		   return;
	    }
		Tfree(ambig);
		dumpAmbigMsg(fset, stderr, 0);

		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
		free((char *)ftbl);
		return;
	}

	/* in case tree construction runs out of memory, set info to make good err msg */
	CurAmbigAlt1 = alt1->altnum;
	CurAmbigAlt2 = alt2->altnum;
	CurAmbigbtype = sub;
	CurAmbigfile = alt1->file;
	CurAmbigline = alt1->line;
	
	/* Don't do full LL(n) analysis if (...)? block because the block,
	   by definition, defies LL(n) analysis.
	   If guess (...)? block and ambiguous then don't remove anything from
	   2nd alt to resolve ambig.
	   Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block
	   since it is much cheaper than LL(n).  LL sup 1 ( n ) "covers" the LL(n)
	   lookahead information.

	   Note: LL(n) context cannot be computed for semantic predicates when
	   followed by (..)?.

	   If (..)? then we scream "AAAHHHH!  No LL(n) analysis will help"

       Is 'ambig' always defined if we enter this if?  I hope so
	   because the 'ensure...()' func references it. TJP Nov 1993.
	   */
	if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
	{
		if ( ParseWithPredicates )
		{
			alt1->predicate = find_predicates((Node *)alt1->p1);
			alt2->predicate = find_predicates((Node *)alt2->p1);
			if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
			{
				verify_context(alt1->predicate);
				verify_context(alt2->predicate);
			}
			if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
				ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
			if ( WarningLevel==1 &&
				(alt1->predicate!=NULL||alt2->predicate!=NULL))
			{
				for (i=1; i<=CLL_k; i++) set_free( fset[i] );
				free((char *)fset);
				for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
				free((char *)ftbl);
				return;
			}
		}

		if ( WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
			if ( jtype == aLoopBegin || jtype == aPlusBlk )
				fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
			else
				fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
						alt1->altnum, alt2->altnum, sub);
			dumpAmbigMsg(fset, stderr, 0);
		}

		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
		free((char *)ftbl);
		return;
	}
	
	/* Not resolved with (..)? block.  Do full LL(n) analysis */
	
	/* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */
	ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);
	for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
	free((char *)ftbl);

	/* are all things in intersection really ambigs? */
	if ( numAmbig < n )
	{
		Tree *v;

		/* remove ambig permutation from 2nd alternative to resolve ambig;
		 * We want to compute the set of artificial tuples, arising from
		 * LL sup 1 (n) compression, that collide with real tuples from the
		 * 2nd alternative.  This is the set of "special case" tuples that
		 * the LL sup 1 (n) decision template maps incorrectly.
		 */
		if ( ambig!=NULL )
		{
			for (v=ambig->down; v!=NULL; v=v->right)
			{
				u = trm_perm(u, v);
			}
/*			fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
		}
		Tfree( t );
		alt1->ftree = tappend(alt1->ftree, u);
		alt1->ftree = tleft_factor(alt1->ftree);
	}

	if ( ambig==NULL )
	{
		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		return;
	}

	ambig = tleft_factor(ambig);

/* TJP:
 * At this point, we surely have an LL(k) ambiguity.  Check for predicates
 */
	if ( ParseWithPredicates )
	{
		alt1->predicate = find_predicates((Node *)alt1->p1);
		alt2->predicate = find_predicates((Node *)alt2->p1);
		if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
		{
			verify_context(alt1->predicate);
			verify_context(alt2->predicate);
		}
		if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
		   ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
		if ( WarningLevel==1 &&
 			(alt1->predicate!=NULL||alt2->predicate!=NULL))
		{
			/* We found at least one pred for at least one of the alts;
			 * If warnings are low, just return.
			 */
			Tfree(ambig);
			return;
		}
		/* else we're gonna give a warning */
	}
/* end TJP addition */

	fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
	if ( jtype == aLoopBegin || jtype == aPlusBlk )
		fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
	else
		fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
					alt1->altnum, alt2->altnum, sub);
	if ( elevel == 3 )
	{
		preorder(ambig->down);
		fprintf(stderr, "\n");
		Tfree(ambig);
		return;
	}
	Tfree(ambig);
	dumpAmbigMsg(fset, stderr, 0);
	for (i=1; i<=CLL_k; i++) set_free( fset[i] );
	free((char *)fset);
}

/* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze
 * Return the 1st node of the beta block if present else return j.
 */
Junction *
#ifdef __STDC__
analysis_point( Junction *j )
#else
analysis_point( j )
Junction *j;
#endif
{
	Junction *gblock;

	if ( j->ntype!=nJunction ) return j;
	gblock = first_item_is_guess_block((Junction *)j);

	if ( gblock!=NULL )
	{
		Junction *past = gblock->end;
		Junction *p;
		require(past!=NULL, "analysis_point: no end block on (...)? block");

		for (p=(Junction *)past->p1; p!=NULL; )
		{
			if ( p->ntype==nAction )
			{
				p=(Junction *)((ActionNode *)p)->next;
				continue;
			}
			if ( p->ntype!=nJunction )
			{
				return (Junction *)past->p1;
			}
			if ( p->jtype==EndBlk || p->jtype==EndRule )
			{
				return j;
			}
/* MR6              									      */
/* MR6	A guess block is of the form "(alpha)? beta" or "(alpha)?".           */
/* MR6  When beta is omitted (second form) this means "(alpha)? alpha".       */
/* MR6  The program does not store another copy of alpha in this case.        */
/* MR6  During analysis when the program needs to know what follows the       */
/* MR6    guess clause.  It calls this routine.                               */
/* MR6                                                                        */
/* MR6      If it is of the form "(alpha)? beta" it returns a pointer to beta.*/
/* MR6                                                                        */
/* MR6      If it is of the form "(alpha)?" it returns a pointer to the guess */
/* MR6        block itself thereby reusing the junction tree.                 */
/* MR6                                                                        */
/* MR6  It works by searching the "next in sequence" chain (skipping actions) */
/* MR6    searching for a RuleRef or Token node.  (Those are the only 4 kinds */
/* MR6    of nodes: Junctions, RuleRef, Token, and Action.)                   */
/* MR6                                                                        */
/* MR6  This won't work for the special case "(alpha)? ()" because it has no  */
/* MR6    rule references or token nodes.  It eventually encounters a         */
/* MR6	  junction of type EndBlk or EndRule and says to its caller: nothing  */
/* MR6    more here to analyze - must be of the form "(alpha)?".              */
/* MR6                                                                        */
/* MR6  In the case of "(alpha)? ()" it should return a pointer to "()"       */
/* MR6                                                                        */
/* MR6  I think.                                                              */
/* MR6                                                                        */
			if ( p->jtype!=Generic) {		                       /* MR6 */
				return (Junction *)past->p1;                           /* MR6 */
			};					                                       /* MR6 */
       			p=(Junction *)p->p1;
		}
	}
	return j;
}

set
#ifdef __STDC__
First( Junction *j, int k, int jtype, int *max_k )
#else
First( j, k, jtype, max_k )
Junction *j;
int k;
int jtype;
int *max_k;
#endif
{
	Junction *alt1, *alt2;
	set a, rk, fCurBlk;
	int savek;
	int p1, p2;
	require(j->ntype==nJunction, "First: non junction passed");

	/* C o m p u t e  F I R S T  s e t  w i t h  k  l o o k a h e a d */
	fCurBlk = rk = empty;
	for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2)
	{
		Junction *p = analysis_point((Junction *)alt1->p1);
		REACH(p, k, &rk, alt1->fset[k]);
		require(set_nil(rk), "rk != nil");
		set_free(rk);
		set_orin(&fCurBlk, alt1->fset[k]);
	}

	/* D e t e c t  A m b i g u i t i e s */
	*max_k = 1;
	for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)
	{
		for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)
		{
			savek = k;
			a = set_and(alt1->fset[k], alt2->fset[k]);
			while ( !set_nil(a) )
			{
				/* if we have hit the max k requested, just give warning */
				if ( j->approx==k ) {
				}

				if ( k==CLL_k )
				{
#ifdef NOT_USED
					int save_LL_k = LL_k;
					int save_CLL_k = CLL_k;
					/* Get new LL_k from interactive feature if enabled */
					if ( AImode )
						AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);
#endif
					*max_k = CLL_k;
					HandleAmbiguity(j, alt1, alt2, jtype);
					break;
				}
				else
				{
					Junction *p = analysis_point((Junction *)alt1->p1);
					Junction *q = analysis_point((Junction *)alt2->p1);
					k++;	/* attempt ambig alts again with more lookahead */
					REACH(p, k, &rk, alt1->fset[k]);
					require(set_nil(rk), "rk != nil");
					REACH(q, k, &rk, alt2->fset[k]);
					require(set_nil(rk), "rk != nil");
					set_free(a);
					a = set_and(alt1->fset[k], alt2->fset[k]);
					if ( k > *max_k ) *max_k = k;
				}
			}
			set_free(a);
			k = savek;
		}
	}

	return fCurBlk;
}