yystate.c

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

    return root->state ;
}

#ifdef DEBUG
  prnt_unfin( root )
  TNODE	*root;
  {
      if( !root )
  	return;

      prnt_unfin( root->left  );

      printf("Node %p, left=%p, right=%p, state=%p, state->num=%d\n",
  	    root, root->left, root->right, root->state, root->state->num );

      prnt_unfin( root->right );

  }
#endif


PRIVATE int	state_cmp( new, tab_node )
STATE	*new ;				/*  Pointer to new node (ignored */
					/*  if Sort_by_number is false). */
STATE	*tab_node;			/*  Pointer to existing node	 */
{
    /* Compare two states as described in the text. Return a number representing
     * the relative weight of the states, or 0 of the states are equivalent.
     */
    ITEM  **tab_item ; /* Array of items for existing state	*/
    ITEM  **item     ; /* Array of items for new state		*/
    int	  nitem      ; /* Size of "				*/
    int	  cmp 	     ;

    if( Sort_by_number )
	return( new->num - tab_node->num );

    if( cmp = State_nitems - tab_node->nkitems )	/* state with largest */
	return cmp;					/* number of items is */
							/* larger.	      */
    nitem    = State_nitems ;
    item     = State_items  ;
    tab_item = tab_node->kernel_items;

    for(; --nitem >= 0 ; ++tab_item, ++item )
    {
	if( cmp = (*item)->prod_num - (*tab_item)->prod_num )
	    return cmp;

	if( cmp = (*item)->dot_posn - (*tab_item)->dot_posn  )
	    return cmp;
    }
    return 0;					/* States are equivalent */
}

#ifdef __TURBOC__
#pragma argsused
#endif

PRIVATE unsigned state_hash( sym )
STATE	*sym;				/* ignored */
{
    /* Hash function for STATEs. Sum together production numbers and dot
     * positions of the kernel items.
     */
    ITEM     **items  ;	/* Array of items for new state		*/
    int	     nitems   ;	/* Size of "				*/
    unsigned total    ;

    items  = State_items  ;
    nitems = State_nitems ;
    total  = 0;

    for(;  --nitems >= 0 ; ++items )
	total += (*items)->prod_num  +  (*items)->dot_posn;
    return total;
}
PRIVATE ITEM	*newitem( production )
PRODUCTION	*production;
{
    ITEM       *item;

    if( Recycled_items )
    {
	item = Recycled_items ;
	Recycled_items = (ITEM *) Recycled_items->prod;
	CLEAR( item->lookaheads );
    }
    else
    {
	if( !(item = (ITEM *) malloc( sizeof(ITEM) )) )
	    error( FATAL, "Insufficient memory for all LR(1) items\n" );

	item->lookaheads = newset() ;
    }

#ifdef DEBUG
      if( !production )
  	  error( FATAL, "Illegal NULL production in newitem\n" );

      printf( "Making new item for %s (at 0x%p)\n", strprod(production), item );

      if( production->rhs[0] && production->rhs_len == 0 )
          error(FATAL, "Illegal epsilon production in newitem\n");
#endif

    ++Nitems;
    item->prod		=  production ;
    item->prod_num	=  production->num ;
    item->dot_posn	=  0;
    item->right_of_dot  =  production->rhs[0] ;
    return item;
}

PRIVATE void	freeitem( item )
ITEM	*item;
{
    --Nitems;
    item->prod = (PRODUCTION *) Recycled_items ;
    Recycled_items = item;
}

PRIVATE void	free_recycled_items()
{
    /* empty the recycling heap, freeing all memory used by items there */

    ITEM *p;

    while( p = Recycled_items )
    {
	Recycled_items = (ITEM *) Recycled_items->prod ;
	free(p);
    }
}

PRIVATE void movedot( item )
ITEM	*item;
{
    /* Moves the dot one position to the right and updates the right_of_dot
     * symbol.
     */

    D( if( item->right_of_dot == NULL )					  )
    D( 	  error(FATAL,"Illegal movedot() call on epsilon production\n");  )

    item->right_of_dot = ( item->prod->rhs )[ ++item->dot_posn ] ;
}

PRIVATE int   item_cmp( item1p,  item2p )
ITEM  **item1p, **item2p ;
{
    /* Return the relative weight of two items, 0 if they're equivalent.  */

    int rval;
    ITEM *item1 = *item1p;
    ITEM *item2 = *item2p;

    if( !(rval = RIGHT_OF_DOT(item1) - RIGHT_OF_DOT(item2)) )
	if( !(rval = item1->prod_num - item2->prod_num ) )
	    return item1->dot_posn - item2->dot_posn ;

    return rval;
}

#ifdef NEVER
    D( printf("Comparing %s\n", stritem( *item1p, 0) );			      )
    D( printf("      and %s\n", stritem( *item2p, 0) );			      )
    D( printf("Symbol to right of dot in item1 = %d\n", RIGHT_OF_DOT(item1)); )
    D( printf("Symbol to right of dot in item2 = %d\n", RIGHT_OF_DOT(item2)); )
    D( printf("item1->prod_num = %d\n", item1->prod_num );		      )
    D( printf("item2->prod_num = %d\n", item2->prod_num );		      )
    D( printf("item1->dot_posn  = %d\n", item1->dot_posn  );		      )
    D( printf("item2->dot_posn  = %d\n", item2->dot_posn  );		      )
    D( printf("Returning %d\n\n",	 rval 		  );		      )
#endif
PUBLIC void	make_parse_tables()
{
    /* Prints an LALR(1) transition matrix for the grammar currently
     * represented in the symbol table.
     */

    ITEM	*item;
    STATE	*state;
    PRODUCTION	*start_prod;
    void	mkstates();
    int		state_cmp();
    FILE	*fp, *old_output;

    /* Make data structures used to produce the table, and create an initial
     * LR(1) item containing the start production and the end-of-input marker
     * as a lookahead symbol.
     */

    States = maketab( 257, state_hash, state_cmp );

    if( !Goal_symbol )
	error(FATAL, "No goal symbol.\n" );

    start_prod = Goal_symbol->productions ;

    if( start_prod->next )
	error(FATAL, "Start symbol must have only one right-hand side.\n" );

    item = newitem( start_prod );	    /* Make item for start production */
    ADD( item->lookaheads, _EOI_ );	    /* FOLLOW(S) = {$} 		      */

    newstate( &item, 1, &state );

    if( lr( state ) )			 /* Add shifts and gotos to the table */
    {
	if( Verbose )
	    printf("Adding reductions:\n");

	reductions();					/* add the reductions */

	if( Verbose )
	    printf("Creating tables:\n" );

	if( !Make_yyoutab )			     /* Tables go in yyout.c */
	{
	    print_tab( Actions, "Yya", "Yy_action", 1);
	    print_tab( Gotos  , "Yyg", "Yy_goto"  , 1);
	}
	else
	{
	    if( !(fp = fopen(TAB_FILE, "w")) )
	    {
		error( NONFATAL, "Can't open %s, ignoring -T\n", TAB_FILE);
		print_tab( Actions, "Yya", "Yy_action", 1);
		print_tab( Gotos  , "Yyg", "Yy_goto"  , 1);
	    }
	    else
	    {
		output ( "extern YY_TTYPE *Yy_action[]; /* in yyoutab.c */\n" );
		output ( "extern YY_TTYPE *Yy_goto[];   /* in yyoutab.c */\n" );

		old_output = Output;
		Output     = fp;

		fprintf(fp, "#include <stdio.h>\n" );
		fprintf(fp, "typedef short YY_TTYPE;\n" );
		fprintf(fp, "#define YYPRIVATE %s\n",
					Public ? "/* empty */" : "static" );

		print_tab( Actions, "Yya", "Yy_action", 0 );
		print_tab( Gotos  , "Yyg", "Yy_goto"  , 0);

		fclose( fp );
		Output = old_output;
	    }
	}
	print_reductions();
    }
}



PRIVATE int lr( cur_state )
STATE  *cur_state;
{
    /* Make LALR(1) state machine. The shifts and gotos are done here, the
     * reductions are done elsewhere. Return the number of states.
     */

    ITEM   **p;
    ITEM   **first_item;
    ITEM   *closure_items[ MAXCLOSE ];
    STATE  *next;		/* Next state.				    */
    int	   isnew;		/* Next state is a new state.		    */
    int	   nclose;		/* Number of items in closure_items.	    */
    int	   nitems;		/* # items with same symbol to right of dot.*/
    int	   val;			/* Value of symbol to right of dot.	    */
    SYMBOL *sym;		/* Actual symbol to right of dot.	    */
    int	   nlr  = 0;		/* Nstates + nlr == number of LR(1) states. */

    add_unfinished( cur_state );

    while( cur_state = get_unfinished() )
    {
	if( Verbose > 1 )
		printf( "Next pass...working on state %d\n", cur_state->num );

	/* closure()  adds normal closure items to closure_items array.
	 * kclose()   adds to that set all items in the kernel that have
	 *            outgoing transitions (ie. whose dots aren't at the far
	 *	      right).
	 * assort()   sorts the closure items by the symbol to the right
	 *	      of the dot. Epsilon transitions will sort to the head of
	 *	      the list, followed by transitions on nonterminals,
	 *	      followed by transitions on terminals.
	 * move_eps() moves the epsilon transitions into the closure kernel set.
	 *            It returns the number of items that it moved.
	 */

	nclose = closure  (cur_state, closure_items, MAXCLOSE 		);
	nclose = kclosure (cur_state, closure_items, MAXCLOSE, nclose	);

	if( nclose == 0 )
	{
	    if( Verbose > 1 )
		printf("There were NO closure items added\n");
	}
	else
	{
	    assort( (void**)closure_items, nclose, sizeof(ITEM*),
					    (int (*)(void*,void*)) item_cmp );
	    nitems  = move_eps( cur_state, closure_items, nclose );
	    p       = closure_items + nitems;
	    nclose -= nitems ;

	    if( Verbose > 1 )
		pclosure( cur_state, p, nclose );
	}

	/* All of the remaining items have at least one symbol to the	*/
	/* right of the dot.						*/

	while( nclose > 0 )  	/* fails immediatly if no closure items */
	{
	    first_item = p ;
	    sym	       = (*first_item)->right_of_dot ;
	    val	       = sym->val ;

	    /* Collect all items with the same symbol to the right of the dot.
	     * On exiting the loop, nitems will hold the number of these items
	     * and p will point at the first nonmatching item. Finally nclose is
	     * decremented by nitems. items = 0 ;
	     */

	    nitems = 0 ;
	    do
	    {
		movedot( *p++ );
		++nitems;

	    } while( --nclose > 0  &&  RIGHT_OF_DOT(*p) == val );

	    /* (1) newstate() gets the next state. It returns NEW if the state
	     *	   didn't exist previously, CLOSED if LR(0) closure has been
	     *     performed on the state, UNCLOSED otherwise.
	     * (2) add a transition from the current state to the next state.
	     * (3) If it's a brand-new state, add it to the unfinished list.
	     * (4) otherwise merge the lookaheads created by the current closure
	     *     operation with the ones already in the state.
	     * (5) If the merge operation added lookaheads to the existing set,
	     *     add it to the unfinished list.
	     */

	    isnew = newstate( first_item, nitems, &next );		/* 1 */

	    if( !cur_state->closed )
	    {
		if( ISTERM( sym ) )					/* 2 */
		    add_action ( cur_state->num, val, next->num );
		else
		    add_goto   ( cur_state->num, val, next->num );
	    }

	    if( isnew == NEW )
		add_unfinished( next );					/* 3 */
	    else
	    {								/* 4 */
		if( merge_lookaheads( next->kernel_items, first_item, nitems))
		{
		    add_unfinished( next );				/* 5 */
		    ++nlr;
		}
		while( --nitems >= 0 )
		    freeitem( *first_item++ );
	    }

	    fprintf( stderr, "\rLR:%-3d LALR:%-3d", Nstates + nlr, Nstates );
	}
	cur_state->closed = 1;
    }

    free_recycled_items();

    if( Verbose )
	fprintf(stderr, " states, %d items, %d shift and goto transitions\n",
					    Nitems, Ntab_entries );
    return Nstates;
}

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

PRIVATE int 	merge_lookaheads( dst_items, src_items, nitems )
ITEM	**src_items;
ITEM	**dst_items;
int	nitems;
{
    /* This routine is called if newstate has determined that a state having the
     * specified items already exists. If this is the case, the item list in the
     * STATE and the current item list will be identical in all respects except
     * lookaheads. This routine merges the lookaheads of the input items
     * (src_items) to the items already in the state (dst_items). 0 is returned
     * if nothing was done (all lookaheads in the new state are already in the
     * existing state), 1 otherwise. It's an internal error if the items don't
     * match.
     */

    int did_something = 0;

    while( --nitems >= 0 )
    {
	if( 	(*dst_items)->prod     != (*src_items)->prod
	    || 	(*dst_items)->dot_posn != (*src_items)->dot_posn )
	{
	    error(FATAL, "INTERNAL [merge_lookaheads], item mismatch\n" );
	}

	if( !subset( (*dst_items)->lookaheads, (*src_items)->lookaheads ) )
	{
	    ++did_something;
	    UNION( (*dst_items)->lookaheads, (*src_items)->lookaheads );
	}

	++dst_items;
	++src_items;
    }

    return did_something;
}

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

PRIVATE int	move_eps( cur_state, closure_items, nclose )
STATE	*cur_state;
ITEM	**closure_items;
int	nclose;
{
    /* Move the epsilon items from the closure_items set to the kernel of the
     * current state. If epsilon items already exist in the current state,
     * just merge the lookaheads. Note that, because the closure items were
     * sorted to partition them, the epsilon productions in the closure_items
     * set will be in the same order as those already in the kernel. Return
     * the number of items that were moved.
     */

    ITEM **eps_items, **p ;
    int  nitems, moved ;

    eps_items = cur_state->epsilon_items;
    nitems    = cur_state->neitems ;
    moved     = 0;

    D( {								 )
    D( 	    extern int _psp;						 )
    D( 	    void huge* p;						 )