fset2.c

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

/*
 * fset2.c
 *
 * Compute FIRST sets for full LL(k)
 *
 * 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-2001
 */

#include <stdio.h>
#include "pcctscfg.h"
#include <stdlib.h>

#ifdef PCCTS_USE_STDARG
#include <stdarg.h>
#else
#include <varargs.h>
#endif

#include "set.h"
#include "syn.h"
#include "hash.h"
#include "generic.h"
#include "dlgdef.h"

/* ick! globals.  Used by permute() to track which elements of a set have been used */

static int *findex;
set *fset;              /* MR11 make global */
static unsigned **ftbl;
static set *constrain; /* pts into fset. constrains tToken() to 'constrain' */
int ConstrainSearch;
int maxk;               /* set to initial k upon tree construction request */
                        /* MR11 make global */
static Tree *FreeList = NULL;

#ifdef __USE_PROTOS
static int tmember_of_context(Tree *, Predicate *);
#else
static int tmember_of_context();
#endif

#if TREE_DEBUG
set     set_of_tnodes_in_use;
int     stop_on_tnode_seq_number=(-1);     /* (-1) to disable */
#endif

/* Do root
 * Then each sibling
 */

void
#ifdef __USE_PROTOS
preorder( Tree *tree )
#else
preorder( tree )
Tree *tree;
#endif
{
	if ( tree == NULL ) return;
	if ( tree->down != NULL ) fprintf(stderr, " (");
	if ( tree->token == ALT ) fprintf(stderr, " ALT");
	else fprintf(stderr, " %s", TerminalString(tree->token));
	if ( tree->token==EpToken ) fprintf(stderr, "(%d)", tree->v.rk);
	preorder(tree->down);
	if ( tree->down != NULL ) fprintf(stderr, " )");
	preorder(tree->right);
}

#ifdef __USE_PROTOS
int MR_tree_matches_constraints(int k,set * constrain,Tree *t)
#else
int MR_tree_matches_constraints(k,constrain,t)
  int       k;
  set *     constrain;
  Tree *    t;
#endif
{
  int       i;
  Tree      *u;

  if (k == 0) return 1;

  /* for testing guard predicates: if the guard tree is shorter
     than the constraint then it is a match.  The reason is that
     a guard of (A B) should be equivalent to a guard of (A B . . .)
     where "." matches every token.  Thus a match which runs out
     of tree before constraint is a match.
  */

  if (t == NULL) return 1;
  require (set_deg(constrain[0]) == 1,
            "MR_tree_matches_constraints: set_deg != 1");
  i=set_int(constrain[0]);
  if (t->token != i) return 0;
  if (k-1 == 0) return 1;
  for (u=t->down; u != NULL; u=u->right) {
    if (MR_tree_matches_constraints(k-1,&constrain[1],u)) {
       return 1;
    };
  };
  return 0;
}

/* check the depth of each primary sibling to see that it is exactly
 * k deep. e.g.;
 *
 *	ALT
 *   |
 *   A ------- B
 *   |         |
 *   C -- D    E
 *
 * Remove all branches <= k deep.
 *
 * Added by TJP 9-23-92 to make the LL(k) constraint mechanism to work.
 */

static int pruneCount=0;
static int prunePeak=200;

Tree *
#ifdef __USE_PROTOS
prune( Tree *t, int k )
#else
prune( t, k )
Tree *t;
int k;
#endif
{
    pruneCount++;
    if (pruneCount > prunePeak+100) {
      prunePeak=pruneCount;
#if 0
***   fprintf(stderr,"pruneCount=%d\n",pruneCount);
/***  preorder(t);   ***/
***   fprintf(stderr,"\n",pruneCount);
#endif
    };
    if ( t == NULL ) {
        pruneCount--;
        return NULL;
    };
    if ( t->token == ALT ) fatal_internal("prune: ALT node in FIRST tree");
    if ( t->right!=NULL ) t->right = prune(t->right, k);
    if ( k>1 )
	{
		if ( t->down!=NULL ) t->down = prune(t->down, k-1);
		if ( t->down == NULL )
		{
			Tree *r = t->right;
			t->right = NULL;
			Tfree(t);
            pruneCount--;
			return r;
		}
	}
    pruneCount--;
    return t;
}

/* build a tree (root child1 child2 ... NULL) */
#ifdef PCCTS_USE_STDARG
Tree *tmake(Tree *root, ...)
#else
Tree *tmake(va_alist)
va_dcl
#endif
{
	Tree *w;
	va_list ap;
	Tree *child, *sibling=NULL, *tail=NULL;
#ifndef PCCTS_USE_STDARG
	Tree *root;
#endif

#ifdef PCCTS_USE_STDARG
	va_start(ap, root);
#else
	va_start(ap);
	root = va_arg(ap, Tree *);
#endif
	child = va_arg(ap, Tree *);
	while ( child != NULL )
	{
#ifdef DUM
		/* added "find end of child" thing TJP March 1994 */
		for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */
#else
		w = child;
#endif

		if ( sibling == NULL ) {sibling = child; tail = w;}
		else {tail->right = child; tail = w;}
		child = va_arg(ap, Tree *);
	}

	/* was "root->down = sibling;" */
	if ( root==NULL ) root = sibling;
	else root->down = sibling;

	va_end(ap);
	return root;
}

Tree *
#ifdef __USE_PROTOS
tnode( int tok )
#else
tnode( tok )
int tok;
#endif
{
	Tree *p, *newblk;
	static int n=0;
	
	if ( FreeList == NULL )
	{
		/*fprintf(stderr, "tnode: %d more nodes\n", TreeBlockAllocSize);*/
		if ( TreeResourceLimit > 0 )
		{
			if ( (n+TreeBlockAllocSize) >= TreeResourceLimit )
			{
				fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
				fprintf(stderr, " hit analysis resource limit while analyzing alts %d and %d %s\n",
								CurAmbigAlt1,
								CurAmbigAlt2,
								CurAmbigbtype);
				exit(PCCTS_EXIT_FAILURE);
			}
		}
		newblk = (Tree *)calloc(TreeBlockAllocSize, sizeof(Tree));
		if ( newblk == NULL )
		{
			fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
			fprintf(stderr, " out of memory while analyzing alts %d and %d %s\n",
							CurAmbigAlt1,
							CurAmbigAlt2,
							CurAmbigbtype);
			exit(PCCTS_EXIT_FAILURE);
		}
		n += TreeBlockAllocSize;
		for (p=newblk; p<&(newblk[TreeBlockAllocSize]); p++)
		{
			p->right = FreeList;	/* add all new Tree nodes to Free List */
			FreeList = p;
		}
	}
	p = FreeList;
	FreeList = FreeList->right;		/* remove a tree node */
	p->right = NULL;				/* zero out ptrs */
	p->down = NULL;
	p->token = tok;

    TnodesAllocated++;                                      /* MR10 */
    TnodesInUse++;                                          /* MR10 */
    if (TnodesInUse > TnodesPeak) TnodesPeak=TnodesInUse;   /* MR10 */

#ifdef TREE_DEBUG
	require(!p->in_use, "tnode: node in use!");
	p->in_use = 1;
    p->seq=TnodesAllocated;
    set_orel( (unsigned) TnodesAllocated,&set_of_tnodes_in_use);
    if (stop_on_tnode_seq_number == p->seq) {
      fprintf(stderr,"\n*** just allocated tnode #%d ***\n",
            stop_on_tnode_seq_number);
    };
#endif
	return p;
}

static Tree *
#ifdef __USE_PROTOS
eofnode( int k )
#else
eofnode( k )
int k;
#endif
{
	Tree *t=NULL;
	int i;

	for (i=1; i<=k; i++)
	{
		t = tmake(tnode((TokenInd!=NULL?TokenInd[EofToken]:EofToken)), t, NULL);
	}
	return t;
}



void
#ifdef __USE_PROTOS
_Tfree( Tree *t )
#else
_Tfree( t )
Tree *t;
#endif
{
	if ( t!=NULL )
	{
#ifdef TREE_DEBUG
        if (t->seq == stop_on_tnode_seq_number) {
           fprintf(stderr,"\n*** just freed tnode #%d ***\n",t->seq);
        };
		require(t->in_use, "_Tfree: node not in use!");
		t->in_use = 0;
        set_rm( (unsigned) t->seq,set_of_tnodes_in_use);
#endif
		t->right = FreeList;
		FreeList = t;
        TnodesInUse--;                   /* MR10 */
	}
}

/* tree duplicate */
Tree *
#ifdef __USE_PROTOS
tdup( Tree *t )
#else
tdup( t )
Tree *t;
#endif
{
	Tree *u;
	
	if ( t == NULL ) return NULL;
	u = tnode(t->token);
	u->v.rk = t->v.rk;
	u->right = tdup(t->right);
	u->down = tdup(t->down);
	return u;
}

/* tree duplicate (assume tree is a chain downwards) */
Tree *
#ifdef __USE_PROTOS
tdup_chain( Tree *t )
#else
tdup_chain( t )
Tree *t;
#endif
{
	Tree *u;
	
	if ( t == NULL ) return NULL;
	u = tnode(t->token);
	u->v.rk = t->v.rk;
	u->down = tdup(t->down);
	return u;
}

Tree *
#ifdef __USE_PROTOS
tappend( Tree *t, Tree *u )
#else
tappend( t, u )
Tree *t;
Tree *u;
#endif
{
	Tree *w;

/*** fprintf(stderr, "tappend(");
 *** preorder(t); fprintf(stderr, ",");
 *** preorder(u); fprintf(stderr, " )\n");
*/
	if ( t == NULL ) return u;
	if ( t->token == ALT && t->right == NULL ) return tappend(t->down, u);
	for (w=t; w->right!=NULL; w=w->right) {;}
	w->right = u;
	return t;
}

/* dealloc all nodes in a tree */
void
#ifdef __USE_PROTOS
Tfree( Tree *t )
#else
Tfree( t )
Tree *t;
#endif
{
	if ( t == NULL ) return;
	Tfree( t->down );
	Tfree( t->right );
	_Tfree( t );
}

/* find all children (alts) of t that require remaining_k nodes to be LL_k
 * tokens long.
 *
 * t-->o
 *     |
 *     a1--a2--...--an		<-- LL(1) tokens
 *     |   |        |
 *     b1  b2  ...  bn		<-- LL(2) tokens
 *     |   |        |
 *     .   .        .
 *     .   .        .
 *     z1  z2  ...  zn		<-- LL(LL_k) tokens
 *
 * We look for all [Ep] needing remaining_k nodes and replace with u.
 * u is not destroyed or actually used by the tree (a copy is made).
 */
Tree *
#ifdef __USE_PROTOS
tlink( Tree *t, Tree *u, int remaining_k )
#else
tlink( t, u, remaining_k )
Tree *t;
Tree *u;
int remaining_k;
#endif
{
	Tree *p;
	require(remaining_k!=0, "tlink: bad tree");

	if ( t==NULL ) return NULL;
	/*fprintf(stderr, "tlink: u is:"); preorder(u); fprintf(stderr, "\n");*/
	if ( t->token == EpToken && t->v.rk == remaining_k )
	{
		require(t->down==NULL, "tlink: invalid tree");
		if ( u == NULL ) {
/* MR10 */  Tree  *tt=t->right;
/* MR10 */  _Tfree(t);
/* MR10 */  return tt;
        };
		p = tdup( u );
		p->right = t->right;
		_Tfree( t );
		return p;
	}
	t->down = tlink(t->down, u, remaining_k);
	t->right = tlink(t->right, u, remaining_k);
	return t;
}

/* remove as many ALT nodes as possible while still maintaining semantics */
Tree *
#ifdef __USE_PROTOS
tshrink( Tree *t )
#else
tshrink( t )
Tree *t;
#endif
{
	if ( t == NULL ) return NULL;
	t->down = tshrink( t->down );
	t->right = tshrink( t->right );
	if ( t->down == NULL )
	{
		if ( t->token == ALT )
		{
			Tree *u = t->right;
			_Tfree(t);
			return u;			/* remove useless alts */
		}
		return t;
	}

	/* (? (ALT (? ...)) s) ==> (? (? ...) s) where s = sibling, ? = match any */
	if ( t->token == ALT && t->down->right == NULL)
	{
		Tree *u = t->down;
		u->right = t->right;
		_Tfree( t );
		return u;
	}
	/* (? (A (ALT t)) s) ==> (? (A t) s) where A is a token; s,t siblings */
	if ( t->token != ALT && t->down->token == ALT && t->down->right == NULL )
	{
		Tree *u = t->down->down;
		_Tfree( t->down );
		t->down = u;
		return t;
	}
	return t;
}

Tree *
#ifdef __USE_PROTOS
tflatten( Tree *t )
#else
tflatten( t )
Tree *t;
#endif
{
	if ( t == NULL ) return NULL;
	t->down = tflatten( t->down );
	t->right = tflatten( t->right );
	if ( t->down == NULL ) return t;
	
	if ( t->token == ALT )
	{
		Tree *u;
		/* find tail of children */
		for (u=t->down; u->right!=NULL; u=u->right) {;}
		u->right = t->right;
		u = t->down;
		_Tfree( t );
		return u;
	}
	return t;
}

Tree *
#ifdef __USE_PROTOS
tJunc( Junction *p, int k, set *rk )
#else
tJunc( p, k, rk )
Junction *p;
int k;
set *rk;
#endif
{
	Tree *t=NULL, *u=NULL;
	Junction *alt;
	Tree *tail=NULL, *r;

#ifdef DBG_TRAV
	fprintf(stderr, "tJunc(%d): %s in rule %s\n", k,
			decodeJType[p->jtype], ((Junction *)p)->rname);
#endif

/* MR14 */    if (AlphaBetaTrace && p->alpha_beta_guess_end) {
/* MR14 */         warnFL(
/* MR14 */           "not possible to compute follow set for alpha in an \"(alpha)? beta\" block.  ",
/* MR14 */                 FileStr[p->file],p->line);
/* MR14 */         MR_alphaBetaTraceReport();
/* MR14 */    };

/* MR14 */    if (p->alpha_beta_guess_end) {
/* MR14 */      return NULL;
/* MR14 */    }

	if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
		 p->jtype==aPlusBlk || p->jtype==aSubBlk || p->jtype==aOptBlk )
	{
		if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) {