misc.c

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

	return p->token;
}

/* return the token number of 'term'.  Return 0 if no 'term' exists */
int
#ifdef __USE_PROTOS
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 __USE_PROTOS
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 __USE_PROTOS
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 __USE_PROTOS
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 */
	}
}

/* MR10 list_free() frees the ListNode elements in the list       */
/* MR10   if freeData then free the data elements of the list too */

void
#ifdef __USE_PROTOS
list_free(ListNode **list,int freeData)
#else
list_free(list,freeData)
  ListNode      **list;
  int           freeData;
#endif
{
	ListNode *p;
    ListNode *next;

	if (list == NULL) return;
    if (*list == NULL) return;
	for (p=*list; p != NULL; p=next) {
      next=p->next;
      if (freeData && p->elem != NULL) {
        free( (char *) p->elem);
      };
      free( (char *) p);
    };
    *list=NULL;
}

void
#ifdef __USE_PROTOS
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 );
}

/* MR27 */

#ifdef __USE_PROTOS
int list_search_cstring(ListNode *list, char * cstring)
#else
int list_search_cstring(list, cstring)
  ListNode * list;
  char * cstring;
#endif
{
	ListNode *p;
	if (list == NULL ) return 0;
	for (p = list->next; p!=NULL; p=p->next) {
		if (p->elem == NULL) continue;
		if (0 == strcmp((char *) p->elem , cstring)) return 1;
	}
	return 0;
}

			/* 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.
 */

/* MR10  Make the key all characters so it can be read easily   */
/* MR10    by a simple dump program.  Also, separates           */
/* MR10   'o' and 'i' from rule name                            */

char *
#ifdef __USE_PROTOS
Fkey( char *rule, int computation, int k )
#else
Fkey( rule, computation, k )
char *rule;
int computation;
int k;
#endif
{
	static char key[MaxRuleName+2+2+1];                                 /* MR10 */
	int i;
	
	if ( k > 99 )                                                       /* MR10 */
		fatal("k>99 is too big for this implementation of ANTLR!\n");   /* MR10 */
	if ( (i=strlen(rule)) > MaxRuleName )                               /* MR10 */
		fatal( eMsgd("rule name > max of %d\n", MaxRuleName) );         /* MR10 */
	strcpy(key,rule);

/* MR10 */     key[i]='*';
/* MR10 */     key[i+1] = (char) computation; /* MR20 G. Hobbelt */
/* MR10 */     if (k < 10) {
/* MR10 */       key[i+2] = (char) ( '0' + k);
/* MR10 */  	 key[i+3] = '\0';
/* MR10 */     } else {
/* MR10 */       key[i+2] = (char) ( '0' + k/10);
/* MR10 */       key[i+3] = (char) ( '0' + k % 10);
/* MR10 */       key[i+4] = '\0';
/* MR10 */     };

	return key;
}

/* Push a rule onto the kth FOLLOW stack */
void
#ifdef __USE_PROTOS
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 __USE_PROTOS
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 __USE_PROTOS
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 __USE_PROTOS
ResolveFoCycles( int k )
#else
ResolveFoCycles( k )
int k;
#endif
{
	ListNode *p, *q;
	Cycle *c;
	int changed = 1;
	CacheEntry *f,*g;
	int r;
/*  int i;  */  /* MR10 not useful */
	unsigned d;

    unsigned    *cursor;        /* MR10 */
    unsigned    *origin;        /* MR10 */
	
	/*fprintf(stderr, "Resolving following cycles for %d\n", k);*/
	while ( changed )
	{
		changed = 0;
/* MR10 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 */

/* MR10 */      origin=set_pdq(c->cyclicDep);
/* MR10 */      for (cursor=origin; *cursor != nil; cursor++) {
/* MR10 */         r=*cursor;

/********		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;
				}
/* MR10 */      free( (char *) origin);
/* MR10 */      origin=NULL;
			}
		}
/* MR10 - this if statement appears to be meaningless since i is always 0 */
/* MR10		if ( i == 1 ) changed = 0;	*/ /* if only 1 cycle, no need to repeat */