build.c

来自「SRI international 发布的OAA框架软件」· C语言 代码 · 共 814 行 · 第 1/2 页

/*
 * 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 __USE_PROTOS
makeBlk( Graph g1, int approx, char * pFirstSetSymbol )
#else
makeBlk( g1, approx, pFirstSetSymbol )
Graph g1;
int approx;
char * pFirstSetSymbol;
#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, pFirstSetSymbol);
	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 __USE_PROTOS
makeLoop( Graph g1, int approx, char * pFirstSetSymbol )
#else
makeLoop( g1, approx, pFirstSetSymbol)
Graph g1;
int approx;
char * pFirstSetSymbol;
#endif
{
	Junction *back, *front, *begin;
	Graph g;
	require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");

	back = newJunction();
	front = newJunction();
	begin = newJunction();
	g = emptyAlt3();
	((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, pFirstSetSymbol);
	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 __USE_PROTOS
makePlus( Graph g1, int approx, char * pFirstSetSymbol)
#else
makePlus( g1, approx, pFirstSetSymbol)
Graph g1;
int approx;
char * pFirstSetSymbol;
#endif
{
	int has_empty_alt_already = 0;
	Graph g;
	Junction *j2, *j3, *first_alt;
	Junction *last_alt=NULL, *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, pFirstSetSymbol);
	((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 __USE_PROTOS
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;
}

/*  MR21
 *
 *  There is code in genBlk which recognizes the node created
 *  by emptyAlt() as a special case and bypasses it.  We don't
 *  want this to happen for the optBlk.
 */

Graph
#ifdef __USE_PROTOS
emptyAlt3( void )
#else
emptyAlt3( )
#endif
{
	Junction *j1, *j2, *j3;
	Graph g;

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

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

TokNode *
#ifdef __USE_PROTOS
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 */
    memset( (char *) p, 0, sizeof(TokNode));        /* MR10 */
	p->ntype = nToken;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->altstart = NULL;

	return p;
}

RuleRefNode *
#ifdef __USE_PROTOS
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 */
    memset( (char *) p, 0, sizeof(RuleRefNode));        /* MR10 */
	p->ntype = nRuleRef;
	p->rname = CurRule;
	p->file = CurFile;
	p->line = zzline;
	p->astnode = ASTinclude;
	p->altstart = NULL;
	
	return p;
}

static int junctionSeqNumber=0;         /* MR10 */

Junction *
#ifdef __USE_PROTOS
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 */
    memset( (char *) p, 0, sizeof(Junction));       /* MR10 */
	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");
    p->seq=++junctionSeqNumber;     /* MR10 */

	return p;
}

ActionNode *
#ifdef __USE_PROTOS
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 */
    memset( (char *) p, 0, sizeof(ActionNode));     /* MR10 */
	p->ntype = nAction;
	p->next = NULL;						/* NULL the ptr we used */
	p->done = 0;
	p->pred_fail = NULL;
	p->guardpred = NULL;
    p->ampersandPred = 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 __USE_PROTOS
makelocks( void )
#else
makelocks( )
#endif
{
	char *p = (char *) calloc(CLL_k+1, sizeof(char));
	require(p!=NULL, "cannot allocate lock array");
	
	return p;
}

#if 0
** #ifdef __USE_PROTOS
** void my_memset(char *p,char value,int count)
** #else
** void my_memset(p,value,count)
**   char      *p;
**   char      value;
**   int       count;
** #endif
** {
**    int      i;
**
**    for (i=0; i<count; i++) {
**     p[i]=value;
**   };
** }
#endif