libpccts_133MR7/antlr/build.c - third_party/vtr-verilog-to-routing - Git at Google

 /*
  * build.c -- functions associated with building syntax diagrams.
  *
  * $Id: build.c,v 1.3 95/06/15 18:07:00 parrt Exp $
  * $Revision: 1.3 $
  *
  * 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"

 #define SetBlk(g, t, approx) {						   			\
 			((Junction *)g.left)->jtype = t;					\
 			((Junction *)g.left)->approx = approx;				\
 			((Junction *)g.left)->end = (Junction *) g.right;	\
 			((Junction *)g.right)->jtype = EndBlk;}

 /* Add the parameter string 'parm' to the parms field of a block-type junction
  * g.left points to the sentinel node on a block.  i.e. g.left->p1 points to
  * the actual junction with its jtype == some block-type.
  */
 void
 #ifdef __STDC__
 addParm( Node *p, char *parm )
 #else
 addParm( p, parm )
 Node *p;
 char *parm;
 #endif
 {
 	char *q = (char *) malloc( strlen(parm) + 1 );
 	require(p!=NULL, "addParm: NULL object\n");
 	require(q!=NULL, "addParm: unable to alloc parameter\n");

 	strcpy(q, parm);
 	if ( p->ntype == nRuleRef )
 	{
 		((RuleRefNode *)p)->parms = q;
 	}
 	else if ( p->ntype == nJunction )
 	{
 		((Junction *)p)->parm = q;	/* only one parameter allowed on subrules */
 	}
 	else fatal_internal("addParm: invalid node for adding parm");
 }

 /*
  * Build an action node for the syntax diagram
  *
  * buildAction(ACTION) ::= --o-->ACTION-->o--
  *
  * Where o is a junction node.
  */
 Graph
 #ifdef __STDC__
 buildAction( char *action, int file, int line, int is_predicate )
 #else
 buildAction( action, file, line, is_predicate )
 char *action;
 int file;
 int line;
 int is_predicate;
 #endif
 {
 	Junction *j1, *j2;
 	Graph g;
 	ActionNode *a;
 	require(action!=NULL, "buildAction: invalid action");

 	j1 = newJunction();
 	j2 = newJunction();
 	a = newActionNode();
 	a->action = (char *) malloc( strlen(action)+1 );
 	require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
 	strcpy(a->action, action);
 	j1->p1 = (Node *) a;
 	a->next = (Node *) j2;
 	a->is_predicate = is_predicate;
 	g.left = (Node *) j1; g.right = (Node *) j2;
 	a->file = file;
 	a->line = line;
 	a->rname = "not filled in";
 	return g;
 }

 /*
  * Build a token node for the syntax diagram
  *
  * buildToken(TOKEN) ::= --o-->TOKEN-->o--
  *
  * Where o is a junction node.
  */
 Graph
 #ifdef __STDC__
 buildToken( char *text )
 #else
 buildToken( text )
 char *text;
 #endif
 {
 	Junction *j1, *j2;
 	Graph g;
 	TokNode *t;
 	require(text!=NULL, "buildToken: invalid token name");

 	j1 = newJunction();
 	j2 = newJunction();
 	t = newTokNode();
 	t->altstart = CurAltStart;
 	if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
 	else {t->label=TRUE; t->token = addTname( text );}
 	j1->p1 = (Node *) t;
 	t->next = (Node *) j2;
 	g.left = (Node *) j1; g.right = (Node *) j2;
 	return g;
 }

 /*
  * Build a wild-card node for the syntax diagram
  *
  * buildToken(TOKEN) ::= --o-->'.'-->o--
  *
  * Where o is a junction node.
  */
 Graph
 #ifdef __STDC__
 buildWildCard( char *text )
 #else
 buildWildCard( text )
 char *text;
 #endif
 {
 	Junction *j1, *j2;
 	Graph g;
 	TokNode *t;
 	TCnode *w;
 	TermEntry *p;
 	require(text!=NULL, "buildWildCard: invalid token name");

 	j1 = newJunction();
 	j2 = newJunction();
 	t = newTokNode();

 	/* If the ref a wild card, make a token class for it */
 	if ( Tnum(WildCardString) == 0 )
 	{
 		w = newTCnode;
 	  	w->tok = addTname( WildCardString );
 		set_orel(w->tok, &imag_tokens);
 		set_orel(w->tok, &tokclasses);
 		WildCardToken = w->tok;
 		require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL,
 				"hash table mechanism is broken");
 		p->classname = 1;	/* entry is class name, not token */
 		p->tclass = w;		/* save ptr to this tclass def */
 		list_add(&tclasses, (char *)w);
 	}
 	else {
 		p=(TermEntry *)hash_get(Tname, WildCardString);
 		require( p!= NULL, "hash table mechanism is broken");
 		w = p->tclass;
 	}

 	t->token = w->tok;
 	t->wild_card = 1;
 	t->tclass = w;

 	t->altstart = CurAltStart;
 	j1->p1 = (Node *) t;
 	t->next = (Node *) j2;
 	g.left = (Node *) j1; g.right = (Node *) j2;
 	return g;
 }

 void
 #ifdef __STDC__
 setUpperRange(TokNode *t, char *text)
 #else
 setUpperRange(t, text)
 TokNode *t;
 char *text;
 #endif
 {
 	require(t!=NULL, "setUpperRange: NULL token node");
 	require(text!=NULL, "setUpperRange: NULL token string");

 	if ( *text == '"' ) {t->upper_range = addTexpr( text );}
 	else {t->upper_range = addTname( text );}
 }

 /*
  * Build a rule reference node of the syntax diagram
  *
  * buildRuleRef(RULE) ::= --o-->RULE-->o--
  *
  * Where o is a junction node.
  *
  * If rule 'text' has been defined already, don't alloc new space to store string.
  * Set r->text to point to old copy in string table.
  */
 Graph
 #ifdef __STDC__
 buildRuleRef( char *text )
 #else
 buildRuleRef( text )
 char *text;
 #endif
 {
 	Junction *j1, *j2;
 	Graph g;
 	RuleRefNode *r;
 	RuleEntry *p;
 	require(text!=NULL, "buildRuleRef: invalid rule name");

 	j1 = newJunction();
 	j2 = newJunction();
 	r = newRNode();
 	r->altstart = CurAltStart;
 	r->assign = NULL;
 	if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
 	else r->text = mystrdup( text );
 	j1->p1  = (Node *) r;
 	r->next = (Node *) j2;
 	g.left = (Node *) j1; g.right = (Node *) j2;
 	return g;
 }

 /*
  * Or two subgraphs into one graph via:
  *
  * Or(G1, G2) ::= --o-G1-o--
  *                  |    ^
  *					v    |
  *                  o-G2-o
  *
  * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
  * If, however, the G1 altnum is 0, make it 1 and then
  * make G2 altnum = G1 altnum + 1.
  */
 Graph
 #ifdef __STDC__
 Or( Graph g1, Graph g2 )
 #else
 Or( g1, g2 )
 Graph g1;
 Graph g2;
 #endif
 {
 	Graph g;
 	require(g1.left != NULL, "Or: invalid graph");
 	require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");

 	((Junction *)g1.left)->p2 = g2.left;
 	((Junction *)g2.right)->p1 = g1.right;
 	/* set altnums */
 	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
 	((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1;
 	g.left = g2.left;
 	g.right = g1.right;
 	return g;
 }

 /*
  * Catenate two subgraphs
  *
  * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
  * Cat(NULL,G2)::= --o-G2-o--
  * Cat(G1,NULL)::= --o-G1-o--
  */
 Graph
 #ifdef __STDC__
 Cat( Graph g1, Graph g2 )
 #else
 Cat( g1, g2 )
 Graph g1;
 Graph g2;
 #endif
 {
 	Graph g;

 	if ( g1.left == NULL && g1.right == NULL ) return g2;
 	if ( g2.left == NULL && g2.right == NULL ) return g1;
 	((Junction *)g1.right)->p1 = g2.left;
 	g.left = g1.left;
 	g.right = g2.right;
 	return g;
 }

 /*
  * Make a subgraph an optional block
  *
  * makeOpt(G) ::= --o-->o-G-o-->o--
  *                      | 	    ^
  *						v  	    |
  *					    o-------o
  *
  * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
  *
  * The node on the far right is added so that every block owns its own
  * EndBlk node.
  */
 Graph
 #ifdef __STDC__
 makeOpt( Graph g1, int approx )
 #else
 makeOpt( g1, approx )
 Graph g1;
 int approx;
 #endif
 {
 	Junction *j1,*j2,*p;
 	Graph g;
 	require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");

 	j1 = newJunction();
 	j2 = newJunction();
 	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
 	g = emptyAlt();
 	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
 	((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1;
 	for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2)
 		{;}										/* find last alt */
 	p->p2 = g.left;								/* add optional alternative */
 	((Junction *)g.right)->p1 = (Node *)j2;		/* opt alt points to EndBlk */
 	g1.right = (Node *)j2;
 	SetBlk(g1, aOptBlk, approx);
 	j1->p1 = g1.left;							/* add generic node in front */
 	g.left = (Node *) j1;
 	g.right = g1.right;

 	return g;
 }

 /*
  * Make a graph into subblock
  *
  * makeBlk(G) ::= --o-->o-G-o-->o--
  *
  * The node on the far right is added so that every block owns its own
  * EndBlk node.
  */
 Graph
 #ifdef __STDC__
 makeBlk( Graph g1, int approx )
 #else
 makeBlk( g1, approx )
 Graph g1;
 int approx;
 #endif
 {
 	Junction *j,*j2;
 	Graph g;
 	require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");

 	j = newJunction();
 	j2 = newJunction();
 	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
 	g1.right = (Node *)j2;
 	SetBlk(g1, aSubBlk, approx);
 	j->p1 = g1.left;							/* add node in front */
 	g.left = (Node *) j;
 	g.right = g1.right;

 	return g;
 }

 /*
  * Make a subgraph into a loop (closure) block -- (...)*
  *
  * makeLoop(G) ::=       |---|
  *					     v   |
  *			   --o-->o-->o-G-o-->o--
  *                   |           ^
  *                   v           |
  *					 o-----------o
  *
  * After making loop, always place generic node out front.  It becomes
  * the start of enclosing block.  The aLoopBlk is the target of the loop.
  *
  * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
  * to the aLoopBlk node.  Node with which we can branch past loop == aLoopBegin and
  * one which is loop target == aLoopBlk.
  * The branch-past (initial) aLoopBegin node has end
  * pointing to the last EndBlk node.  The loop-target node has end==NULL.
  *
  * Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
  */
 Graph
 #ifdef __STDC__
 makeLoop( Graph g1, int approx )
 #else
 makeLoop( g1, approx )
 Graph g1;
 int approx;
 #endif
 {
 	Junction *back, *front, *begin;
 	Graph g;
 	require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");

 	back = newJunction();
 	front = newJunction();
 	begin = newJunction();
 	g = emptyAlt();
 	((Junction *)g1.right)->p2 = g1.left;		/* add loop branch to G */
 	((Junction *)g1.right)->p1 = (Node *) back;	/* add node to G at end */
 	((Junction *)g1.right)->jtype = EndBlk;		/* mark 1st EndBlk node */
 	((Junction *)g1.left)->jtype = aLoopBlk;	/* mark 2nd aLoopBlk node */
 	((Junction *)g1.left)->end = (Junction *) g1.right;
 	((Junction *)g1.left)->lock = makelocks();
 	((Junction *)g1.left)->pred_lock = makelocks();
 	g1.right = (Node *) back;
 	begin->p1 = (Node *) g1.left;
 	g1.left = (Node *) begin;
 	begin->p2 = (Node *) g.left;				/* make bypass arc */
 	((Junction *)g.right)->p1 = (Node *) back;
 	SetBlk(g1, aLoopBegin, approx);
 	front->p1 = g1.left;						/* add node to front */
 	g1.left = (Node *) front;

 	return g1;
 }

 /*
  * Make a subgraph into a plus block -- (...)+ -- 1 or more times
  *
  * makePlus(G) ::=	 |---|
  *					 v   |
  *			   --o-->o-G-o-->o--
  *
  * After making loop, always place generic node out front.  It becomes
  * the start of enclosing block.  The aPlusBlk is the target of the loop.
  *
  * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
  * to the aPlusBlk node.
  *
  * Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
  */
 Graph
 #ifdef __STDC__
 makePlus( Graph g1, int approx )
 #else
 makePlus( g1, approx )
 Graph g1;
 int approx;
 #endif
 {
 	int has_empty_alt_already = 0;
 	Graph g;
 	Junction *j2, *j3, *first_alt;
 	Junction *last_alt, *p;
 	require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");

 	first_alt = (Junction *)g1.left;
 	j2 = newJunction();
 	j3 = newJunction();
 	if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
 	((Junction *)g1.right)->p2 = g1.left;		/* add loop branch to G */
 	((Junction *)g1.right)->p1 = (Node *) j2;	/* add node to G at end */
 	((Junction *)g1.right)->jtype = EndBlk;		/* mark 1st EndBlk node */
 	g1.right = (Node *) j2;
 	SetBlk(g1, aPlusBlk, approx);
 	((Junction *)g1.left)->lock = makelocks();
 	((Junction *)g1.left)->pred_lock = makelocks();
 	j3->p1 = g1.left;							/* add node to front */
 	g1.left = (Node *) j3;

 	/* add an optional branch which is the "exit" branch of loop */
 	/* FIRST, check to ensure that there does not already exist
 	 * an optional path.
 	 */
 	/* find last alt */
 	for(p=first_alt; p!=NULL; p=(Junction *)p->p2)
 	{
 		if ( p->p1->ntype == nJunction &&
 			 p->p1!=NULL &&
 			 ((Junction *)p->p1)->jtype==Generic &&
 			 ((Junction *)p->p1)->p1!=NULL &&
 			 ((Junction *)((Junction *)p->p1)->p1)->jtype==EndBlk )
 		{
 			has_empty_alt_already = 1;
 		}
 		last_alt = p;
 	}
 	if ( !has_empty_alt_already )
 	{
 		require(last_alt!=NULL, "last_alt==NULL; bad (..)+");
 		g = emptyAlt();
 		last_alt->p2 = g.left;
 		((Junction *)g.right)->p1 = (Node *) j2;

 		/* make sure lookahead computation ignores this alt for
 		* FIRST("(..)+"); but it's still used for computing the FIRST
 		* of each alternative.
 		*/
 		((Junction *)g.left)->ignore = 1;
 	}

 	return g1;
 }

 /*
  * Return an optional path:  --o-->o--
  */
 Graph
 #ifdef __STDC__
 emptyAlt( void )
 #else
 emptyAlt( )
 #endif
 {
 	Junction *j1, *j2;
 	Graph g;

 	j1 = newJunction();
 	j2 = newJunction();
 	j1->p1 = (Node *) j2;
 	g.left = (Node *) j1;
 	g.right = (Node *) j2;

 	return g;
 }

 /* N o d e  A l l o c a t i o n */

 TokNode *
 #ifdef __STDC__
 newTokNode( void )
 #else
 newTokNode( )
 #endif
 {
 	static TokNode *FreeList = NULL;
 	TokNode *p, *newblk;

 	if ( FreeList == NULL )
 	{
 		newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
 		if ( newblk == NULL )
 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
 		for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
 		{
 			p->next = (Node *)FreeList;	/* add all new token nodes to FreeList */
 			FreeList = p;
 		}
 	}
 	p = FreeList;
 	FreeList = (TokNode *)FreeList->next;/* remove a TokNode node */
 	p->next = NULL;						/* NULL the ptr we used */

 	p->ntype = nToken;
 	p->rname = CurRule;
 	p->file = CurFile;
 	p->line = zzline;
 	p->altstart = NULL;

 	return p;
 }

 RuleRefNode *
 #ifdef __STDC__
 newRNode( void )
 #else
 newRNode( )
 #endif
 {
 	static RuleRefNode *FreeList = NULL;
 	RuleRefNode *p, *newblk;

 	if ( FreeList == NULL )
 	{
 		newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
 		if ( newblk == NULL )
 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
 		for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
 		{
 			p->next = (Node *)FreeList;	/* add all new rref nodes to FreeList */
 			FreeList = p;
 		}
 	}
 	p = FreeList;
 	FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */
 	p->next = NULL;						/* NULL the ptr we used */

 	p->ntype = nRuleRef;
 	p->rname = CurRule;
 	p->file = CurFile;
 	p->line = zzline;
 	p->astnode = ASTinclude;
 	p->altstart = NULL;

 	return p;
 }

 Junction *
 #ifdef __STDC__
 newJunction( void )
 #else
 newJunction( )
 #endif
 {
 	static Junction *FreeList = NULL;
 	Junction *p, *newblk;

 	if ( FreeList == NULL )
 	{
 		newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
 		if ( newblk == NULL )
 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
 		for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
 		{
 			p->p1 = (Node *)FreeList;	/* add all new Junction nodes to FreeList */
 			FreeList = p;
 		}
 	}
 	p = FreeList;
 	FreeList = (Junction *)FreeList->p1;/* remove a Junction node */
 	p->p1 = NULL;						/* NULL the ptr we used */

 	p->ntype = nJunction;	p->visited = 0;
 	p->jtype = Generic;
 	p->rname = CurRule;
 	p->file = CurFile;
 	p->line = zzline;
 	p->exception_label = NULL;
 	p->fset = (set *) calloc(CLL_k+1, sizeof(set));
 	require(p->fset!=NULL, "cannot allocate fset in newJunction");

 	return p;
 }

 ActionNode *
 #ifdef __STDC__
 newActionNode( void )
 #else
 newActionNode( )
 #endif
 {
 	static ActionNode *FreeList = NULL;
 	ActionNode *p, *newblk;

 	if ( FreeList == NULL )
 	{
 		newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
 		if ( newblk == NULL )
 			fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
 		for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
 		{
 			p->next = (Node *)FreeList;	/* add all new Action nodes to FreeList */
 			FreeList = p;
 		}
 	}
 	p = FreeList;
 	FreeList = (ActionNode *)FreeList->next;/* remove an Action node */
 	p->ntype = nAction;
 	p->next = NULL;						/* NULL the ptr we used */
 	p->done = 0;
 	p->pred_fail = NULL;
 	p->guardpred = NULL;

 	return p;
 }

 /*
  * allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
  * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
  * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
  *
  * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
  * of lookahead.
  */
 char *
 #ifdef __STDC__
 makelocks( void )
 #else
 makelocks( )
 #endif
 {
 	char *p = (char *) calloc(CLL_k+1, sizeof(char));
 	require(p!=NULL, "cannot allocate lock array");

 	return p;
 }
	/*
	* build.c -- functions associated with building syntax diagrams.
	*
	* $Id: build.c,v 1.3 95/06/15 18:07:00 parrt Exp $
	* $Revision: 1.3 $
	*
	* 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"

	#define SetBlk(g, t, approx) { \
	((Junction *)g.left)->jtype = t; \
	((Junction *)g.left)->approx = approx; \
	((Junction )g.left)->end = (Junction ) g.right; \
	((Junction *)g.right)->jtype = EndBlk;}

	/* Add the parameter string 'parm' to the parms field of a block-type junction
	* g.left points to the sentinel node on a block. i.e. g.left->p1 points to
	* the actual junction with its jtype == some block-type.
	*/
	void
	#ifdef __STDC__
	addParm( Node p, char parm )
	#else
	addParm( p, parm )
	Node *p;
	char *parm;
	#endif
	{
	char q = (char ) malloc( strlen(parm) + 1 );
	require(p!=NULL, "addParm: NULL object\n");
	require(q!=NULL, "addParm: unable to alloc parameter\n");

	strcpy(q, parm);
	if ( p->ntype == nRuleRef )
	{
	((RuleRefNode *)p)->parms = q;
	}
	else if ( p->ntype == nJunction )
	{
	((Junction )p)->parm = q; / only one parameter allowed on subrules */
	}
	else fatal_internal("addParm: invalid node for adding parm");
	}

	/*
	* Build an action node for the syntax diagram
	*
	* buildAction(ACTION) ::= --o-->ACTION-->o--
	*
	* Where o is a junction node.
	*/
	Graph
	#ifdef __STDC__
	buildAction( char *action, int file, int line, int is_predicate )
	#else
	buildAction( action, file, line, is_predicate )
	char *action;
	int file;
	int line;
	int is_predicate;
	#endif
	{
	Junction j1, j2;
	Graph g;
	ActionNode *a;
	require(action!=NULL, "buildAction: invalid action");

	j1 = newJunction();
	j2 = newJunction();
	a = newActionNode();
	a->action = (char *) malloc( strlen(action)+1 );
	require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
	strcpy(a->action, action);
	j1->p1 = (Node *) a;
	a->next = (Node *) j2;
	a->is_predicate = is_predicate;
	g.left = (Node ) j1; g.right = (Node ) j2;
	a->file = file;
	a->line = line;
	a->rname = "not filled in";
	return g;
	}

	/*
	* Build a token node for the syntax diagram
	*
	* buildToken(TOKEN) ::= --o-->TOKEN-->o--
	*
	* Where o is a junction node.
	*/
	Graph
	#ifdef __STDC__
	buildToken( char *text )
	#else
	buildToken( text )
	char *text;
	#endif
	{
	Junction j1, j2;
	Graph g;
	TokNode *t;
	require(text!=NULL, "buildToken: invalid token name");

	j1 = newJunction();
	j2 = newJunction();
	t = newTokNode();
	t->altstart = CurAltStart;
	if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
	else {t->label=TRUE; t->token = addTname( text );}
	j1->p1 = (Node *) t;
	t->next = (Node *) j2;
	g.left = (Node ) j1; g.right = (Node ) j2;
	return g;
	}

	/*
	* Build a wild-card node for the syntax diagram
	*
	* buildToken(TOKEN) ::= --o-->'.'-->o--
	*
	* Where o is a junction node.
	*/
	Graph
	#ifdef __STDC__
	buildWildCard( char *text )
	#else
	buildWildCard( text )
	char *text;
	#endif
	{
	Junction j1, j2;
	Graph g;
	TokNode *t;
	TCnode *w;
	TermEntry *p;
	require(text!=NULL, "buildWildCard: invalid token name");

	j1 = newJunction();
	j2 = newJunction();
	t = newTokNode();

	/* If the ref a wild card, make a token class for it */
	if ( Tnum(WildCardString) == 0 )
	{
	w = newTCnode;
	w->tok = addTname( WildCardString );
	set_orel(w->tok, &imag_tokens);
	set_orel(w->tok, &tokclasses);
	WildCardToken = w->tok;
	require((p=(TermEntry *)hash_get(Tname, WildCardString)) != NULL,
	"hash table mechanism is broken");
	p->classname = 1; /* entry is class name, not token */
	p->tclass = w; /* save ptr to this tclass def */
	list_add(&tclasses, (char *)w);
	}
	else {
	p=(TermEntry *)hash_get(Tname, WildCardString);
	require( p!= NULL, "hash table mechanism is broken");
	w = p->tclass;
	}

	t->token = w->tok;
	t->wild_card = 1;
	t->tclass = w;

	t->altstart = CurAltStart;
	j1->p1 = (Node *) t;
	t->next = (Node *) j2;
	g.left = (Node ) j1; g.right = (Node ) j2;
	return g;
	}

	void
	#ifdef __STDC__
	setUpperRange(TokNode t, char text)
	#else
	setUpperRange(t, text)
	TokNode *t;
	char *text;
	#endif
	{
	require(t!=NULL, "setUpperRange: NULL token node");
	require(text!=NULL, "setUpperRange: NULL token string");

	if ( *text == '"' ) {t->upper_range = addTexpr( text );}
	else {t->upper_range = addTname( text );}
	}

	/*
	* Build a rule reference node of the syntax diagram
	*
	* buildRuleRef(RULE) ::= --o-->RULE-->o--
	*
	* Where o is a junction node.
	*
	* If rule 'text' has been defined already, don't alloc new space to store string.
	* Set r->text to point to old copy in string table.
	*/
	Graph
	#ifdef __STDC__
	buildRuleRef( char *text )
	#else
	buildRuleRef( text )
	char *text;
	#endif
	{
	Junction j1, j2;
	Graph g;
	RuleRefNode *r;
	RuleEntry *p;
	require(text!=NULL, "buildRuleRef: invalid rule name");

	j1 = newJunction();
	j2 = newJunction();
	r = newRNode();
	r->altstart = CurAltStart;
	r->assign = NULL;
	if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
	else r->text = mystrdup( text );
	j1->p1 = (Node *) r;
	r->next = (Node *) j2;
	g.left = (Node ) j1; g.right = (Node ) j2;
	return g;
	}

	/*
	* Or two subgraphs into one graph via:
	*
	* Or(G1, G2) ::= --o-G1-o--
	* \| ^
	* v \|
	* o-G2-o
	*
	* Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
	* If, however, the G1 altnum is 0, make it 1 and then
	* make G2 altnum = G1 altnum + 1.
	*/
	Graph
	#ifdef __STDC__
	Or( Graph g1, Graph g2 )
	#else
	Or( g1, g2 )
	Graph g1;
	Graph g2;
	#endif
	{
	Graph g;
	require(g1.left != NULL, "Or: invalid graph");
	require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");

	((Junction *)g1.left)->p2 = g2.left;
	((Junction *)g2.right)->p1 = g1.right;
	/* set altnums */
	if ( ((Junction )g1.left)->altnum == 0 ) ((Junction )g1.left)->altnum = 1;
	((Junction )g2.left)->altnum = ((Junction )g1.left)->altnum + 1;
	g.left = g2.left;
	g.right = g1.right;
	return g;
	}

	/*
	* Catenate two subgraphs
	*
	* Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
	* Cat(NULL,G2)::= --o-G2-o--
	* Cat(G1,NULL)::= --o-G1-o--
	*/
	Graph
	#ifdef __STDC__
	Cat( Graph g1, Graph g2 )
	#else
	Cat( g1, g2 )
	Graph g1;
	Graph g2;
	#endif
	{
	Graph g;

	if ( g1.left == NULL && g1.right == NULL ) return g2;
	if ( g2.left == NULL && g2.right == NULL ) return g1;
	((Junction *)g1.right)->p1 = g2.left;
	g.left = g1.left;
	g.right = g2.right;
	return g;
	}

	/*
	* Make a subgraph an optional block
	*
	* makeOpt(G) ::= --o-->o-G-o-->o--
	* \| ^
	* v \|
	* o-------o
	*
	* Note that this constructs {A\|B\|...\|Z} as if (A\|B\|...\|Z\|) was found.
	*
	* The node on the far right is added so that every block owns its own
	* EndBlk node.
	*/
	Graph
	#ifdef __STDC__
	makeOpt( Graph g1, int approx )
	#else
	makeOpt( g1, approx )
	Graph g1;
	int approx;
	#endif
	{
	Junction j1,j2,*p;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");

	j1 = newJunction();
	j2 = newJunction();
	((Junction )g1.right)->p1 = (Node ) j2; /* add node to G at end */
	g = emptyAlt();
	if ( ((Junction )g1.left)->altnum == 0 ) ((Junction )g1.left)->altnum = 1;
	((Junction )g.left)->altnum = ((Junction )g1.left)->altnum + 1;
	for(p=(Junction )g1.left; p->p2!=NULL; p=(Junction )p->p2)
	{;} /* find last alt */
	p->p2 = g.left; /* add optional alternative */
	((Junction )g.right)->p1 = (Node )j2; /* opt alt points to EndBlk */
	g1.right = (Node *)j2;
	SetBlk(g1, aOptBlk, approx);
	j1->p1 = g1.left; /* add generic node in front */
	g.left = (Node *) j1;
	g.right = g1.right;

	return g;
	}

	/*
	* Make a graph into subblock
	*
	* makeBlk(G) ::= --o-->o-G-o-->o--
	*
	* The node on the far right is added so that every block owns its own
	* EndBlk node.
	*/
	Graph
	#ifdef __STDC__
	makeBlk( Graph g1, int approx )
	#else
	makeBlk( g1, approx )
	Graph g1;
	int approx;
	#endif
	{
	Junction j,j2;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");

	j = newJunction();
	j2 = newJunction();
	((Junction )g1.right)->p1 = (Node ) j2; /* add node to G at end */
	g1.right = (Node *)j2;
	SetBlk(g1, aSubBlk, approx);
	j->p1 = g1.left; /* add node in front */
	g.left = (Node *) j;
	g.right = g1.right;

	return g;
	}

	/*
	* Make a subgraph into a loop (closure) block -- (...)*
	*
	* makeLoop(G) ::= \|---\|
	* v \|
	* --o-->o-->o-G-o-->o--
	* \| ^
	* v \|
	* o-----------o
	*
	* After making loop, always place generic node out front. It becomes
	* the start of enclosing block. The aLoopBlk is the target of the loop.
	*
	* Loop blks have TWO EndBlk nodes--the far right and the node that loops back
	* to the aLoopBlk node. Node with which we can branch past loop == aLoopBegin and
	* one which is loop target == aLoopBlk.
	* The branch-past (initial) aLoopBegin node has end
	* pointing to the last EndBlk node. The loop-target node has end==NULL.
	*
	* Loop blocks have a set of locks (from 1..CLL_k) on the aLoopBlk node.
	*/
	Graph
	#ifdef __STDC__
	makeLoop( Graph g1, int approx )
	#else
	makeLoop( g1, approx )
	Graph g1;
	int approx;
	#endif
	{
	Junction back, front, *begin;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");

	back = newJunction();
	front = newJunction();
	begin = newJunction();
	g = emptyAlt();
	((Junction )g1.right)->p2 = g1.left; / add loop branch to G */
	((Junction )g1.right)->p1 = (Node ) back; /* add node to G at end */
	((Junction )g1.right)->jtype = EndBlk; / mark 1st EndBlk node */
	((Junction )g1.left)->jtype = aLoopBlk; / mark 2nd aLoopBlk node */
	((Junction )g1.left)->end = (Junction ) g1.right;
	((Junction *)g1.left)->lock = makelocks();
	((Junction *)g1.left)->pred_lock = makelocks();
	g1.right = (Node *) back;
	begin->p1 = (Node *) g1.left;
	g1.left = (Node *) begin;
	begin->p2 = (Node ) g.left; / make bypass arc */
	((Junction )g.right)->p1 = (Node ) back;
	SetBlk(g1, aLoopBegin, approx);
	front->p1 = g1.left; /* add node to front */
	g1.left = (Node *) front;

	return g1;
	}

	/*
	* Make a subgraph into a plus block -- (...)+ -- 1 or more times
	*
	* makePlus(G) ::= \|---\|
	* v \|
	* --o-->o-G-o-->o--
	*
	* After making loop, always place generic node out front. It becomes
	* the start of enclosing block. The aPlusBlk is the target of the loop.
	*
	* Plus blks have TWO EndBlk nodes--the far right and the node that loops back
	* to the aPlusBlk node.
	*
	* Plus blocks have a set of locks (from 1..CLL_k) on the aPlusBlk node.
	*/
	Graph
	#ifdef __STDC__
	makePlus( Graph g1, int approx )
	#else
	makePlus( g1, approx )
	Graph g1;
	int approx;
	#endif
	{
	int has_empty_alt_already = 0;
	Graph g;
	Junction j2, j3, *first_alt;
	Junction last_alt, p;
	require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");

	first_alt = (Junction *)g1.left;
	j2 = newJunction();
	j3 = newJunction();
	if ( ((Junction )g1.left)->altnum == 0 ) ((Junction )g1.left)->altnum = 1;
	((Junction )g1.right)->p2 = g1.left; / add loop branch to G */
	((Junction )g1.right)->p1 = (Node ) j2; /* add node to G at end */
	((Junction )g1.right)->jtype = EndBlk; / mark 1st EndBlk node */
	g1.right = (Node *) j2;
	SetBlk(g1, aPlusBlk, approx);
	((Junction *)g1.left)->lock = makelocks();
	((Junction *)g1.left)->pred_lock = makelocks();
	j3->p1 = g1.left; /* add node to front */
	g1.left = (Node *) j3;

	/* add an optional branch which is the "exit" branch of loop */
	/* FIRST, check to ensure that there does not already exist
	* an optional path.
	*/
	/* find last alt */
	for(p=first_alt; p!=NULL; p=(Junction *)p->p2)
	{
	if ( p->p1->ntype == nJunction &&
	p->p1!=NULL &&
	((Junction *)p->p1)->jtype==Generic &&
	((Junction *)p->p1)->p1!=NULL &&
	((Junction )((Junction )p->p1)->p1)->jtype==EndBlk )
	{
	has_empty_alt_already = 1;
	}
	last_alt = p;
	}
	if ( !has_empty_alt_already )
	{
	require(last_alt!=NULL, "last_alt==NULL; bad (..)+");
	g = emptyAlt();
	last_alt->p2 = g.left;
	((Junction )g.right)->p1 = (Node ) j2;

	/* make sure lookahead computation ignores this alt for
	* FIRST("(..)+"); but it's still used for computing the FIRST
	* of each alternative.
	*/
	((Junction *)g.left)->ignore = 1;
	}

	return g1;
	}

	/*
	* Return an optional path: --o-->o--
	*/
	Graph
	#ifdef __STDC__
	emptyAlt( void )
	#else
	emptyAlt( )
	#endif
	{
	Junction j1, j2;
	Graph g;

	j1 = newJunction();
	j2 = newJunction();
	j1->p1 = (Node *) j2;
	g.left = (Node *) j1;
	g.right = (Node *) j2;

	return g;
	}

	/* N o d e A l l o c a t i o n */

	TokNode *
	#ifdef __STDC__
	newTokNode( void )
	#else
	newTokNode( )
	#endif
	{
	static TokNode *FreeList = NULL;
	TokNode p, newblk;

	if ( FreeList == NULL )
	{
	newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
	if ( newblk == NULL )
	fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
	for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
	{
	p->next = (Node )FreeList; / add all new token nodes to FreeList */
	FreeList = p;
	}
	}
	p = FreeList;
	FreeList = (TokNode )FreeList->next;/ remove a TokNode node */
	p->next = NULL; /* NULL the ptr we used */

	p->ntype = nToken;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->altstart = NULL;

	return p;
	}

	RuleRefNode *
	#ifdef __STDC__
	newRNode( void )
	#else
	newRNode( )
	#endif
	{
	static RuleRefNode *FreeList = NULL;
	RuleRefNode p, newblk;

	if ( FreeList == NULL )
	{
	newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
	if ( newblk == NULL )
	fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
	for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
	{
	p->next = (Node )FreeList; / add all new rref nodes to FreeList */
	FreeList = p;
	}
	}
	p = FreeList;
	FreeList = (RuleRefNode )FreeList->next;/ remove a Junction node */
	p->next = NULL; /* NULL the ptr we used */

	p->ntype = nRuleRef;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->astnode = ASTinclude;
	p->altstart = NULL;

	return p;
	}

	Junction *
	#ifdef __STDC__
	newJunction( void )
	#else
	newJunction( )
	#endif
	{
	static Junction *FreeList = NULL;
	Junction p, newblk;

	if ( FreeList == NULL )
	{
	newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
	if ( newblk == NULL )
	fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
	for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
	{
	p->p1 = (Node )FreeList; / add all new Junction nodes to FreeList */
	FreeList = p;
	}
	}
	p = FreeList;
	FreeList = (Junction )FreeList->p1;/ remove a Junction node */
	p->p1 = NULL; /* NULL the ptr we used */

	p->ntype = nJunction; p->visited = 0;
	p->jtype = Generic;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->exception_label = NULL;
	p->fset = (set *) calloc(CLL_k+1, sizeof(set));
	require(p->fset!=NULL, "cannot allocate fset in newJunction");

	return p;
	}

	ActionNode *
	#ifdef __STDC__
	newActionNode( void )
	#else
	newActionNode( )
	#endif
	{
	static ActionNode *FreeList = NULL;
	ActionNode p, newblk;

	if ( FreeList == NULL )
	{
	newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
	if ( newblk == NULL )
	fatal_internal(eMsg1("out of memory while building rule '%s'",CurRule));
	for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
	{
	p->next = (Node )FreeList; / add all new Action nodes to FreeList */
	FreeList = p;
	}
	}
	p = FreeList;
	FreeList = (ActionNode )FreeList->next;/ remove an Action node */
	p->ntype = nAction;
	p->next = NULL; /* NULL the ptr we used */
	p->done = 0;
	p->pred_fail = NULL;
	p->guardpred = NULL;

	return p;
	}

	/*
	* allocate the array of locks (1..CLL_k) used to inhibit infinite recursion.
	* Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
	* Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
	*
	* if ( lock[k]==TRUE ) then we have been here before looking for k tokens
	* of lookahead.
	*/
	char *
	#ifdef __STDC__
	makelocks( void )
	#else
	makelocks( )
	#endif
	{
	char p = (char ) calloc(CLL_k+1, sizeof(char));
	require(p!=NULL, "cannot allocate lock array");

	return p;
	}