fset2.c

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

	/*
	fprintf(stderr, "trm_perm(");
	preorder(t); fprintf(stderr, ",");
	preorder(p); fprintf(stderr, " )\n");
	*/
	if ( t == NULL || p == NULL ) return NULL;
	if ( t->token == ALT )
	{
		t->down = trm_perm(t->down, p);
		if ( t->down == NULL ) 				/* nothing left below, rm cur node */
		{
			Tree *u = t->right;
			_Tfree( t );
			return trm_perm(u, p);
		}
		t->right = trm_perm(t->right, p);	/* look for more instances of p */
		return t;
	}
	if ( p->token != t->token )				/* not found, try a sibling */
	{
		t->right = trm_perm(t->right, p);
		return t;
	}
	t->down = trm_perm(t->down, p->down);
	if ( t->down == NULL ) 					/* nothing left below, rm cur node */
	{
		Tree *u = t->right;
		_Tfree( t );
		return trm_perm(u, p);
	}
	t->right = trm_perm(t->right, p);		/* look for more instances of p */
	return t;
}

/* add the permutation 'perm' to the LL_k sets in 'fset' */
void
#ifdef __USE_PROTOS
tcvt( set *fset, Tree *perm )
#else
tcvt( fset, perm )
set *fset;
Tree *perm;
#endif
{
	if ( perm==NULL ) return;
	set_orel(perm->token, fset);
	tcvt(fset+1, perm->down);
}

/* for each element of ftbl[k], make it the root of a tree with permute(ftbl[k+1])
 * as a child.
 */
Tree *
#ifdef __USE_PROTOS
permute( int k, int max_k )
#else
permute( k, max_k )
int k, max_k;
#endif
{
	Tree *t, *u;
	
	if ( k>max_k ) return NULL;
	if ( ftbl[k][findex[k]] == nil ) return NULL;
	t = permute(k+1, max_k);
	if ( t==NULL&&k<max_k )		/* no permutation left below for k+1 tokens? */
	{
		findex[k+1] = 0;
		(findex[k])++;			/* try next token at this k */
		return permute(k, max_k);
	}
	
	u = tmake(tnode(ftbl[k][findex[k]]), t, NULL);
	if ( k == max_k ) (findex[k])++;
	return u;
}

/* Compute LL(k) trees for alts alt1 and alt2 of p.
 * function result is tree of ambiguous input permutations
 *
 * ALGORITHM may change to look for something other than LL_k size
 * trees ==> maxk will have to change.
 */
Tree *
#ifdef __USE_PROTOS
VerifyAmbig( Junction *alt1, Junction *alt2, unsigned **ft, set *fs, Tree **t, Tree **u, int *numAmbig )
#else
VerifyAmbig( alt1, alt2, ft, fs, t, u, numAmbig )
Junction *alt1;
Junction *alt2;
unsigned **ft;
set *fs;
Tree **t;
Tree **u;
int *numAmbig;
#endif
{
	set rk;
	Tree *perm, *ambig=NULL;
	Junction *p;
	int k;
    int    tnodes_at_start=TnodesAllocated;
    int    tnodes_at_end;
    int    tnodes_used;
    set    *save_fs;
    int    j;

    save_fs=(set *) calloc(CLL_k+1,sizeof(set));
    require(save_fs != NULL,"save_fs calloc");

    for (j=0; j <= CLL_k ; j++) save_fs[j]=set_dup(fs[j]);

	maxk = LL_k;				/* NOTE: for now, we look for LL_k */
	ftbl = ft;
	fset = fs;
	constrain = &(fset[1]);
	findex = (int *) calloc(LL_k+1, sizeof(int));
	if ( findex == NULL )
	{
		fprintf(stderr, ErrHdr, FileStr[CurAmbigfile], CurAmbigline);
		fprintf(stderr, " out of memory while analyzing alts %d and %d of %s\n",
						CurAmbigAlt1,
						CurAmbigAlt2,
						CurAmbigbtype);
		exit(PCCTS_EXIT_FAILURE);
	}
	for (k=1; k<=LL_k; k++) findex[k] = 0;

	rk = empty;
	ConstrainSearch = 1;	/* consider only tokens in ambig sets */

	p = analysis_point((Junction *)alt1->p1);
	TRAV(p, LL_k, &rk, *t);
	*t = tshrink( *t );
	*t = tflatten( *t );
	*t = tleft_factor( *t );    /* MR10 */
	*t = prune(*t, LL_k);
	*t = tleft_factor( *t );

/***	fprintf(stderr, "after shrink&flatten&prune&left_factor:"); preorder(*t); fprintf(stderr, "\n");*/
	if ( *t == NULL )
	{
/***	fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
		Tfree( *t );	/* kill if impossible to have ambig */
		*t = NULL;
	}

	p = analysis_point((Junction *)alt2->p1);

	TRAV(p, LL_k, &rk, *u);
	*u = tshrink( *u );
	*u = tflatten( *u );
	*t = tleft_factor( *t );    /* MR10 */
	*u = prune(*u, LL_k);
	*u = tleft_factor( *u );
/*	fprintf(stderr, "after shrink&flatten&prune&lfactor:"); preorder(*u); fprintf(stderr, "\n");*/
	if ( *u == NULL )
	{
/*		fprintf(stderr, "TreeIncomplete --> no LL(%d) ambiguity\n", LL_k);*/
		Tfree( *u );
		*u = NULL;
	}

	for (k=1; k<=LL_k; k++) set_clr( fs[k] );

	ambig = tnode(ALT);
	k = 0;
	if ( *t!=NULL && *u!=NULL )
	{
		while ( (perm=permute(1,LL_k))!=NULL )
		{
/*			fprintf(stderr, "chk perm:"); preorder(perm); fprintf(stderr, "\n");*/
			if ( tmember(perm, *t) && tmember(perm, *u) )
			{
/*				fprintf(stderr, "ambig upon"); preorder(perm); fprintf(stderr, "\n");*/

				k++;
				perm->right = ambig->down;
				ambig->down = perm;
				tcvt(&(fs[1]), perm);
			}
			else Tfree( perm );
		}
	}

    for (j=0; j <= CLL_k ; j++) fs[j]=save_fs[j];
    free( (char *) save_fs);

    tnodes_at_end=TnodesAllocated;
    tnodes_used=tnodes_at_end - tnodes_at_start;

    if (TnodesReportThreshold > 0 && tnodes_used > TnodesReportThreshold) {
      fprintf(stdout,"There were %d tuples whose ambiguity could not be resolved by full lookahead\n",k);
      fprintf(stdout,"There were %d tnodes created to resolve ambiguity between:\n\n",tnodes_used);
      fprintf(stdout,"  Choice 1: %s  line %d  file %s\n",
                                 MR_ruleNamePlusOffset( (Node *) alt1),alt1->line,FileStr[alt1->file]);
      fprintf(stdout,"  Choice 2: %s  line %d  file %s\n",
                                 MR_ruleNamePlusOffset( (Node *) alt2),alt2->line,FileStr[alt2->file]);
      for (j=1; j <= CLL_k ; j++) {
        fprintf(stdout,"\n    Intersection of lookahead[%d] sets:\n",j);
        MR_dumpTokenSet(stdout,2,fs[j]);
      };
      fprintf(stdout,"\n");
    };

	*numAmbig = k;
	if ( ambig->down == NULL ) {_Tfree(ambig); ambig = NULL;}
	free( (char *)findex );
/*	fprintf(stderr, "final ambig:"); preorder(ambig); fprintf(stderr, "\n");*/
	return ambig;
}

static Tree *
#ifdef __USE_PROTOS
bottom_of_chain( Tree *t )
#else
bottom_of_chain( t )
Tree *t;
#endif
{
    if ( t==NULL ) return NULL;
    for (; t->down != NULL; t=t->down) {;}
    return t;
}

/*
 * Make a tree from k sets where the degree of the first k-1 sets is 1.
 */
Tree *
#ifdef __USE_PROTOS
make_tree_from_sets( set *fset1, set *fset2 )
#else
make_tree_from_sets( fset1, fset2 )
set *fset1;
set *fset2;
#endif
{
	set inter;
	int i;
	Tree *t=NULL, *n, *u;
	unsigned *p,*q;
	require(LL_k>1, "make_tree_from_sets: LL_k must be > 1");

	/* do the degree 1 sets first */
	for (i=1; i<=LL_k-1; i++)
	{
		inter = set_and(fset1[i], fset2[i]);
		require(set_deg(inter)==1, "invalid set to tree conversion");
		n = tnode(set_int(inter));
		if (t==NULL) t=n; else tmake(t, n, NULL);
		set_free(inter);
	}

	/* now add the chain of tokens at depth k */
	u = bottom_of_chain(t);
	inter = set_and(fset1[LL_k], fset2[LL_k]);
	if ( (q=p=set_pdq(inter)) == NULL ) fatal_internal("Can't alloc space for set_pdq");
	/* first one is linked to bottom, then others are sibling linked */
	n = tnode(*p++);
	u->down = n;
	u = u->down;
	while ( *p != nil )
	{
		n = tnode(*p);
		u->right = n;
		u = u->right;
		p++;
	}
	free((char *)q);

	return t;
}

/* create and return the tree of lookahead k-sequences that are in t, but not
 * in the context of predicates in predicate list p.
 */
Tree *
#ifdef __USE_PROTOS
tdif( Tree *ambig_tuples, Predicate *p, set *fset1, set *fset2 )
#else
tdif( ambig_tuples, p, fset1, fset2 )
Tree *ambig_tuples;
Predicate *p;
set *fset1;
set *fset2;
#endif
{
	unsigned **ft;
	Tree *dif=NULL;
	Tree *perm;
	set b;
	int i,k;

	if ( p == NULL ) return tdup(ambig_tuples);

	ft = (unsigned **) calloc(CLL_k+1, sizeof(unsigned *));
	require(ft!=NULL, "cannot allocate ft");
	for (i=1; i<=CLL_k; i++)
	{
		b = set_and(fset1[i], fset2[i]);
		ft[i] = set_pdq(b);
		set_free(b);
	}
	findex = (int *) calloc(LL_k+1, sizeof(int));
	if ( findex == NULL )
	{
		fatal_internal("out of memory in tdif while checking predicates");
	}
	for (k=1; k<=LL_k; k++) findex[k] = 0;

#ifdef DBG_TRAV
	fprintf(stderr, "tdif_%d[", p->k);
	preorder(ambig_tuples);
	fprintf(stderr, ",");
	preorder(p->tcontext);
	fprintf(stderr, "] =");
#endif

	ftbl = ft;
	while ( (perm=permute(1,p->k))!=NULL )
	{
#ifdef DBG_TRAV
		fprintf(stderr, "test perm:"); preorder(perm); fprintf(stderr, "\n");
#endif
		if ( tmember_constrained(perm, ambig_tuples) &&
			 !tmember_of_context(perm, p) )
		{
#ifdef DBG_TRAV
			fprintf(stderr, "satisfied upon"); preorder(perm); fprintf(stderr, "\n");
#endif
			k++;
			if ( dif==NULL ) dif = perm;
			else
			{
				perm->right = dif;
				dif = perm;
			}
		}
		else Tfree( perm );
	}

#ifdef DBG_TRAV
	preorder(dif);
	fprintf(stderr, "\n");
#endif

	for (i=1; i<=CLL_k; i++) free( (char *)ft[i] );
	free((char *)ft);
	free((char *)findex);

	return dif;
}

/* is lookahead sequence t a member of any context tree for any
 * predicate in p?
 */
static int
#ifdef __USE_PROTOS
tmember_of_context( Tree *t, Predicate *p )
#else
tmember_of_context( t, p )
Tree *t;
Predicate *p;
#endif
{
	for (; p!=NULL; p=p->right)
	{
		if ( p->expr==PRED_AND_LIST || p->expr==PRED_OR_LIST )
			return tmember_of_context(t, p->down);
		if ( tmember_constrained(t, p->tcontext) ) return 1;
		if ( tmember_of_context(t, p->down) ) return 1;
	}
	return 0;
}

int
#ifdef __USE_PROTOS
is_single_tuple( Tree *t )
#else
is_single_tuple( t )
Tree *t;
#endif
{
	if ( t == NULL ) return 0;
	if ( t->right != NULL ) return 0;
	if ( t->down == NULL ) return 1;
	return is_single_tuple(t->down);
}


/* MR10 Check that a context guard contains only allowed things */
/* MR10   (mainly token references).                            */

#ifdef __USE_PROTOS
int contextGuardOK(Node *p,int h,int *hmax)
#else
int contextGuardOK(p,h,hmax)
  Node  *p;
  int   h;
  int   *hmax;
#endif
{
    Junction     *j;
    TokNode      *tn;

    if (p == NULL) return 1;
    if (p->ntype == nToken) {
      h++;
      if (h > *hmax) *hmax=h;
      tn=(TokNode *)p;
      if (tn->el_label != NULL) {
        warnFL(eMsg1("a label (\"%s\") for a context guard element is meaningless",tn->el_label),
                             FileStr[p->file],p->line);
      };
      return contextGuardOK( ( (TokNode *) p)->next,h,hmax);
    } else if (p->ntype == nAction) {
      goto Fail;
    } else if (p->ntype == nRuleRef) {
      goto Fail;
    } else {
      require (p->ntype == nJunction,"Unexpected ntype");
      j=(Junction *) p;
      if (j->jtype != Generic &&
          j->jtype != aSubBlk &&        /* pretty sure this one is allowed */
/****     j->jtype != aOptBlk && ****/  /* pretty sure this one is allowed */ /* MR11 not any more ! */
          j->jtype != EndBlk) {
        errFL("A context guard may not contain an option block: {...} or looping block: (...)* or (...)+",
                  FileStr[p->file],p->line);
        contextGuardOK(j->p1,h,hmax);
        return 0;
      };
      /* do both p1 and p2 so use | rather than ||  */
      return contextGuardOK(j->p2,h,hmax) | contextGuardOK(j->p1,h,hmax);
    };
Fail:
    errFL("A context guard may contain only Token references - guard will be ignored",
                             FileStr[p->file],p->line);
    contextGuardOK( ( (ActionNode *) p)->next,h,hmax);
    return 0;
}

/*
 * Look at a (...)? generalized-predicate context-guard and compute
 * either a lookahead set (k==1) or a lookahead tree for k>1.  The
 * k level is determined by the guard itself rather than the LL_k
 * variable.  For example, ( A B )? is an LL(2) guard and ( ID )?
 * is an LL(1) guard.  For the moment, you can only have a single
 * tuple in the guard.  Physically, the block must look like this
 *   --o-->TOKEN-->o-->o-->TOKEN-->o-- ... -->o-->TOKEN-->o--
 * An error is printed for any other type.
 */
Predicate *
#ifdef __USE_PROTOS
computePredFromContextGuard(Graph blk,int *msgDone)    /* MR10 */
#else
computePredFromContextGuard(blk,msgDone)               /* MR10 */
  Graph     blk;
  int       *msgDone;                                       /* MR10 */
#endif
{
    Junction *junc = (Junction *)blk.left, *p;
    Tree        *t=NULL;
	Predicate   *pred = NULL;
	set         scontext, rk;
    int         ok;
    int         hmax=0;

    require(junc!=NULL && junc->ntype == nJunction, "bad context guard");

/* MR10 Check for anything other than Tokens and generic junctions */

    *msgDone=0;                                             /* MR10 */
    ok=contextGuardOK( (Node *)junc,0,&hmax);               /* MR10 */
    if (! ok) {                                             /* MR10 */
      *msgDone=1;                                           /* MR10 */
      return NULL;                                          /* MR10 */
    };                                                      /* MR10 */
    if (hmax == 0) {
errFL("guard is 0 tokens long",FileStr[junc->file],junc->line);          /* MR11 */
      *msgDone=1;
      return NULL;
    };
    if (hmax > CLL_k) {                                     /* MR10 */
errFL(eMsgd2("guard is %d tokens long - lookahead is limited to max(k,ck)==%d", /* MR10 */
        hmax,CLL_k),                                        /* MR10 */
        FileStr[junc->file],junc->line);                    /* MR10 */
      *msgDone=1;                                           /* MR10 */
      return NULL;                                          /* MR10 */
    };                                                      /* MR10 */

	rk = empty;
	p = junc;
	pred = new_pred();
	pred->k = hmax;     /* MR10 should be CLL_k, not LLK ? */
	if (hmax > 1 )      /* MR10 was LL_k                   */
	{
		ConstrainSearch = 0;
		ContextGuardTRAV = 1;
		TRAV(p, hmax, &rk, t);  /* MR10 was LL_k */
		ContextGuardTRAV = 0;
		set_free(rk);
		t = tshrink( t );
		t = tflatten( t );
		t = tleft_factor( t );
/*
		fprintf(stderr, "ctx guard:");
		preorder(t);
		fprintf(stderr, "\n");
*/
		pred->tcontext = t;
	}
	else
	{
		REACH(p, 1, &rk, scontext);
		require(set_nil(rk), "rk != nil");
		set_free(rk);
/*
		fprintf(stderr, "LL(1) ctx guard is:");
		s_fprT(stderr, scontext);
		fprintf(stderr, "\n");
*/
		pred->scontext[1] = scontext;
	}

    list_add(&ContextGuardPredicateList,pred);     /* MR13 */

	return pred;
}

/* MR13
   When the context guard is originally computed the
   meta-tokens are not known.
*/

#ifdef __USE_PROTOS
void recomputeContextGuard(Predicate *pred)
#else
void recomputeContextGuard(pred)
    Predicate   *pred;
#endif
{
    Tree *          t=NULL;
	set             scontext;
    set             rk;
    ActionNode *    actionNode;
    Junction *      p;

    actionNode=pred->source;
    require (actionNode != NULL,"context predicate's source == NULL");

    p=actionNode->guardNodes;
    require (p != NULL,"context predicate's guardNodes == NULL");

	rk = empty;
	if (pred->k > 1 )
	{
		ConstrainSearch = 0;
		ContextGuardTRAV = 1;
		TRAV(p, pred->k, &rk, t);
		ContextGuardTRAV = 0;
		set_free(rk);
		t = tshrink( t );
		t = tflatten( t );