fset.c

本工具提供一个词法分析器和语法分析器的集成开发环境

		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
		free((char *)ftbl);
		return;
	}

    /* here ENDS the special case in which the lookahead sets for alt1 and alt2
       all have degree 1 for k<LL_k (including LL_k=1)
    */

	/* in case tree construction runs out of memory, set info to make good err msg */

	CurAmbigAlt1 = alt1->altnum;
	CurAmbigAlt2 = alt2->altnum;
	CurAmbigbtype = sub;
	CurAmbigfile = alt1->file;
	CurAmbigline = alt1->line;
	
	/* Don't do full LL(n) analysis if (...)? block because the block,
	   by definition, defies LL(n) analysis.
	   If guess (...)? block and ambiguous then don't remove anything from
	   2nd alt to resolve ambig.
	   Want to predict with LL sup 1 ( n ) decision not LL(n) if guess block
	   since it is much cheaper than LL(n).  LL sup 1 ( n ) "covers" the LL(n)
	   lookahead information.

	   Note: LL(n) context cannot be computed for semantic predicates when
	   followed by (..)?.

	   If (..)? then we scream "AAAHHHH!  No LL(n) analysis will help"

       Is 'ambig' always defined if we enter this if?  I hope so
	   because the 'ensure...()' func references it. TJP Nov 1993.
	   */

	if ( first_item_is_guess_block((Junction *)alt1->p1)!=NULL )
	{
		if ( ParseWithPredicates )
		{
            if (alt1->predicate != NULL) predicate_free(alt1->predicate);  /* MR12 */
            if (alt2->predicate != NULL) predicate_free(alt2->predicate);  /* MR12 */
            require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
        	alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1);
            require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
            require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed");
            alt1->predicate=MR_predSimplifyALL(alt1->predicate);

            require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
    		alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1);
            require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
            require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed");
            alt2->predicate=MR_predSimplifyALL(alt2->predicate);

            MR_doPredicatesHelp(1,alt1,alt2,jtype,sub);

			if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
			{
				verify_context(alt1->predicate);
				verify_context(alt2->predicate);
			}
			if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
				ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
			if ( WarningLevel==1 &&
				(alt1->predicate!=NULL||alt2->predicate!=NULL))
			{
				for (i=1; i<=CLL_k; i++) set_free( fset[i] );
				free((char *)fset);
				for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
				free((char *)ftbl);
				return;
			}
		}

		if ( WarningLevel>1 )
		{
			fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
			if ( jtype == aLoopBegin || jtype == aPlusBlk )
				fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
			else
				fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
						alt1->altnum, alt2->altnum, sub);
			dumpAmbigMsg(fset, stderr, 0);
            MR_traceAmbSource(fset,alt1,alt2);
		}

		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
		free((char *)ftbl);
		return;
	}
	
	/* Not resolved with (..)? block.  Do full LL(n) analysis */
	
	/* ambig is the set of k-tuples truly in common between alt 1 and alt 2 */
    /* MR11 VerifyAmbig once used fset destructively */

	ambig = VerifyAmbig(alt1, alt2, ftbl, fset, &t, &u, &numAmbig);

	/* are all things in intersection really ambigs? */

	if (thisOverflow ||  numAmbig < n )                     /* MR9 */
	{
		Tree *v;

		/* remove ambig permutation from 2nd alternative to resolve ambig;
		 * We want to compute the set of artificial tuples, arising from
		 * LL sup 1 (n) compression, that collide with real tuples from the
		 * 2nd alternative.  This is the set of "special case" tuples that
		 * the LL sup 1 (n) decision template maps incorrectly.
		 */

        /* when generating code in genExpr() it does
         *
         *      if ( genExprSets(j->fset) && !genExprTree(j->ftree)) {...
         *
         * Sooooo the j->ftree is the tree of alt2
         *               after removal of conflicts, not alt1 !
         */

		if ( ambig!=NULL )
		{
            /* at the top of ambig is an ALT node */

			for (v=ambig->down; v!=NULL; v=v->right)
			{
				u = trm_perm(u, v);     /* remove v FROM u */
			}
/*			fprintf(stderr, "after rm alt2:"); preorder(u); fprintf(stderr, "\n");*/
		}
		Tfree( t );
		alt1->ftree = tappend(alt1->ftree, u);
		alt1->ftree = tleft_factor(alt1->ftree);
	}

	if ( ambig==NULL )
	{
		for (i=1; i<=CLL_k; i++) set_free( fset[i] );
		free((char *)fset);
		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
		free((char *)ftbl);
		return;
	}

	ambig = tleft_factor(ambig);

/* TJP:
 * At this point, we surely have an LL(k) ambiguity.  Check for predicates
 */
	if ( ParseWithPredicates )
	{
        if (alt1->predicate != NULL) predicate_free(alt1->predicate);  /* MR12 */
        if (alt2->predicate != NULL) predicate_free(alt2->predicate);  /* MR12 */
        require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
    	alt1->predicate = MR_find_predicates_and_supp((Node *)alt1->p1);
        require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
        require (MR_predicate_context_completed(alt1->predicate),"predicate alt 1 not completed");
        alt1->predicate=MR_predSimplifyALL(alt1->predicate);

        require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
		alt2->predicate = MR_find_predicates_and_supp((Node *)alt2->p1);
        require(MR_PredRuleRefStack.count == 0,"PredRuleRef stack not empty");
        require (MR_predicate_context_completed(alt2->predicate),"predicate alt 2 not completed");
        alt2->predicate=MR_predSimplifyALL(alt2->predicate);

        MR_doPredicatesHelp(0,alt1,alt2,jtype,sub);

		if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) )
		{
			verify_context(alt1->predicate);
			verify_context(alt2->predicate);
		}
		if ( HoistPredicateContext && (alt1->predicate!=NULL||alt2->predicate!=NULL) && WarningLevel>1 )
		   ensure_predicates_cover_ambiguous_lookahead_sequences(alt1, alt2, sub, ambig);
		if ( WarningLevel==1 &&
 			(alt1->predicate!=NULL||alt2->predicate!=NULL))
		{

			/* We found at least one pred for at least one of the alts;
			 * If warnings are low, just return.
			 */

			Tfree(ambig);
            for (i=1; i<=CLL_k; i++) set_free( fset[i] );
    	    free((char *)fset);
    		for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
    		free((char *)ftbl);
			return;
		}
		/* else we're gonna give a warning */
	}
/* end TJP addition */

	fprintf(stderr, ErrHdr, FileStr[alt1->file], alt1->line);
	if ( jtype == aLoopBegin || jtype == aPlusBlk )
		fprintf(stderr, " warning: optional/exit path and alt(s) %sambiguous upon", sub);
	else
		fprintf(stderr, " warning: alts %d and %d %sambiguous upon",
					alt1->altnum, alt2->altnum, sub);
	if ( elevel == 3 )
	{
		preorder(ambig->down);      /* <===== k>1 ambiguity message data */
		fprintf(stderr, "\n");
	} else {
        MR_skipped_e3_report=1;
    	dumpAmbigMsg(fset, stderr, 0);
    };

    MR_traceAmbSourceK(ambig,alt1,alt2);     /* <====== k>1 ambiguity aid */

	Tfree(ambig);

    for (i=1; i<=CLL_k; i++) set_free( fset[i] );
	free((char *)fset);
	for (i=1; i<=CLL_k; i++) free( (char *)ftbl[i] );
	free((char *)ftbl);
}

/* Don't analyze alpha block of (alpha)?beta; if (alpha)? then analyze
 * Return the 1st node of the beta block if present else return j.
 */
Junction *
#ifdef __STDC__
analysis_point( Junction *j )
#else
analysis_point( j )
Junction *j;
#endif
{
	Junction *gblock;

    /* MR13b  When there was an action/predicate preceding a guess block
              the guess block became invisible at the analysis_point.

              first_item_is_guess_block accepts any kind of node,
              despite the fact that the formal is a junction.  But
              I don't want to have to change it all over the place
              until I know it works.
    */

	if ( j->ntype != nJunction && j->ntype != nAction) return j;

	gblock = first_item_is_guess_block((Junction *)j);

	if ( gblock!=NULL )
	{
		Junction *past = gblock->end;
		Junction *p;
		require(past!=NULL, "analysis_point: no end block on (...)? block");

		for (p=(Junction *)past->p1; p!=NULL; )
		{
			if ( p->ntype==nAction )
			{
				p=(Junction *)((ActionNode *)p)->next;
				continue;
			}
			if ( p->ntype!=nJunction )
			{
                past->alpha_beta_guess_end=1;           /* MR14 */
				return (Junction *)past->p1;
			}
			if ( p->jtype==EndBlk || p->jtype==EndRule )
			{
				return j;
			}
/* MR6                                									      */
/* MR6	A guess block is of the form "(alpha)? beta" or "(alpha)?".           */
/* MR6  When beta is omitted (second form) this means "(alpha)? alpha".       */
/* MR6  The program does not store another copy of alpha in this case.        */
/* MR6  During analysis when the program needs to know what follows the       */
/* MR6    guess clause.  It calls this routine.                               */
/* MR6                                                                        */
/* MR6      If it is of the form "(alpha)? beta" it returns a pointer to beta.*/
/* MR6                                                                        */
/* MR6      If it is of the form "(alpha)?" it returns a pointer to the guess */
/* MR6        block itself thereby reusing the junction tree.                 */
/* MR6                                                                        */
/* MR6  It works by searching the "next in sequence" chain (skipping actions) */
/* MR6    searching for a RuleRef or Token node.  (Those are the only 4 kinds */
/* MR6    of nodes: Junctions, RuleRef, Token, and Action.)                   */
/* MR6                                                                        */
/* MR6  This won't work for the special case "(alpha)? ()" because it has no  */
/* MR6    rule references or token nodes.  It eventually encounters a         */
/* MR6	  junction of type EndBlk or EndRule and says to its caller: nothing  */
/* MR6    more here to analyze - must be of the form "(alpha)?".              */
/* MR6                                                                        */
/* MR6  In the case of "(alpha)? ()" it should return a pointer to "()"       */
/* MR6                                                                        */
/* MR6  I think.                                                              */
/* MR6                                                                        */
			if ( p->jtype!=Generic) {		                           /* MR6 */
                past->alpha_beta_guess_end=1;                          /* MR14 */
				return (Junction *)past->p1;                           /* MR6 */
			};					                                       /* MR6 */
   			p=(Junction *)p->p1;
		}
	}
	return j;
}

set
#ifdef __STDC__
First( Junction *j, int k, int jtype, int *max_k )
#else
First( j, k, jtype, max_k )
Junction *j;
int k;
int jtype;
int *max_k;
#endif
{
	Junction *alt1, *alt2;
	set a, rk, fCurBlk;
	int savek;
	int p1, p2;

    int     save_maintainBackTrace;

	require(j->ntype==nJunction, "First: non junction passed");

	/* C o m p u t e  F I R S T  s e t  w i t h  k  l o o k a h e a d */
	fCurBlk = rk = empty;
	for (alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2 )
	{
		Junction *p = analysis_point((Junction *)alt1->p1);
		REACH(p, k, &rk, alt1->fset[k]);
		require(set_nil(rk), "rk != nil");
		set_free(rk);
		set_orin(&fCurBlk, alt1->fset[k]);
	}

	/* D e t e c t  A m b i g u i t i e s */
	*max_k = 1;
	for (p1=1,alt1=j; alt1!=NULL; alt1 = (Junction *)alt1->p2, p1++)
	{
		for (p2=1,alt2=(Junction *)alt1->p2; alt2!=NULL; alt2 = (Junction *)alt2->p2, p2++)
		{
			savek = k;
			a = set_and(alt1->fset[k], alt2->fset[k]);
			while ( !set_nil(a) )
			{
				/* if we have hit the max k requested, just give warning */
				if ( j->approx==k ) {
				}

				if ( k==CLL_k )
				{
#ifdef NOT_USED
***					int save_LL_k = LL_k;
***					int save_CLL_k = CLL_k;
***					/* Get new LL_k from interactive feature if enabled */
***					if ( AImode )
***						AmbiguityDialog(j, jtype, alt1, alt2, &CLL_k, &LL_k);
#endif
					*max_k = CLL_k;
                    save_maintainBackTrace=MR_MaintainBackTrace;
                    if (AlphaBetaTrace) MR_MaintainBackTrace=0;
					HandleAmbiguity(j, alt1, alt2, jtype);
                    MR_MaintainBackTrace=save_maintainBackTrace;
					break;
				}
				else
				{
					Junction *p = analysis_point((Junction *)alt1->p1);
					Junction *q = analysis_point((Junction *)alt2->p1);
					k++;	/* attempt ambig alts again with more lookahead */

					REACH(p, k, &rk, alt1->fset[k]);
					require(set_nil(rk), "rk != nil");
					REACH(q, k, &rk, alt2->fset[k]);
					require(set_nil(rk), "rk != nil");
					set_free(a);
					a = set_and(alt1->fset[k], alt2->fset[k]);
					if ( k > *max_k ) *max_k = k;
				}
			}
			set_free(a);
			k = savek;
		}
	}

	return fCurBlk;
}