fset2.c

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

			require(p->lock!=NULL, "rJunc: lock array is NULL");
			if ( p->lock[k] ) return NULL;
			p->lock[k] = TRUE;
		}

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR10 */    };

		TRAV(p->p1, k, rk, tail);

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
/* MR10 */    };

		if ( p->jtype==RuleBlk ) {p->lock[k] = FALSE; return tail;}
		r = tmake(tnode(ALT), tail, NULL);
		for (alt=(Junction *)p->p2; alt!=NULL; alt = (Junction *)alt->p2)
		{
			/* if this is one of the added optional alts for (...)+ then break */
			if ( alt->ignore ) break;

			if ( tail==NULL ) {TRAV(alt->p1, k, rk, tail); r->down = tail;}
			else
			{
/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR10 */    };

				TRAV(alt->p1, k, rk, tail->right);

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
/* MR10 */    };
				if ( tail->right != NULL ) tail = tail->right;
			}
		}
		if ( p->jtype!=aSubBlk && p->jtype!=aOptBlk ) p->lock[k] = FALSE;
#ifdef DBG_TREES
		fprintf(stderr, "blk(%s) returns:",((Junction *)p)->rname); preorder(r); fprintf(stderr, "\n");
#endif
		if ( r->down == NULL ) {_Tfree(r); return NULL;}
		return r;
	}

	if ( p->jtype==EndRule )
	{
		if ( p->halt )						/* don't want FOLLOW here? */
		{
/****		if ( ContextGuardTRAV ) return NULL; ****/
			set_orel( (unsigned) k, rk);	/* indicate this k value needed */ /* MR10 cast */
			t = tnode(EpToken);
			t->v.rk = k;
			return t;
		}
		require(p->lock!=NULL, "rJunc: lock array is NULL");
		if ( p->lock[k] ) return NULL;
		/* if no FOLLOW assume k EOF's */
		if ( p->p1 == NULL ) return eofnode(k);
		p->lock[k] = TRUE;
	}

/* MR14 */	if (p->p1 != NULL && p->guess &&  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 */  }	

	if ( p->p2 == NULL )
	{

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR10 */    };

/* M14 */        if (p->guess_analysis_point != NULL) {
/* M14 */ 		   TRAV(p->guess_analysis_point, k, rk,t);
/* M14 */        } else {
        		   TRAV(p->p1, k, rk,t);
/* M14 */        }

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
/* MR10 */    };

		if ( p->jtype==EndRule ) p->lock[k]=FALSE;
		return t;
	}

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR10 */    };

/* M14 */        if (p->guess_analysis_point != NULL) {
/* M14 */ 		   TRAV(p->guess_analysis_point, k, rk,t);
/* M14 */        } else {
        		   TRAV(p->p1, k, rk,t);
/* M14 */        }

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (p->jtype != Generic) MR_pointerStackPop(&MR_BackTraceStack);
/* MR10 */    };

	if ( p->jtype!=RuleBlk && /* MR14 */ !p->guess) TRAV(p->p2, k, rk, u);

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

	if ( t==NULL ) return tmake(tnode(ALT), u, NULL);
	return tmake(tnode(ALT), t, u, NULL);
}

Tree *
#ifdef __USE_PROTOS
tRuleRef( RuleRefNode *p, int k, set *rk_out )
#else
tRuleRef( p, k, rk_out )
RuleRefNode *p;
int k;
set *rk_out;
#endif
{
	int k2;
	Tree *t=NULL, *u=NULL;
	Junction *r;
	set rk, rk2;
	int save_halt;
	RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
	
#ifdef DBG_TRAV
	fprintf(stderr, "tRuleRef: %s\n", p->text);
#endif
	if ( q == NULL )
	{
		TRAV(p->next, k, rk_out, t);/* ignore undefined rules */
		return t;
	}
	rk = rk2 = empty;
    if (RulePtr == NULL) fatal("RulePtr==NULL");
	r = RulePtr[q->rulenum];
	if ( r->lock[k] ) return NULL;
	save_halt = r->end->halt;
	r->end->halt = TRUE;		/* don't let reach fall off end of rule here */

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR10 */    };

	TRAV(r, k, &rk, t);

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      MR_pointerStackPop(&MR_BackTraceStack);
/* MR10 */    };

	r->end->halt = save_halt;
#ifdef DBG_TREES
	fprintf(stderr, "after ruleref, t is:"); preorder(t); fprintf(stderr, "\n");
#endif
	t = tshrink( t );
	while ( !set_nil(rk) ) {	/* any k left to do? if so, link onto tree */
		k2 = set_int(rk);
		set_rm(k2, rk);

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR10 */    };

		TRAV(p->next, k2, &rk2, u);

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      MR_pointerStackPop(&MR_BackTraceStack);
/* MR10 */    };

		t = tlink(t, u, k2);	/* any alts missing k2 toks, add u onto end */
        Tfree(u);               /* MR10 */
	}
	set_free(rk);				/* rk is empty, but free it's memory */
	set_orin(rk_out, rk2);		/* remember what we couldn't do */
	set_free(rk2);
	return t;
}

Tree *
#ifdef __USE_PROTOS
tToken( TokNode *p, int k, set *rk )
#else
tToken( p, k, rk )
TokNode *p;
int k;
set *rk;
#endif
{
	Tree *t=NULL, *tset=NULL, *u;

	if (ConstrainSearch) {
      if (MR_AmbSourceSearch) {
		require(constrain>=fset&&constrain<=&(fset[CLL_k]),"tToken: constrain is not a valid set");
      } else {
		require(constrain>=fset&&constrain<=&(fset[LL_k]),"tToken: constrain is not a valid set");
      };
      constrain = &fset[maxk-k+1];
	}

#ifdef DBG_TRAV
        	fprintf(stderr, "tToken(%d): %s\n", k, TerminalString(p->token));
        	if ( ConstrainSearch ) {
        		fprintf(stderr, "constrain is:"); s_fprT(stderr, *constrain); fprintf(stderr, "\n");
        	}
#endif

	/* is it a meta token (set of tokens)? */

	if ( !set_nil(p->tset) )
	{
		unsigned e=0;
		set a;
		Tree *n, *tail = NULL;

		if ( ConstrainSearch ) {
          a = set_and(p->tset, *constrain);
          if (set_nil(a)) {         /* MR10 */
            set_free(a);            /* MR11 */
            return NULL;            /* MR10 */
          };                        /* MR10 */
		} else {
          a = set_dup(p->tset);
        };

		for (; !set_nil(a); set_rm(e, a))
		{
			e = set_int(a);
			n = tnode(e);
			if ( tset==NULL ) { tset = n; tail = n; }
			else { tail->right = n; tail = n; }
		}
		set_free( a );
	}
	else if ( ConstrainSearch && !set_el(p->token, *constrain) )
    {
/*      fprintf(stderr, "ignoring token %s(%d)\n", TerminalString(p->token),
                k);*/
        return NULL;
    }
	else {
        tset = tnode( p->token );
    };

/* MR10 */    if (MR_MaintainBackTrace) {
/* MR10 */      if (k == 1) {
/* MR10 */        MR_pointerStackPush(&MR_BackTraceStack,p);
/* MR13 */        if (MR_SuppressSearch) {
/* MR13 */          MR_suppressSearchReport();
/* MR13 */        } else {
/* MR10 */          MR_backTraceReport();
/* MR13 */        };
/* MR10 */        MR_pointerStackPop(&MR_BackTraceStack);
/* MR11 */        Tfree(tset);
/* MR11 */        return NULL;
/* MR10 */      };
/* MR10 */    };

	if ( k == 1 ) return tset;

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

	TRAV(p->next, k-1, rk, t);

    if (MR_MaintainBackTrace) {
      Tfree(t);
      Tfree(tset);
      MR_pointerStackPop(&MR_BackTraceStack);
      return NULL;
    };

	/* here, we are positive that, at least, this tree will not contribute
	 * to the LL(2) tree since it will be too shallow, IF t==NULL.
	 * If doing a context guard walk, then don't prune.
	 */
	if ( t == NULL && !ContextGuardTRAV )	/* tree will be too shallow */
	{
		if ( tset!=NULL ) Tfree( tset );
		return NULL;
	}
#ifdef DBG_TREES
	fprintf(stderr, "tToken(%d)->next:",k); preorder(t); fprintf(stderr, "\n");
#endif

	/* if single token root, then just make new tree and return */
    /* MR10 - set_nil(p->tset) isn't a good test because of ConstraintSearch */

	if (tset->right == NULL) return tmake(tset, t, NULL);    /* MR10 */

	/* here we must make a copy of t as a child of each element of the tset;
	 * e.g., "T1..T3 A" would yield ( nil ( T1 A ) ( T2 A ) ( T3 A ) )
	 */
	for (u=tset; u!=NULL; u=u->right)
	{
		/* make a copy of t and hook it onto bottom of u */
		u->down = tdup(t);
	}
	Tfree( t );
#ifdef DBG_TREES
	fprintf(stderr, "range is:"); preorder(tset); fprintf(stderr, "\n");
#endif
	return tset;
}

Tree *
#ifdef __USE_PROTOS
tAction( ActionNode *p, int k, set *rk )
#else
tAction( p, k, rk )
ActionNode *p;
int k;
set *rk;
#endif
{
	Tree        *t=NULL;
    set         *save_fset=NULL;
    int         i;

	/* fprintf(stderr, "tAction\n"); */

/*  An MR_SuppressSearch is looking for things that can be
      reached even when the predicate is false.

    There are three kinds of predicates:
        plain:              r1: <<p>>? r2
        guarded:            r1: (A)? => <<p>>? r2
        ampersand style:    r1: (A)? && <<p>>? r2

    Of the three kinds of predicates, only a guard predicate
      has things which are reachable even when the predicate
      is false.  To be reachable the constraint must *not*
      match the guard.

*/

    if (p->is_predicate && MR_SuppressSearch) {

      Predicate     *pred=p->guardpred;

      if (pred == NULL) {
        t=NULL;
        goto EXIT;
      };
      constrain = &fset[maxk-k+1];
      if (pred->k == 1) {
        set     dif;
        dif=set_dif(*constrain,pred->scontext[1]);
        if (set_nil(dif)) {
          set_free(dif);
          t=NULL;
          goto EXIT;
        };
        set_free(dif);
      } else {
        if (MR_tree_matches_constraints(k,constrain,pred->tcontext)) {
          t=NULL;
          goto EXIT;
        };
      }
    };

    /* The ampersand predicate differs from the
         other predicates because its first set
         is a subset of the first set behind the predicate

            r1: (A)? && <<p>>? r2 ;
            r2: A | B;

       In this case first[1] of r1 is A, even
         though first[1] of r2 is {A B}.
    */

    if (p->is_predicate && p->ampersandPred != NULL) {

      Predicate     *pred=p->ampersandPred;
      Tree          *tAND;
      Tree          *tset;

      if (k <= pred->k) {
        if (MR_MaintainBackTrace) MR_pointerStackPush(&MR_BackTraceStack,p);
        TRAV(p->guardNodes,k,rk,t);
        if (MR_MaintainBackTrace) MR_pointerStackPop(&MR_BackTraceStack);
        return t;
      } else {
        require (k>1,"tAction for ampersandpred: k <= 1");
        if (ConstrainSearch) {
          if (MR_AmbSourceSearch) {
    		require(constrain>=fset&&constrain<=&(fset[CLL_k]),
                                "tToken: constrain is not a valid set");
          } else {
    		require(constrain>=fset&&constrain<=&(fset[LL_k]),
                                "tToken: constrain is not a valid set");
          };
          save_fset=(set *) calloc (CLL_k+1,sizeof(set));
          require (save_fset != NULL,"tAction save_fset alloc");
          for (i=1; i <= CLL_k ; i++) {
            save_fset[i]=set_dup(fset[i]);
          };
          if (pred->k == 1) {
            constrain = &fset[maxk-k+1];
            set_andin(constrain,pred->scontext[1]);
            if (set_nil(*constrain)) {
              t=NULL;
              goto EXIT;
            };
          } else {
            constrain = &fset[maxk-k+1];
            if (! MR_tree_matches_constraints(pred->k,constrain,pred->tcontext)) {
               t=NULL;
               goto EXIT;
            };  /* end loop on i          */
          }; /* end loop on pred scontext/tcontext */
        }; /* end if on k > pred->k     */
      }; /* end if on constrain search  */

      TRAV(p->next,k,rk,t);

      if (t != NULL) {
        t=tshrink(t);
        t=tflatten(t);
        t=tleft_factor(t);
        if (pred->tcontext != NULL) {
          tAND=MR_computeTreeAND(t,pred->tcontext);
        } else {
          tset=MR_make_tree_from_set(pred->scontext[1]);
          tAND=MR_computeTreeAND(t,tset);
          Tfree(tset);
        };
        Tfree(t);
        t=tAND;
      };
      goto EXIT;

    }; /* end if on ampersand predicate */

    TRAV(p->next,k,rk,t);

EXIT:
    if (save_fset != NULL) {
      for (i=1 ; i <= CLL_k ; i++) {
        set_free(fset[i]);
        fset[i]=save_fset[i];
      };
      free ( (char *) save_fset);
    };
	return t;
}

/* see if e exists in s as a possible input permutation (e is always a chain) */

int
#ifdef __USE_PROTOS
tmember( Tree *e, Tree *s )
#else
tmember( e, s )
Tree *e;
Tree *s;
#endif
{
	if ( e==NULL||s==NULL ) return 0;
/** fprintf(stderr, "tmember(");
***	preorder(e); fprintf(stderr, ",");
***	preorder(s); fprintf(stderr, " )\n");
*/
	if ( s->token == ALT && s->right == NULL ) return tmember(e, s->down);
	if ( e->token!=s->token )
	{
		if ( s->right==NULL ) return 0;
		return tmember(e, s->right);
	}
	if ( e->down==NULL && s->down == NULL ) return 1;
	if ( tmember(e->down, s->down) ) return 1;
	if ( s->right==NULL ) return 0;
	return tmember(e, s->right);
}

/* see if e exists in s as a possible input permutation (e is always a chain);
 * Only check s to the depth of e.  In other words, 'e' can be a shorter
 * sequence than s.
 */
int
#ifdef __USE_PROTOS
tmember_constrained( Tree *e, Tree *s)
#else
tmember_constrained( e, s )
Tree *e;
Tree *s;
#endif
{
	if ( e==NULL||s==NULL ) return 0;
/**	fprintf(stderr, "tmember_constrained(");
***	preorder(e); fprintf(stderr, ",");
***	preorder(s); fprintf(stderr, " )\n");
**/
	if ( s->token == ALT && s->right == NULL )
		return tmember_constrained(e, s->down);
	if ( e->token!=s->token )
	{
		if ( s->right==NULL ) return 0;
		return tmember_constrained(e, s->right);
	}
	if ( e->down == NULL ) return 1; /* if s is matched to depth of e return */
	if ( tmember_constrained(e->down, s->down) ) return 1;
	if ( s->right==NULL ) return 0;
	return tmember_constrained(e, s->right);
}

/* combine (? (A t) ... (A u) ...) into (? (A t u)) */
Tree *
#ifdef __USE_PROTOS
tleft_factor( Tree *t )
#else
tleft_factor( t )
Tree *t;
#endif
{
	Tree *u, *v, *trail, *w;

	/* left-factor what is at this level */
	if ( t == NULL ) return NULL;
	for (u=t; u!=NULL; u=u->right)
	{
		trail = u;
		v=u->right;
		while ( v!=NULL )
		{
			if ( u->token == v->token )
			{
				if ( u->down!=NULL )
				{
					for (w=u->down; w->right!=NULL; w=w->right) {;}
					w->right = v->down;	/* link children together */
				}
				else u->down = v->down;
				trail->right = v->right;		/* unlink factored node */
				_Tfree( v );
				v = trail->right;
			}
			else {trail = v; v=v->right;}
		}
	}
	/* left-factor what is below */
	for (u=t; u!=NULL; u=u->right) u->down = tleft_factor( u->down );
	return t;
}

/* remove the permutation p from t if present */
Tree *
#ifdef __USE_PROTOS
trm_perm( Tree *t, Tree *p )
#else
trm_perm( t, p )
Tree *t;
Tree *p;
#endif
{