fset.c

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

/*
 * fset.c
 *
 * Compute FIRST and FOLLOW sets.
 *
 * 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 <stdlib.h>

#include "pcctscfg.h"

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

#ifdef __USE_PROTOS
static void ensure_predicates_cover_ambiguous_lookahead_sequences
                                    (Junction *, Junction *, char *, Tree *);
#else
static void ensure_predicates_cover_ambiguous_lookahead_sequences();
#endif

/*
 * What tokens are k tokens away from junction q?
 *
 * Follow both p1 and p2 paths (unless RuleBlk) to collect the tokens k away from this
 * node.
 * We lock the junction according to k--the lookahead.  If we have been at this
 * junction before looking for the same, k, number of lookahead tokens, we will
 * do it again and again...until we blow up the stack.  Locks are only used on aLoopBlk,
 * RuleBlk, aPlusBlk and EndRule junctions to remove/detect infinite recursion from
 * FIRST and FOLLOW calcs.
 *
 * If p->jtype == EndRule we are going to attempt a FOLLOW.  (FOLLOWs are really defined
 * in terms of FIRST's, however).  To proceed with the FOLLOW, p->halt cannot be
 * set.  p->halt is set to indicate that a reference to the current rule is in progress
 * and the FOLLOW is not desirable.
 *
 * If we attempt a FOLLOW and find that there is no FOLLOW or REACHing beyond the EndRule
 * junction yields an empty set, replace the empty set with EOF.  No FOLLOW means that
 * only EOF can follow the current rule.  This normally occurs only on the start symbol
 * since all other rules are referenced by another rule somewhere.
 *
 * Normally, both p1 and p2 are followed.  However, checking p2 on a RuleBlk node is
 * the same as checking the next rule which is clearly incorrect.
 *
 * Cycles in the FOLLOW sense are possible.  e.g. Fo(c) requires Fo(b) which requires
 * Fo(c).  Both Fo(b) and Fo(c) are defined to be Fo(b) union Fo(c).  Let's say
 * Fo(c) is attempted first.  It finds all of the FOLLOW symbols and then attempts
 * to do Fo(b) which finds of its FOLLOW symbols.  So, we have:
 *
 *                  Fo(c)
 *                 /     \
 *              a set    Fo(b)
 *                      /     \
 *                   a set    Fo(c) .....Hmmmm..... Infinite recursion!
 *
 * The 2nd Fo(c) is not attempted and Fo(b) is left deficient, but Fo(c) is now
 * correctly Fo(c) union Fo(b).  We wish to pick up where we left off, so the fact
 * that Fo(b) terminated early means that we lack Fo(c) in the Fo(b) set already
 * laying around.  SOOOOoooo, we track FOLLOW cycles.  All FOLLOW computations are
 * cached in a hash table.  After the sequence of FOLLOWs finish, we reconcile all
 * cycles --> correct all Fo(rule) sets in the cache.
 *
 * Confused? Good! Read my MS thesis [Purdue Technical Report TR90-30].
 * TJP 8/93 -- can now read PhD thesis from Purdue.
 *
 * Also, FIRST sets are cached in the hash table.  Keys are (rulename,Fi/Fo,k).
 * Only FIRST sets, for which the FOLLOW is not included, are stored.
 *
 * SPECIAL CASE of (...)+ blocks:
 * I added an optional alt so that the alts could see what
 * was behind the (...)+ block--thus using enough lookahead
 * to branch out rather than just enough to distinguish
 * between alts in the (...)+.  However, when the FIRST("(...)+") is
 * is needed, must not use this last "optional" alt.  This routine
 * turns off this path by setting a new 'ignore' flag for
 * the alt and then resetting it afterwards.
 */

set
#ifdef __USE_PROTOS
rJunc( Junction *p, int k, set *rk )
#else
rJunc( p, k, rk )
Junction *p;
int k;
set *rk;
#endif
{
	set     a, b;

	require(p!=NULL,				"rJunc: NULL node");
	require(p->ntype==nJunction,	"rJunc: not junction");

#ifdef DBG_LL1
	if ( p->jtype == RuleBlk ) fprintf(stderr, "FIRST(%s,%d) \n",((Junction *)p)->rname,k);
	else fprintf(stderr, "rJunc: %s in rule %s\n",
			decodeJType[p->jtype], ((Junction *)p)->rname);
#endif
	/* if this is one of the added optional alts for (...)+ then return */

    /* no need to pop backtrace - hasn't been pushed */

	if ( p->ignore ) return empty;

    if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);

/* 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 */      if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
/* MR14 */      return empty;
/* MR14 */    }

	/* locks are valid for aLoopBlk,aPlusBlk,RuleBlk,EndRule junctions only */
	if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
		 p->jtype==aPlusBlk || p->jtype==EndRule )
	{
		require(p->lock!=NULL, "rJunc: lock array is NULL");
		if ( p->lock[k] )
		{
			if ( p->jtype == EndRule )	/* FOLLOW cycle? */
			{
#ifdef DBG_LL1
				fprintf(stderr, "FOLLOW cycle to %s: panic!\n", p->rname);
#endif
                if (! MR_AmbSourceSearch) RegisterCycle(p->rname, k);
			}
            if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
			return empty;
		}
		if ( p->jtype == RuleBlk &&
                 p->end->halt  &&
                     ! MR_AmbSourceSearch)	/* check for FIRST cache */
		{
			CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'i',k));
			if ( q != NULL )
			{
				set_orin(rk, q->rk);
                if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
   				return set_dup( q->fset );
			}
		}
		if ( p->jtype == EndRule &&
                !p->halt &&                     /* MR11 was using cache even when halt set */
                     ! MR_AmbSourceSearch)		/* FOLLOW set cached already? */
		{
			CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
			if ( q != NULL )
			{
#ifdef DBG_LL1
				fprintf(stderr, "cache for FOLLOW(%s,%d):", p->rname,k);
				s_fprT(stderr, q->fset);
				if ( q->incomplete ) fprintf(stderr, " (incomplete)");
				fprintf(stderr, "\n");
#endif
				if ( !q->incomplete )
				{
                    if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
					return set_dup( q->fset );
				}
			}
		}
		p->lock[k] = TRUE;	/* This rule is busy */
	}

	a = b = empty;

	if ( p->jtype == EndRule )
	{
		if (p->halt )			/* don't want FOLLOW here? */ /* unless MR10 hoisting */
		{
 	  	      p->lock[k] = FALSE;
			  set_orel(k, rk);						/* indicate this k value needed */
              if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
			  return empty;
		}
		if (! MR_AmbSourceSearch) FoPush(p->rname, k);		/* Attempting FOLLOW */
		if ( p->p1 == NULL ) set_orel((TokenInd!=NULL?TokenInd[EofToken]:EofToken), &a);/* if no FOLLOW assume EOF */
#ifdef DBG_LL1
		fprintf(stderr, "-->FOLLOW(%s,%d)\n", p->rname,k);
#endif
	}

	if ( p->p1 != NULL ) {
/* MR14 */      if (p->guess) {
/* MR14 */        if (p->guess_analysis_point == NULL) {
/* MR14 */           Node * guess_point;
/* MR14 */           guess_point=(Node *)analysis_point(p);
/* MR14 */           if (guess_point == (Node *)p) {
/* MR14 */             guess_point=p->p1;
/* MR14 */           }
/* MR14 */           p->guess_analysis_point=guess_point;
/* MR14 */        }
/* MR14 */        REACH(p->guess_analysis_point, k, rk, a);
                } else {
                  REACH(p->p1, k, rk, a);
                }
    }	

	/* C a c h e  R e s u l t s */

	if ( p->jtype == RuleBlk && p->end->halt && ! MR_AmbSourceSearch)		/* can save FIRST set? */
	{
		CacheEntry *q = newCacheEntry( Fkey(p->rname,'i',k) );
		/*fprintf(stderr, "Caching %s FIRST %d\n", p->rname, k);*/
		hash_add(Fcache, Fkey(p->rname,'i',k), (Entry *)q);
		q->fset = set_dup( a );
		q->rk = set_dup( *rk );
	}

	if ( p->jtype == EndRule &&
            !p->halt &&                         /* MR11 was using cache even with halt set */
                 ! MR_AmbSourceSearch)			/* just completed FOLLOW? */
	{
		/* Cache Follow set */
		CacheEntry *q = (CacheEntry *) hash_get(Fcache, Fkey(p->rname,'o',k));
		if ( q==NULL )
		{
			q = newCacheEntry( Fkey(p->rname,'o',k) );
			hash_add(Fcache, Fkey(p->rname,'o',k), (Entry *)q);
		}
		/*fprintf(stderr, "Caching %s FOLLOW %d\n", p->rname, k);*/
		if ( set_nil(a) && !q->incomplete )
		{
			/* Don't ever save a nil set as complete.
			 * Turn it into an eof set.
			 */
			set_orel(EofToken, &a);
		}
		set_orin(&(q->fset), a);
		FoPop( k );
		if ( FoTOS[k] == NULL && Cycles[k] != NULL ) ResolveFoCycles(k);
#ifdef DBG_LL1
		fprintf(stderr, "saving FOLLOW(%s,%d):", p->rname, k);
		s_fprT(stderr, q->fset);
		if ( q->incomplete ) fprintf(stderr, " (incomplete)");
		fprintf(stderr, "\n");
#endif
	}
	
    if (p->jtype != RuleBlk && p->p2 != NULL && /* MR14 */ ! p->guess) {
       REACH(p->p2, k, rk, b);
    }	

	if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
		 p->jtype==aPlusBlk || p->jtype==EndRule )
		p->lock[k] = FALSE;							/* unlock node */

	set_orin(&a, b);
	set_free(b);
    if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
	return a;
}

set
#ifdef __USE_PROTOS
rRuleRef( RuleRefNode *p, int k, set *rk_out )
#else
rRuleRef( p, k, rk_out )
RuleRefNode *p;
int k;
set *rk_out;
#endif
{
	set rk;
	Junction *r;
	int k2;
	set a, rk2, b;
	int save_halt;
	RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
	require(p!=NULL,			"rRuleRef: NULL node");
	require(p->ntype==nRuleRef,	"rRuleRef: not rule ref");

#ifdef DBG_LL1
	fprintf(stderr, "rRuleRef: %s\n", p->text);
#endif

    if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);

	if ( q == NULL )
	{
		warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
		REACH(p->next, k, rk_out, a);
        if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
		return a;
	}
	rk2 = empty;

/* MR9 Problems with rule references in guarded predicates */
/* MR9    Perhaps can use hash table to find rule ?        */

/* MR9 */    if (RulePtr == NULL) {
/* MR9 */        fatalFL(eMsg2("Rule %s uses rule %s via RulePtr before it has been initialized",
/* MR9 */                                p->rname,q->str),FileStr[p->file],p->line);
/* MR9 */    };

	r = RulePtr[q->rulenum];
	if ( r->lock[k] )
	{
		errNoFL( eMsg2("infinite left-recursion to rule %s from rule %s",
						r->rname, p->rname) );

        if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);

		return empty;
	}

	save_halt = r->end->halt;
	r->end->halt = TRUE;		/* don't let reach fall off end of rule here */
	rk = empty;
	REACH(r, k, &rk, a);
	r->end->halt = save_halt;
	while ( !set_nil(rk) ) {
		k2 = set_int(rk);               /* MR11 this messes up the ambiguity search routine */
		set_rm(k2, rk);
		REACH(p->next, k2, &rk2, b);    /* MR11 by changing the value of k                  */
		set_orin(&a, b);
		set_free(b);
	}
	set_free(rk);				/* this has no members, but free it's memory */
	set_orin(rk_out, rk2);		/* remember what we couldn't do */
	set_free(rk2);
    if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
	return a;
}

/*
 * Return FIRST sub k ( token_node )
 *
 * TJP 10/11/93 modified this so that token nodes that are actually
 * ranges (T1..T2) work.
 */
set
#ifdef __USE_PROTOS
rToken( TokNode *p, int k, set *rk )
#else
rToken( p, k, rk )
TokNode *p;
int k;
set *rk;
#endif
{
	set a;

	require(p!=NULL,			"rToken: NULL node");
	require(p->ntype==nToken,	"rToken: not token node");

#ifdef DBG_LL1
	fprintf(stderr, "rToken: %s\n", (TokenString(p->token)!=NULL)?TokenString(p->token):
									ExprString(p->token));
#endif