yystate.c

一个c语言写做的编译器的源码

    D(	    void huge *q = (*closure_items)->prod;		 	 )
    D( 	    SEG(p) = _psp;						 )
    D( 	    OFF(p) = 0 ;						 )

    D( 	    if( PHYS(closure_items) < PHYS(p) || PHYS(q) < PHYS(p))	 )
    D(	 	error(FATAL, "Bad pointer in move_eps\n" );		 )
    D( }								 )

    for( p = closure_items; (*p)->prod->rhs_len == 0 && --nclose >= 0; )
    {
	if( ++moved > MAXEPSILON )
	    error(FATAL, "Too many epsilon productions in state %d\n",
						 cur_state->num );
	if( nitems )
	    UNION( (*eps_items++)->lookaheads, (*p++)->lookaheads );
	else
	    *eps_items++ = *p++ ;

        D( if( !p || !(*p)->prod )				)
      	D(     error(FATAL, "Bad pointer in move_eps\n" );	)

    }

    if( moved )
	cur_state->neitems = moved ;

    return moved ;
}

/*----------------------------------------------------------------------*/

PRIVATE int   kclosure( kernel, closure_items, maxitems, nclose )
STATE *kernel;			/* Kernel state to close.		   */
ITEM  **closure_items;		/* Array into which closure items are put. */
int   maxitems;			/* Size of the closure_items[] array.	   */
int   nclose;			/* # of items already in set.		   */
{
    /* Adds to the closure set those items from the kernel that will shift to
     * new states (ie. the items with dots somewhere other than the far right).
     */

    int 	nitems;
    ITEM	*item, **itemp, *citem ;

    closure_items += nclose;			/* Correct for existing items */
    maxitems      -= nclose;

    itemp  = kernel->kernel_items ;
    nitems = kernel->nkitems ;

    while( --nitems >= 0 )
    {
	item = *itemp++;

	if( item->right_of_dot )
	{
	    citem 		= newitem( item->prod );
    	    citem->prod		= item->prod ;
    	    citem->dot_posn     = item->dot_posn ;
            citem->right_of_dot = item->right_of_dot ;
    	    citem->lookaheads	= dupset( item->lookaheads );

	    if( --maxitems < 0 )
		error( FATAL, "Too many closure items in state %d\n",
								kernel->num );
	    *closure_items++ = citem;
	    ++nclose;
	}
    }
    return nclose;
}

/*----------------------------------------------------------------------*/

PRIVATE int closure( kernel, closure_items, maxitems )
STATE *kernel;			/* Kernel state to close.		  */
ITEM  *closure_items[];		/* Array into which closure items are put */
int   maxitems;			/* Size of the closure_items[] array.	  */
{
    /* Do LR(1) closure on the kernel items array in the input STATE. When
     * finished, closure_items[] will hold the new items. The logic is:
     *
     * (1) for( each kernel item )
     *         do LR(1) closure on that item.
     * (2) while( items were added in the previous step or are added below )
     *         do LR(1) closure on the items that were added.
     */

    int  i ;
    int  nclose 	= 0 ;		/* Number of closure items */
    int  did_something  = 0 ;
    ITEM **p 		= kernel->kernel_items ;

    for( i = kernel->nkitems; --i >= 0 ;)			       /* (1) */
    {
	did_something |= do_close( *p++, closure_items, &nclose, &maxitems );
    }

    while( did_something )					       /* (2) */
    {
	did_something = 0;
	p = closure_items;
	for( i = nclose ; --i >= 0 ; )
	    did_something |= do_close( *p++, closure_items, &nclose, &maxitems);
    }

    return nclose;
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

PRIVATE int   do_close( item, closure_items, nitems, maxitems )
ITEM  *item;
ITEM  *closure_items[];	/* (output) Array of items added by closure process */
int   *nitems;		/* (input)  # of items currently in closure_items[] */
			/* (output) # of items in closure_items after       */
			/*  					 processing */
int   *maxitems;	/* (input)  max # of items that can be added        */
			/* (output) input adjusted for newly added items    */
{
    /* Workhorse function used by closure(). Performs LR(1) closure on the
     * input item ([A->b.Cd, e] add [C->x, FIRST(de)]). The new items are added
     * to the closure_items[] array and *nitems and *maxitems are modified to
     * reflect the number of items in the closure set. Return 1 if do_close()
     * did anything, 0 if no items were added (as will be the case if the dot
     * is at the far right of the production or the symbol to the right of the
     * dot is a terminal).
     */

    int 	did_something = 0;
    int		rhs_is_nullable;
    PRODUCTION	*prod;
    ITEM	*close_item;
    SET		*closure_set;
    SYMBOL	**symp;

    if( !item->right_of_dot )
	return 0;

    if( !ISNONTERM( item->right_of_dot ) )
	return 0;

    closure_set = newset();

    /* The symbol to the right of the dot is a nonterminal. Do the following:
     *
     *(1)  for( every production attached to that nonterminal )
     *(2)	if( the current production is not already in the set of
     *								closure items)
     *(3)            add it;
     *(4)       if( the d in [A->b.Cd, e] doesn't exist )
     *(5)            add e to the lookaheads in the closure production.
     *	        else
     *(6)	    The d in [A->b.Cd, e] does exist, compute FIRST(de) and add
     *		    it to the lookaheads for the current item if necessary.
     */
								       /* (1) */

    for( prod = item->right_of_dot->productions; prod ; prod = prod->next )
    {
								       /* (2) */
	if( !(close_item = in_closure_items(prod, closure_items, *nitems)))
        {
	    if( --(*maxitems) <= 0 )
		error(FATAL, "LR(1) Closure set too large\n" );
								       /* (3) */
	    closure_items[ (*nitems)++ ] = close_item = newitem( prod );
	    ++did_something;
	}

	if( !*(symp = & ( item->prod->rhs [ item->dot_posn + 1 ])) )   /* (4) */
	{
	    did_something |= add_lookahead( close_item->lookaheads,    /* (5) */
							     item->lookaheads );
	}
	else
	{
	    truncate( closure_set );				       /* (6) */

	    rhs_is_nullable = first_rhs( closure_set, symp,
				    item->prod->rhs_len - item->dot_posn - 1 );

	    REMOVE( closure_set, EPSILON );

	    if( rhs_is_nullable )
		UNION( closure_set, item->lookaheads );

	    did_something |= add_lookahead(close_item->lookaheads, closure_set);
	}
    }

    delset( closure_set );
    return did_something;
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

PRIVATE ITEM	  *in_closure_items(production, closure_item, nitems)
PRODUCTION *production;
ITEM	   **closure_item;
int	   nitems;
{
    /* If the indicated production is in the closure_items already, return a
     * pointer to the existing item, otherwise return NULL.
     */

    for(; --nitems >= 0 ; ++closure_item )
	if( (*closure_item)->prod == production )
	    return *closure_item;

    return NULL;
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
PRIVATE int	add_lookahead( dst, src )
SET	*dst, *src;
{
    /* Merge the lookaheads in the src and dst sets. If the original src
     * set was empty, or if it was already a subset of the destination set,
     * return 0, otherwise return 1.
     */

    if( !IS_EMPTY( src ) && !subset( dst, src ) )
    {
	UNION( dst, src );
	return 1;
    }

    return 0;
}
PRIVATE void	reductions()
{
    /* Do the reductions. If there's memory, sort the table by state number */
    /* first so that yyout.doc will look nice.				    */

    void  addreductions();					/* below */

    Sort_by_number = 1;
    if( !ptab( States, (ptab_t)addreductions, NULL, 1 ) )
	ptab( States, (ptab_t)addreductions, NULL, 0 );
}
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#ifdef __TURBOC__
#pragma argsused
#endif

PRIVATE void addreductions( state, junk )
STATE	*state;
void	*junk;
{
    /* This routine is called for each state. It adds the reductions using the
     * disambiguating rules described in the text, and then prints the state to
     * yyout.doc if Verbose is true. I don't like the idea of doing two things
     * at once, but it makes for nicer output because the error messages will
     * be next to the state that caused the error.
     */

    int	  	i;
    ITEM  	**item_p;

     D( printf("----------------------------------\n");	)
     D( pstate_stdout( state );  			)
     D( printf("- - - - - - - - - - - - - - - - -\n");	)

    for( i = state->nkitems, item_p = state->kernel_items;  --i>=0; ++item_p )
	reduce_one_item( state, *item_p );

    for( i = state->neitems, item_p = state->epsilon_items; --i>=0; ++item_p )
	reduce_one_item( state, *item_p );

    if( Verbose )
    {
	pstate( state );

	if( state->num % 10 == 0 )
	    fprintf( stderr, "%d\r", state->num );
    }
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

PRIVATE void	reduce_one_item( state, item )
ITEM	*item;				/* Reduce on this item	*/
STATE	*state;				/* from this state	*/
{
    int		token;	  		/* Current lookahead	        */
    int		pprec;	  		/* Precedence of production	*/
    int		tprec;	  		/* Precedence of token 		*/
    int		assoc;	  		/* Associativity of token	*/
    int		reduce_by;
    int		resolved;		/* True if conflict can be resolved */
    ACT		*ap;

    if( item->right_of_dot )		/* No reduction required */
	    return;

    pprec = item->prod->prec ;		/* precedence of entire production */

    D( printf( "ITEM:  %s\n", stritem(item, 2) ); )

    for( next_member(NULL); (token = next_member(item->lookaheads)) >= 0 ;)
    {
	tprec = Precedence[token].level ;	/* precedence of lookahead */
	assoc = Precedence[token].assoc ;	/* symbol.		   */

  	D( printf( "TOKEN: %s (prec=%d, assoc=%c)\n", Terms[token]->name, \
  							     tprec, assoc ); )

	if( !(ap = p_action( state->num, token )) )	/* No conflicts */
	{
	    add_action( state->num, token, -(item->prod_num) );

  	    D( printf( "Action[%d][%s]=%d\n", state->num, \
  				Terms[token]->name, -(item->prod_num) ); )
	}
	else if( ap->do_this <= 0 )
	{
	    /* Resolve a reduce/reduce conflict in favor of the production */
	    /* with the smaller number. Print a warning.		   */

	    ++Reduce_reduce;

	    reduce_by   = min( -(ap->do_this), item->prod_num );
	    ap->do_this = -reduce_by ;

	    error( WARNING, "State %2d: reduce/reduce conflict ", state->num );
	    error( NOHDR,   "%d/%d on %s (choose %d).\n",
				    -(ap->do_this), item->prod_num ,
				    token ? Terms[token]->name: "<_EOI_>",
				    reduce_by				     );
	}
	else				 /* Shift/reduce conflict. */
	{
	    if( resolved = (pprec && tprec) )
		if( tprec < pprec || (pprec == tprec && assoc != 'r')  )
		    ap->do_this = -( item->prod_num );

	    if( Verbose > 1 || !resolved )
	    {
		++Shift_reduce;
		error( WARNING, "State %2d: shift/reduce conflict", state->num);
		error( NOHDR,	" %s/%d (choose %s) %s\n",
				Terms[token]->name,
				item->prod_num,
				ap->do_this < 0 ? "reduce"     : "shift",
				resolved        ? "(resolved)" : ""
									    );
	    }
	}
    }
}
PUBLIC void lr_stats( fp )
FILE	*fp;
{
    /*  Print out various statistics about the table-making process */

    fprintf(fp, "%4d      LALR(1) states\n",	 	   Nstates );
    fprintf(fp, "%4d      items\n",		 	   Nitems  );
    fprintf(fp, "%4d      nonerror transitions in tables\n", Ntab_entries  );
    fprintf(fp, "%4ld/%-4d unfinished items\n", (long)(Next_allocate - Heap),
							    MAX_UNFINISHED);
    fprintf(fp, "%4d      bytes required for LALR(1) transition matrix\n",
			      (2 * sizeof(char*) * Nstates) /* index arrays */
			      + Nstates			    /* count fields */
			      + (Npairs * sizeof(short))    /* pairs        */
	   );
    fprintf(fp, "\n");
}
/*----------------------------------------------------------------------*/
PUBLIC int lr_conflicts( fp )
FILE	*fp;
{
    /* Print out statistics for the inadequate states and return the number of
     * conflicts.
     */

    fprintf(fp, "%4d      shift/reduce  conflicts\n",  Shift_reduce  );
    fprintf(fp, "%4d      reduce/reduce conflicts\n",  Reduce_reduce );
    return Shift_reduce + Reduce_reduce ;
}

#if ( (0 ANSI(+1)) == 0 )	/* if not an ANSI compiler */
#define sprintf _sprintf
#endif
#ifdef __TURBOC__
#pragma argsused
#endif

PRIVATE void sprint_tok( bp, format, arg )
char	**bp;
char	*format;		/* not used here, but supplied by pset() */
int	arg;
{
    /* Print one nonterminal symbol to a buffer maintained by the
     * calling routine and update the calling routine's pointer.
     */

    if     ( arg == -1     ) *bp += sprintf( *bp, "null "		  );
    else if( arg == -2     ) *bp += sprintf( *bp, "empty "		  );
    else if( arg == _EOI_  ) *bp += sprintf( *bp, "$ "			  );
    else if( arg == EPSILON) *bp += sprintf( *bp, ""			  );
    else	             *bp += sprintf( *bp, "%s ", Terms[arg]->name );

    if( ++Tokens_printed >= MAX_TOK_PER_LINE )
    {
	*bp += sprintf(*bp, "\n\t\t");
	Tokens_printed = 0;
    }
}
/*----------------------------------------------------------------------*/
PRIVATE  char 	*stritem( item, lookaheads )
ITEM	*item;
int	lookaheads;
{
    /* Return a pointer to a string that holds a representation of an item.
     * The lookaheads are printed too if "lookaheads" is true or Verbose
     * is > 1 (-V was specified on the command line).
     */

    static char buf[ MAXOBUF * 4 ];
    char	*bp;
    int	   	i;

    bp  = buf;
    bp += sprintf( bp, "%s->", item->prod->lhs->name );

    if( item->prod->rhs_len <= 0 )
	bp += sprintf( bp, "<epsilon>. " );
    else
    {
	for( i = 0; i < item->prod->rhs_len ; ++i )
	{
	    if( i == item->dot_posn )
		*bp++  = '.' ;

	    bp += sprintf(bp, " %s", item->prod->rhs[i]->name );
	}
	if( i == item->dot_posn )
	    *bp++  = '.' ;
    }

    if( lookaheads || Verbose >1 )
    {
	bp += sprintf( bp, " (production %d, precedence %d)\n\t\t[",
					item->prod->num, item->prod->prec );
	Tokens_printed = 0;
	pset( item->lookaheads, (pset_t)sprint_tok, &bp );
	*bp++ = ']'  ;
    }

    if(  bp >= &buf[sizeof(buf)]   )