libpccts_133MR33/antlr/misc.c

/*
 * misc.c
 *
 * Manage tokens, regular expressions.
 * Print methods for debugging
 * Compute follow lists onto tail ends of rules.
 *
 * The following functions are visible:
 *
 *		int		addTname(char *);		Add token name
 *		int		addTexpr(char *);		Add token expression
 *		int		Tnum(char *);			Get number of expr/token
 *		void	Tklink(char *, char *);	Link a name with an expression
 *		int		hasAction(expr);		Does expr already have action assigned?
 *		void	setHasAction(expr);		Indicate that expr now has an action
 *		Entry	*newEntry(char *,int);	Create new table entry with certain size
 *		void	list_add(ListNode **list, char *e)
 *		void	list_apply(ListNode *list, void (*f)())
 *		void	lexclass(char *m);		switch to new/old lexical class
 *		void	lexmode(int i);			switch to old lexical class i
 *
 * 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"

static int tsize=TSChunk;		/* size of token str arrays */

static void
#ifdef __STDC__
RemapForcedTokensInSyntaxDiagram(Node *);
#else
RemapForcedTokensInSyntaxDiagram();
#endif

				/* T o k e n  M a n i p u l a t i o n */

/*
 * add token 't' to the TokenStr/Expr array.  Make more room if necessary.
 * 't' is either an expression or a token name.
 *
 * There is only one TokenStr array, but multiple ExprStr's.  Therefore,
 * for each lex class (element of lclass) we must extend the ExprStr array.
 * ExprStr's and TokenStr are always all the same size.
 *
 * Also, there is a Texpr hash table for each automaton.
 */
static void
#ifdef __STDC__
Ttrack( char *t )
#else
Ttrack( t )
char *t;
#endif
{
	if ( TokenNum >= tsize )	/* terminal table overflow? */
	{
		char **p;
		int i, more, j;

		more = TSChunk * (1 + ((TokenNum-tsize) / TSChunk));
		tsize += more;
		TokenStr = (char **) realloc((char *)TokenStr, tsize*sizeof(char *));
		require(TokenStr != NULL, "Ttrack: can't extend TokenStr");
		for (i=0; i<NumLexClasses; i++)
		{
			lclass[i].exprs = (char **)
							  realloc((char *)lclass[i].exprs, tsize*sizeof(char *));
			require(lclass[i].exprs != NULL, "Ttrack: can't extend ExprStr");
			for (p= &lclass[i].exprs[tsize-more],j=1; j<=more; j++) *p++ = NULL;
		}
		for (p= &TokenStr[tsize-more],i=1; i<=more; i++) *p++ = NULL;
		lexmode( CurrentLexClass ); /* reset ExprStr in case table moved */
	}
	/* note: we use the actual ExprStr/TokenStr array
	 * here as TokenInd doesn't exist yet
	 */
	if ( *t == '"' ) ExprStr[TokenNum] = t;
	else TokenStr[TokenNum] = t;
}

static Expr *
#ifdef __STDC__
newExpr( char *e )
#else
newExpr( e )
char *e;
#endif
{
	Expr *p = (Expr *) calloc(1, sizeof(Expr));
	require(p!=NULL, "newExpr: cannot alloc Expr node");

	p->expr = e;
	p->lclass = CurrentLexClass;
	return p;
}

/* switch to lexical class/mode m.  This amounts to creating a new
 * lex mode if one does not already exist and making ExprStr point
 * to the correct char string array.  We must also switch Texpr tables.
 *
 * BTW, we need multiple ExprStr arrays because more than one automaton
 * may have the same label for a token, but with different expressions.
 * We need to track an expr for each automaton.  If we disallowed this
 * feature, only one ExprStr would be required.
 */
void
#ifdef __STDC__
lexclass( char *m )
#else
lexclass( m )
char *m;
#endif
{
	int i;
	TermEntry *p;
	static char EOFSTR[] = "\"@\"";

	if ( hash_get(Tname, m) != NULL )
	{
		warn(eMsg1("lexclass name conflicts with token/errclass label '%s'",m));
	}
	/* does m already exist? */
	i = LexClassIndex(m);
	if ( i != -1 ) {lexmode(i); return;}
	/* must make new one */
	NumLexClasses++;
	CurrentLexClass = NumLexClasses-1;
	require(NumLexClasses<=MaxLexClasses, "number of allowable lexclasses exceeded\nIncrease MaxLexClasses in generic.h and recompile all C files");
	lclass[CurrentLexClass].classnum = m;
	lclass[CurrentLexClass].exprs = (char **) calloc(tsize, sizeof(char *));
	require(lclass[CurrentLexClass].exprs!=NULL,
			"lexclass: cannot allocate ExprStr");
	lclass[CurrentLexClass].htable = newHashTable();
	ExprStr = lclass[CurrentLexClass].exprs;
	Texpr = lclass[CurrentLexClass].htable;
	/* define EOF for each automaton */
	p = newTermEntry( EOFSTR );
	p->token = EofToken;	/* couldn't have remapped tokens yet, use EofToken */
	hash_add(Texpr, EOFSTR, (Entry *)p);
	list_add(&ExprOrder, (void *)newExpr(EOFSTR));
	/* note: we use the actual ExprStr array
	 * here as TokenInd doesn't exist yet
	 */
	ExprStr[EofToken] = EOFSTR;
}

void
#ifdef __STDC__
lexmode( int i )
#else
lexmode( i )
int i;
#endif
{
	require(i<NumLexClasses, "lexmode: invalid mode");
	ExprStr = lclass[i].exprs;
	Texpr = lclass[i].htable;
	CurrentLexClass = i;
}

/* return index into lclass array of lexical class. return -1 if nonexistent */
int
#ifdef __STDC__
LexClassIndex( char *cl )
#else
LexClassIndex( cl )
char *cl;
#endif
{
	int i;

	for (i=0; i<NumLexClasses; i++)
	{
		if ( strcmp(lclass[i].classnum, cl) == 0 ) return i;
	}
	return -1;
}

int
#ifdef __STDC__
hasAction( char *expr )
#else
hasAction( expr )
char *expr;
#endif
{
	TermEntry *p;
	require(expr!=NULL, "hasAction: invalid expr");

	p = (TermEntry *) hash_get(Texpr, expr);
	require(p!=NULL, eMsg1("hasAction: expr '%s' doesn't exist",expr));
	return (p->action!=NULL);
}

void
#ifdef __STDC__
setHasAction( char *expr, char *action )
#else
setHasAction( expr, action )
char *expr;
char *action;
#endif
{
	TermEntry *p;
	require(expr!=NULL, "setHasAction: invalid expr");

	p = (TermEntry *) hash_get(Texpr, expr);
	require(p!=NULL, eMsg1("setHasAction: expr '%s' doesn't exist",expr));
	p->action = action;
}

ForcedToken *
#ifdef __STDC__
newForcedToken(char *token, int tnum)
#else
newForcedToken(token, tnum)
char *token;
int tnum;
#endif
{
	ForcedToken *ft = (ForcedToken *) calloc(1, sizeof(ForcedToken));
	require(ft!=NULL, "out of memory");
	ft->token = token;
	ft->tnum = tnum;
	return ft;
}

/*
 * Make a token indirection array that remaps token numbers and then walk
 * the appropriate symbol tables and SynDiag to change token numbers
 */
void
#ifdef __STDC__
RemapForcedTokens(void)
#else
RemapForcedTokens()
#endif
{
	ListNode *p;
	ForcedToken *q;
	unsigned int max_token_number=0;
	int i;

	if ( ForcedTokens == NULL ) return;

	/* find max token num */
	for (p = ForcedTokens->next; p!=NULL; p=p->next)
	{
		q = (ForcedToken *) p->elem;
		if ( q->tnum > max_token_number ) max_token_number = q->tnum;
	}
	fprintf(stderr, "max token number is %d\n", max_token_number);

	/* make token indirection array */
	TokenInd = (int *) calloc(max_token_number+1, sizeof(int));
	LastTokenCounted = TokenNum;
	TokenNum = max_token_number+1;
	require(TokenInd!=NULL, "RemapForcedTokens: cannot allocate TokenInd");

	/* fill token indirection array and change token id htable ; swap token indices */
	for (i=1; i<TokenNum; i++) TokenInd[i] = i;
	for (p = ForcedTokens->next; p!=NULL; p=p->next)
	{
		TermEntry *te;
		int old_pos, t;

		q = (ForcedToken *) p->elem;
		fprintf(stderr, "%s forced to %d\n", q->token, q->tnum);
		te = (TermEntry *) hash_get(Tname, q->token);
		require(te!=NULL, "RemapForcedTokens: token not in hash table");
		old_pos = te->token;
		fprintf(stderr, "Before: TokenInd[old_pos==%d] is %d\n", old_pos, TokenInd[old_pos]);
		fprintf(stderr, "Before: TokenInd[target==%d] is %d\n", q->tnum, TokenInd[q->tnum]);
		q = (ForcedToken *) p->elem;
		t = TokenInd[old_pos];
		TokenInd[old_pos] = q->tnum;
		TokenInd[q->tnum] = t;
		te->token = q->tnum;		/* update token type id symbol table */
		fprintf(stderr, "After: TokenInd[old_pos==%d] is %d\n", old_pos, TokenInd[old_pos]);
		fprintf(stderr, "After: TokenInd[target==%d] is %d\n", q->tnum, TokenInd[q->tnum]);

		/* Change the token number in the sym tab entry for the exprs
		 * at the old position of the token id and the target position
		 */
		/* update expr at target (if any) of forced token id */
		if ( q->tnum < TokenNum )	/* is it a valid position? */
		{
			for (i=0; i<NumLexClasses; i++)
			{
				if ( lclass[i].exprs[q->tnum]!=NULL )
				{
					/* update the symbol table for this expr */
					TermEntry *e = (TermEntry *) hash_get(lclass[i].htable, lclass[i].exprs[q->tnum]);
					require(e!=NULL, "RemapForcedTokens: expr not in hash table");
					e->token = old_pos;
					fprintf(stderr, "found expr '%s' at target %d in lclass[%d]; changed to %d\n",
							lclass[i].exprs[q->tnum], q->tnum, i, old_pos);
				}
			}
		}
		/* update expr at old position (if any) of forced token id */
		for (i=0; i<NumLexClasses; i++)
		{
			if ( lclass[i].exprs[old_pos]!=NULL )
			{
				/* update the symbol table for this expr */
				TermEntry *e = (TermEntry *) hash_get(lclass[i].htable, lclass[i].exprs[old_pos]);
				require(e!=NULL, "RemapForcedTokens: expr not in hash table");
				e->token = q->tnum;
				fprintf(stderr, "found expr '%s' for id %s in lclass[%d]; changed to %d\n",
						lclass[i].exprs[old_pos], q->token, i, q->tnum);
			}
		}
	}

	/* Update SynDiag */
	RemapForcedTokensInSyntaxDiagram((Node *)SynDiag);
}

static void
#ifdef __STDC__
RemapForcedTokensInSyntaxDiagram(Node *p)
#else
RemapForcedTokensInSyntaxDiagram(p)
Node *p;
#endif
{
	Junction *j = (Junction *) p;
	RuleRefNode *r = (RuleRefNode *) p;
	TokNode *t = (TokNode *)p;

	if ( p==NULL ) return;
	require(p->ntype>=1 && p->ntype<=NumNodeTypes,	"Remap...: invalid diagram node");
	switch ( p->ntype )
	{
		case nJunction :
			if ( j->visited ) return;
			if ( j->jtype == EndRule ) return;
			j->visited = TRUE;
			RemapForcedTokensInSyntaxDiagram( j->p1 );
			RemapForcedTokensInSyntaxDiagram( j->p2 );
			j->visited = FALSE;
			return;
		case nRuleRef :
			RemapForcedTokensInSyntaxDiagram( r->next );
			return;
		case nToken :
			if ( t->remapped ) return;	/* we've been here before */
			t->remapped = 1;
			fprintf(stderr, "remapping %d to %d\n", t->token, TokenInd[t->token]);
			t->token = TokenInd[t->token];
			RemapForcedTokensInSyntaxDiagram( t->next );
			return;
		case nAction :
			RemapForcedTokensInSyntaxDiagram( ((ActionNode *)p)->next );
			return;
		default :
			fatal_internal("invalid node type");
	}
}

/*
 * Add a token name.  Return the token number associated with it.  If it already
 * exists, then return the token number assigned to it.
 *
 * Track the order in which tokens are found so that the DLG output maintains
 * that order.  It also lets us map token numbers to strings.
 */
int
#ifdef __STDC__
addTname( char *token )
#else
addTname( token )
char *token;
#endif
{
	TermEntry *p;
	require(token!=NULL, "addTname: invalid token name");

	if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
	p = newTermEntry( token );
	Ttrack( p->str );
	p->token = TokenNum++;
	hash_add(Tname, token, (Entry *)p);
	return p->token;
}

/* This is the same as addTname except we force the TokenNum to be tnum.
 * We don't have to use the Forced token stuff as no tokens will have
 * been defined with #tokens when this is called.  This is only called
 * when a #tokdefs meta-op is used.
 */
int
#ifdef __STDC__
addForcedTname( char *token, int tnum )
#else
addForcedTname( token, tnum )
char *token;
int tnum;
#endif
{
	TermEntry *p;
	require(token!=NULL, "addTname: invalid token name");

	if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
	p = newTermEntry( token );
	Ttrack( p->str );
	p->token = tnum;
	hash_add(Tname, token, (Entry *)p);
	return p->token;
}

/*
 * Add a token expr.  Return the token number associated with it.  If it already
 * exists, then return the token number assigned to it.
 */
int
#ifdef __STDC__
addTexpr( char *expr )
#else
addTexpr( expr )
char *expr;
#endif
{
	TermEntry *p;
	require(expr!=NULL, "addTexpr: invalid regular expression");

	if ( (p=(TermEntry *)hash_get(Texpr, expr)) != NULL ) return p->token;
	p = newTermEntry( expr );
	Ttrack( p->str );
	/* track the order in which they occur */
	list_add(&ExprOrder, (void *)newExpr(p->str));
	p->token = TokenNum++;
	hash_add(Texpr, expr, (Entry *)p);
	return p->token;
}

/* return the token number of 'term'.  Return 0 if no 'term' exists */
int
#ifdef __STDC__
Tnum( char *term )
#else
Tnum( term )
char *term;
#endif
{
	TermEntry *p;
	require(term!=NULL, "Tnum: invalid terminal");
	
	if ( *term=='"' ) p = (TermEntry *) hash_get(Texpr, term);
	else p = (TermEntry *) hash_get(Tname, term);
	if ( p == NULL ) return 0;
	else return p->token;
}

/* associate a Name with an expr.  If both have been already assigned
 * token numbers, then an error is reported.  Add the token or expr
 * that has not been added if no error.  This 'represents' the #token
 * ANTLR pseudo-op.  If both have not been defined, define them both
 * linked to same token number.
 */
void
#ifdef __STDC__
Tklink( char *token, char *expr )
#else
Tklink( token, expr )
char *token;
char *expr;
#endif
{
	TermEntry *p, *q;
	require(token!=NULL && expr!=NULL, "Tklink: invalid token name and/or expr");

	p = (TermEntry *) hash_get(Tname, token);
	q = (TermEntry *) hash_get(Texpr, expr);
	if ( p != NULL && q != NULL )	/* both defined */
	{
		warn( eMsg2("token name %s and rexpr %s already defined; ignored",
					token, expr) );
		return;
	}
	if ( p==NULL && q==NULL )		/* both not defined */
	{
		int t = addTname( token );
		q = newTermEntry( expr );
		hash_add(Texpr, expr, (Entry *)q);
		q->token = t;
		/* note: we use the actual ExprStr array
		 * here as TokenInd doesn't exist yet
		 */
		ExprStr[t] = q->str;
		/* track the order in which they occur */
		list_add(&ExprOrder, (void *)newExpr(q->str));
		return;
	}
	if ( p != NULL )				/* one is defined, one is not */
	{
		q = newTermEntry( expr );
		hash_add(Texpr, expr, (Entry *)q);
		q->token = p->token;
		ExprStr[p->token] = q->str;	/* both expr and token str defined now */
		list_add(&ExprOrder, (void *)newExpr(q->str));
	}
	else							/* trying to associate name with expr here*/
	{
		p = newTermEntry( token );
		hash_add(Tname, token, (Entry *)p);
		p->token = q->token;
		TokenStr[p->token] = p->str;/* both expr and token str defined now */
	}
}

/*
 * Given a string, this function allocates and returns a pointer to a
 * hash table record of size 'sz' whose "str" pointer is reset to a position
 * in the string table.
 */
Entry *
#ifdef __STDC__
newEntry( char *text, int sz )
#else
newEntry( text, sz )
char *text;
int sz;
#endif
{
	Entry *p;
	require(text!=NULL, "new: NULL terminal");
	
	if ( (p = (Entry *) calloc(1,sz)) == 0 )
	{
		fatal_internal("newEntry: out of memory for terminals\n");
		exit(PCCTS_EXIT_FAILURE);
	}
	p->str = mystrdup(text);
	
	return(p);
}

/*
 * add an element to a list.
 *
 * Any non-empty list has a sentinel node whose 'elem' pointer is really
 * a pointer to the last element.  (i.e. length(list) = #elemIn(list)+1).
 * Elements are appended to the list.
 */
void
#ifdef __STDC__
list_add( ListNode **list, void *e )
#else
list_add( list, e )
ListNode **list;
void *e;
#endif
{
	ListNode *p, *tail;
	require(e!=NULL, "list_add: attempting to add NULL list element");

	p = newListNode;
	require(p!=NULL, "list_add: cannot alloc new list node");
	p->elem = e;
	if ( *list == NULL )
	{
		ListNode *sentinel = newListNode;
		require(sentinel!=NULL, "list_add: cannot alloc sentinel node");
		*list=sentinel;
		sentinel->next = p;
		sentinel->elem = (char *)p;		/* set tail pointer */
	}
	else								/* find end of list */
	{
		tail = (ListNode *) (*list)->elem;	/* get tail pointer */
		tail->next = p;
		(*list)->elem = (char *) p;		/* reset tail */
	}
}

void
#ifdef __STDC__
list_apply( ListNode *list, void (*f)(void *) )
#else
list_apply( list, f )
ListNode *list;
void (*f)();
#endif
{
	ListNode *p;
	require(f!=NULL, "list_apply: NULL function to apply");

	if ( list == NULL ) return;
	for (p = list->next; p!=NULL; p=p->next) (*f)( p->elem );
}

			/* F O L L O W  C y c l e  S t u f f */
		
/* make a key based upon (rulename, computation, k value).
 * Computation values are 'i'==FIRST, 'o'==FOLLOW.
 */
char *
#ifdef __STDC__
Fkey( char *rule, int computation, int k )
#else
Fkey( rule, computation, k )
char *rule;
int computation;
int k;
#endif
{
	static char key[MaxRuleName+2+1];
	int i;
	
	if ( k > 255 )
		fatal("k>255 is too big for this implementation of ANTLR!\n");
	if ( (i=strlen(rule)) > MaxRuleName )
		fatal( eMsgd("rule name > max of %d\n", MaxRuleName) );
	strcpy(key,rule);
	key[i] = (int) computation;
	key[i+1] = (char) ((unsigned int) k);
	key[i+2] = '\0';
	return key;
}

/* Push a rule onto the kth FOLLOW stack */
void
#ifdef __STDC__
FoPush( char *rule, int k )
#else
FoPush( rule, k )
char *rule;
int k;
#endif
{
	RuleEntry *r;
	require(rule!=NULL, "FoPush: tried to push NULL rule");
	require(k<=CLL_k,	"FoPush: tried to access non-existent stack");

	/*fprintf(stderr, "FoPush(%s)\n", rule);*/
	r = (RuleEntry *) hash_get(Rname, rule);
	if ( r == NULL ) {fatal_internal( eMsg1("rule %s must be defined but isn't", rule) );}
	if ( FoStack[k] == NULL )		/* Does the kth stack exist yet? */
	{
		/*fprintf(stderr, "allocating FoStack\n");*/
		FoStack[k] = (int *) calloc(FoStackSize, sizeof(int));
		require(FoStack[k]!=NULL, "FoPush: cannot allocate FOLLOW stack\n");
	}
	if ( FoTOS[k] == NULL )
	{
		FoTOS[k]=FoStack[k];
		*(FoTOS[k]) = r->rulenum;
	}
	else
	{
#ifdef MEMCHK
		require(valid(FoStack[k]), "FoPush: invalid FoStack");
#endif
		if ( FoTOS[k] >= &(FoStack[k][FoStackSize-1]) )
			fatal( eMsgd("exceeded max depth of FOLLOW recursion (%d)\n",
						FoStackSize) );
		require(FoTOS[k]>=FoStack[k],
				eMsg1("FoPush: FoStack stack-ptr is playing out of its sandbox",
					  rule));
		++(FoTOS[k]);
		*(FoTOS[k]) = r->rulenum;
	}
	{
		/*
		int *p;
		fprintf(stderr, "FoStack[k=%d]:\n", k);
		for (p=FoStack[k]; p<=FoTOS[k]; p++)
		{
			fprintf(stderr, "\t%s\n", RulePtr[*p]->rname);
		}
		*/
	}
}

/* Pop one rule off of the FOLLOW stack.  TOS ptr is NULL if empty. */
void
#ifdef __STDC__
FoPop( int k )
#else
FoPop( k )
int k;
#endif
{
	require(k<=CLL_k, "FoPop: tried to access non-existent stack");
	/*fprintf(stderr, "FoPop\n");*/
	require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
			"FoPop: FoStack stack-ptr is playing out of its sandbox");
	if ( FoTOS[k] == FoStack[k] ) FoTOS[k] = NULL;
	else (FoTOS[k])--;
}

/* Compute FOLLOW cycle.
 * Mark all FOLLOW sets for rules in cycle as incomplete.
 * Then, save cycle on the cycle list (Cycles) for later resolution.
 * The Cycle is stored in the form:
 *		(head of cycle==croot, rest of rules in cycle==cyclicDep)
 *
 * e.g. (Fo means "FOLLOW of", "-->" means requires or depends on)
 *
 *		Fo(x)-->Fo(a)-->Fo(b)-->Fo(c)-->Fo(x)
 *										   ^----Infinite recursion (cycle)
 *
 * the cycle would be: x -> {a,b,c} or stored as (x,{a,b,c}).  Fo(x) depends
 * on the FOLLOW of a,b, and c.  The root of a cycle is always complete after
 * Fo(x) finishes.  Fo(a,b,c) however are not.  It turns out that all rules
 * in a FOLLOW cycle have the same FOLLOW set.
 */
void
#ifdef __STDC__
RegisterCycle( char *rule, int k )
#else
RegisterCycle( rule, k )
char *rule;
int k;
#endif
{
	CacheEntry *f;
	Cycle *c;
	int *p;
	RuleEntry *r;
	require(rule!=NULL, "RegisterCycle: tried to register NULL rule");
	require(k<=CLL_k,	"RegisterCycle: tried to access non-existent stack");

	/*fprintf(stderr, "RegisterCycle(%s)\n", rule);*/
	/* Find cycle start */
	r = (RuleEntry *) hash_get(Rname, rule);
	require(r!=NULL,eMsg1("rule %s must be defined but isn't", rule));
	require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
			eMsg1("RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox",
				  rule));
/*	if ( FoTOS[k]<FoStack[k]||FoTOS[k]>&(FoStack[k][FoStackSize-1]) )
	{
		fprintf(stderr, "RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox\n",
						rule);
		fprintf(stderr, "RegisterCycle: sp==0x%x out of bounds 0x%x...0x%x\n",
						FoTOS[k], FoStack[k], &(FoStack[k][FoStackSize-1]));
		exit(PCCTS_EXIT_FAILURE);
	}
*/
#ifdef MEMCHK
	require(valid(FoStack[k]), "RegisterCycle: invalid FoStack");
#endif
	for (p=FoTOS[k]; *p != r->rulenum && p >= FoStack[k]; --p) {;}
	require(p>=FoStack[k], "RegisterCycle: FoStack is screwed up beyond belief");
	if ( p == FoTOS[k] ) return;	/* don't worry about cycles to oneself */
	
	/* compute cyclic dependents (rules in cycle except head) */
	c = newCycle;
	require(c!=NULL, "RegisterCycle: couldn't alloc new cycle");
	c->cyclicDep = empty;
	c->croot = *p++;		/* record root of cycle */
	for (; p<=FoTOS[k]; p++)
	{
		/* Mark all dependent rules as incomplete */
		f = (CacheEntry *) hash_get(Fcache, Fkey(RulePtr[*p]->rname,'o',k));
		if ( f==NULL )
		{
			f = newCacheEntry( Fkey(RulePtr[*p]->rname,'o',k) );
			hash_add(Fcache, Fkey(RulePtr[*p]->rname,'o',k), (Entry *)f);
		}
		f->incomplete = TRUE;
		
		set_orel(*p, &(c->cyclicDep)); /* mark rule as dependent of croot */
	}
	list_add(&(Cycles[k]), (void *)c);
}

/* make all rules in cycle complete
 *
 * while ( some set has changed ) do
 *		for each cycle do
 *			if degree of FOLLOW set for croot > old degree then
 *				update all FOLLOW sets for rules in cyclic dependency
 *				change = TRUE
 *			endif
 *		endfor
 * endwhile
 */
void
#ifdef __STDC__
ResolveFoCycles( int k )
#else
ResolveFoCycles( k )
int k;
#endif
{
	ListNode *p, *q;
	Cycle *c;
	int changed = 1;
	CacheEntry *f,*g;
	int r,i;
	unsigned d;
	
	/*fprintf(stderr, "Resolving following cycles for %d\n", k);*/
	while ( changed )
	{
		changed = 0;
		i = 0;
		for (p = Cycles[k]->next; p!=NULL; p=p->next)
		{
			c = (Cycle *) p->elem;
			/*fprintf(stderr, "cycle %d: %s -->", i++, RulePtr[c->croot]->rname);*/
			/*s_fprT(stderr, c->cyclicDep);*/
			/*fprintf(stderr, "\n");*/
			f = (CacheEntry *)
					hash_get(Fcache, Fkey(RulePtr[c->croot]->rname,'o',k));
			require(f!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[c->croot]->rname) );
			if ( (d=set_deg(f->fset)) > c->deg )
			{
				/*fprintf(stderr, "Fo(%s) has changed\n", RulePtr[c->croot]->rname);*/
				changed = 1;
				c->deg = d;		/* update cycle FOLLOW set degree */
				while ( !set_nil(c->cyclicDep) )
				{
					r = set_int(c->cyclicDep);
					set_rm(r, c->cyclicDep);
					/*fprintf(stderr, "updating Fo(%s)\n", RulePtr[r]->rname);*/
					g = (CacheEntry *)
							hash_get(Fcache, Fkey(RulePtr[r]->rname,'o',k));
					require(g!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[r]->rname) );
					set_orin(&(g->fset), f->fset);
					g->incomplete = FALSE;
				}
			}
		}
		if ( i == 1 ) changed = 0;	/* if only 1 cycle, no need to repeat */
	}
	/* kill Cycle list */
	for (q = Cycles[k]->next; q != NULL; q=p)
	{
		p = q->next;
		set_free( ((Cycle *)q->elem)->cyclicDep );
		free((char *)q);
	}
	free( (char *)Cycles[k] );
	Cycles[k] = NULL;
}


			/* P r i n t i n g  S y n t a x  D i a g r a m s */

static void
#ifdef __STDC__
pBlk( Junction *q, int btype )
#else
pBlk( q, btype )
Junction *q;
int btype;
#endif
{
	int k,a;
	Junction *alt, *p;

	q->end->pvisited = TRUE;
	if ( btype == aLoopBegin )
	{
		require(q->p2!=NULL, "pBlk: invalid ()* block");
		PRINT(q->p1);
		alt = (Junction *)q->p2;
		PRINT(alt->p1);
		if ( PrintAnnotate )
		{
			printf(" /* Opt ");
			k = 1;
			while ( !set_nil(alt->fset[k]) )
			{
				s_fprT(stdout, alt->fset[k]);
				if ( k++ == CLL_k ) break;
				if ( !set_nil(alt->fset[k]) ) printf(", ");
			}
			printf(" */\n");
		}
		return;
	}
	for (a=1,alt=q; alt != NULL; alt= (Junction *) alt->p2, a++)
	{
		if ( alt->p1 != NULL ) PRINT(alt->p1);
		if ( PrintAnnotate )
		{
			printf( " /* [%d] ", alt->altnum);
			k = 1;
			while ( !set_nil(alt->fset[k]) )
			{
				s_fprT(stdout, alt->fset[k]);
				if ( k++ == CLL_k ) break;
				if ( !set_nil(alt->fset[k]) ) printf(", ");
			}
			if ( alt->p2 == NULL && btype == aOptBlk )
				printf( " (optional branch) */\n");
			else printf( " */\n");
		}

		/* ignore implied empty alt of Plus blocks */
		if ( alt->p2 != NULL && ((Junction *)alt->p2)->ignore ) break;

		if ( alt->p2 != NULL && !(((Junction *)alt->p2)->p2==NULL && btype == aOptBlk) )
		{
			if ( pLevel == 1 )
			{
				printf("\n");
				if ( a+1==pAlt1 || a+1==pAlt2 ) printf("=>");
				printf("\t");
			}
			else printf(" ");
			printf("|");
			if ( pLevel == 1 )
			{
				p = (Junction *) ((Junction *)alt->p2)->p1;
				while ( p!=NULL )
				{
					if ( p->ntype==nAction )
					{
						p=(Junction *)((ActionNode *)p)->next;
						continue;
					}
					if ( p->ntype!=nJunction )
					{
						break;
					}
					if ( p->jtype==EndBlk || p->jtype==EndRule )
					{
						p = NULL;
						break;
					}
					p = (Junction *)p->p1;
				}
				if ( p==NULL ) printf("\n\t");	/* Empty alt? */
			}
		}
	}
	q->end->pvisited = FALSE;
}

/* How to print out a junction */
void
#ifdef __STDC__
pJunc( Junction *q )
#else
pJunc( q )
Junction *q;
#endif
{
	int dum_k;
	int doing_rule;
	require(q!=NULL, "pJunc: NULL node");
	require(q->ntype==nJunction, "pJunc: not junction");
	
	if ( q->pvisited == TRUE ) return;
	q->pvisited = TRUE;
	switch ( q->jtype )
	{
		case aSubBlk :
			if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
			if ( q->end->p1 != NULL && ((Junction *)q->end->p1)->ntype==nJunction &&
				 ((Junction *)q->end->p1)->jtype == EndRule ) doing_rule = 1;
			else doing_rule = 0;
			pLevel++;
			if ( pLevel==1 )
			{
				if ( pAlt1==1 ) printf("=>");
				printf("\t");
			}
			else printf(" ");
			if ( doing_rule )
			{
				if ( pLevel==1 ) printf(" ");
				pBlk(q,q->jtype);
			}
			else {
				printf("(");
				if ( pLevel==1 ) printf(" ");
				pBlk(q,q->jtype);
				if ( pLevel>1 ) printf(" ");
				printf(")");
			}
			if ( q->guess ) printf("?");
			pLevel--;
			if ( PrintAnnotate ) freeBlkFsets(q);
			if ( q->end->p1 != NULL ) PRINT(q->end->p1);
			break;
		case aOptBlk :
			if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
			pLevel++;
			if ( pLevel==1 )
			{
				if ( pAlt1==1 ) printf("=>");
				printf("\t");
			}
			else printf(" ");
			printf("{");
			if ( pLevel==1 ) printf(" ");
			pBlk(q,q->jtype);
			if ( pLevel>1 ) printf(" ");
			else printf("\n\t");
			printf("}");
			pLevel--;
			if ( PrintAnnotate ) freeBlkFsets(q);
			if ( q->end->p1 != NULL ) PRINT(q->end->p1);
			break;
		case aLoopBegin :
			if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
			pLevel++;
			if ( pLevel==1 )
			{
				if ( pAlt1==1 ) printf("=>");
				printf("\t");
			}
			else printf(" ");
			printf("(");
			if ( pLevel==1 ) printf(" ");
			pBlk(q,q->jtype);
			if ( pLevel>1 ) printf(" ");
			else printf("\n\t");
			printf(")*");
			pLevel--;
			if ( PrintAnnotate ) freeBlkFsets(q);
			if ( q->end->p1 != NULL ) PRINT(q->end->p1);
			break;
		case aLoopBlk :
			if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
			pBlk(q,q->jtype);
			if ( PrintAnnotate ) freeBlkFsets(q);
			break;
		case aPlusBlk :
			if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
			pLevel++;
			if ( pLevel==1 )
			{
				if ( pAlt1==1 ) printf("=>");
				printf("\t");
			}
			else printf(" ");
			printf("(");
			if ( pLevel==1 ) printf(" ");
			pBlk(q,q->jtype);
			if ( pLevel>1 ) printf(" ");
			printf(")+");
			pLevel--;
			if ( PrintAnnotate ) freeBlkFsets(q);
			if ( q->end->p1 != NULL ) PRINT(q->end->p1);
			break;
		case EndBlk :
			break;
		case RuleBlk :
			printf( "\n%s :\n", q->rname);
			PRINT(q->p1);
			if ( q->p2 != NULL ) PRINT(q->p2);
			break;
		case Generic :
			if ( q->p1 != NULL ) PRINT(q->p1);
			q->pvisited = FALSE;
			if ( q->p2 != NULL ) PRINT(q->p2);
			break;
		case EndRule :
			printf( "\n\t;\n");
			break;
	}
	q->pvisited = FALSE;
}

/* How to print out a rule reference node */
void
#ifdef __STDC__
pRuleRef( RuleRefNode *p )
#else
pRuleRef( p )
RuleRefNode *p;
#endif
{
	require(p!=NULL, "pRuleRef: NULL node");
	require(p->ntype==nRuleRef, "pRuleRef: not rule ref node");
	
	printf( " %s", p->text);
	PRINT(p->next);
}

/* How to print out a terminal node */
void
#ifdef __STDC__
pToken( TokNode *p )
#else
pToken( p )
TokNode *p;
#endif
{
	require(p!=NULL, "pToken: NULL node");
	require(p->ntype==nToken, "pToken: not token node");

	if ( p->wild_card ) printf(" .");
	printf( " %s", TerminalString(p->token));
	PRINT(p->next);
}

/* How to print out a terminal node */
void
#ifdef __STDC__
pAction( ActionNode *p )
#else
pAction( p )
ActionNode *p;
#endif
{
	require(p!=NULL, "pAction: NULL node");
	require(p->ntype==nAction, "pAction: not action node");
	
	PRINT(p->next);
}

					/* F i l l  F o l l o w  L i s t s */

/*
 * Search all rules for all rule reference nodes, q to rule, r.
 * Add q->next to follow list dangling off of rule r.
 * i.e.
 *
 *		r: -o-R-o-->o--> Ptr to node following rule r in another rule
 *					|
 *					o--> Ptr to node following another reference to r.
 *
 * This is the data structure employed to avoid FOLLOW set computation.  We
 * simply compute the FIRST (reach) of the EndRule Node which follows the
 * list found at the end of all rules which are referenced elsewhere.  Rules
 * not invoked by other rules have no follow list (r->end->p1==NULL).
 * Generally, only start symbols are not invoked by another rule.
 *
 * Note that this mechanism also gives a free cross-reference mechanism.
 *
 * The entire syntax diagram is layed out like this:
 *
 * SynDiag
 *	|
 *	v
 *	o-->R1--o
 *	|
 *	o-->R2--o
 *	|
 *	...
 *	|
 *	o-->Rn--o
 *
 */
void
#ifdef __STDC__
FoLink( Node *p )
#else
FoLink( p )
Node *p;
#endif
{
	RuleEntry *q;
	Junction *j = (Junction *) p;
	RuleRefNode *r = (RuleRefNode *) p;

	if ( p==NULL ) return;
	require(p->ntype>=1 && p->ntype<=NumNodeTypes,
			eMsgd("FoLink: invalid diagram node: ntype==%d",p->ntype));
	switch ( p->ntype )
	{
		case nJunction :
			if ( j->fvisited ) return;
			if ( j->jtype == EndRule ) return;
			j->fvisited = TRUE;
			FoLink( j->p1 );
			FoLink( j->p2 );
			return;
		case nRuleRef :
			if ( r->linked ) return;
			q = (RuleEntry *) hash_get(Rname, r->text);
			if ( q == NULL )
			{
				warnFL( eMsg1("rule %s not defined",r->text), FileStr[r->file], r->line );
			}
			else
			{
				if ( r->parms!=NULL && RulePtr[q->rulenum]->pdecl==NULL )
				{
					warnFL( eMsg1("rule %s accepts no parameter(s)", r->text),
							FileStr[r->file], r->line );
				}
				if ( r->parms==NULL && RulePtr[q->rulenum]->pdecl!=NULL )
				{
					warnFL( eMsg1("rule %s requires parameter(s)", r->text),
							FileStr[r->file], r->line );
				}
				if ( r->assign!=NULL && RulePtr[q->rulenum]->ret==NULL )
				{
					warnFL( eMsg1("rule %s yields no return value(s)", r->text),
							FileStr[r->file], r->line );
				}
				if ( r->assign==NULL && RulePtr[q->rulenum]->ret!=NULL )
				{
					warnFL( eMsg1("rule %s returns a value(s)", r->text),
							FileStr[r->file], r->line );
				}
				if ( !r->linked )
				{
					addFoLink(	r->next, r->rname, RulePtr[q->rulenum] );
					r->linked = TRUE;
				}
			}
			FoLink( r->next );
			return;
		case nToken :
			FoLink( ((TokNode *)p)->next );
			return;
		case nAction :
			FoLink( ((ActionNode *)p)->next );
			return;
		default :
			fatal_internal("invalid node type");
	}
}

/*
 * Add a reference to the end of a rule.
 *
 * 'r' points to the RuleBlk node in a rule.  r->end points to the last node
 * (EndRule jtype) in a rule.
 *
 * Initial:
 *		r->end --> 	o
 *
 * After:
 *		r->end --> 	o-->o--> Ptr to node following rule r in another rule
 *						|
 *						o--> Ptr to node following another reference to r.
 *
 * Note that the links are added to the head of the list so that r->end->p1
 * always points to the most recently added follow-link.  At the end, it should
 * point to the last reference found in the grammar (starting from the 1st rule).
 */
void
#ifdef __STDC__
addFoLink( Node *p, char *rname, Junction *r )
#else
addFoLink( p, rname, r )
Node *p;
char *rname;
Junction *r;
#endif
{
	Junction *j;
	require(r!=NULL,				"addFoLink: incorrect rule graph");
	require(r->end!=NULL,			"addFoLink: incorrect rule graph");
	require(r->end->jtype==EndRule,	"addFoLink: incorrect rule graph");
	require(p!=NULL,				"addFoLink: NULL FOLLOW link");

	j = newJunction();
	j->rname = rname;			/* rname on follow links point to target rule */
	j->p1 = p;					/* link to other rule */
	j->p2 = (Node *) r->end->p1;/* point to head of list */
	r->end->p1 = (Node *) j;	/* reset head to point to new node */
}

void
#ifdef __STDC__
GenCrossRef( Junction *p )
#else
GenCrossRef( p )
Junction *p;
#endif
{
	set a;
	Junction *j;
	RuleEntry *q;
	unsigned e;
	require(p!=NULL, "GenCrossRef: why are you passing me a null grammar?");

	printf("Cross Reference:\n\n");
	a = empty;
	for (; p!=NULL; p = (Junction *)p->p2)
	{
		printf("Rule %11s referenced by {", p->rname);
		/* make a set of rules for uniqueness */
		for (j = (Junction *)(p->end)->p1; j!=NULL; j = (Junction *)j->p2)
		{
			q = (RuleEntry *) hash_get(Rname, j->rname);
			require(q!=NULL, "GenCrossRef: FoLinks are screwed up");
			set_orel(q->rulenum, &a);
		}
		for (; !set_nil(a); set_rm(e, a))
		{
			e = set_int(a);
			printf(" %s", RulePtr[e]->rname);
		}
		printf(" }\n");
	}
	set_free( a );
}