acts.c

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

/*@A (C) 1992 Allen I. Holub                                                */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <tools/debug.h>
#include <tools/set.h>
#include <tools/hash.h>
#include <tools/compiler.h>
#include <tools/l.h>

#include <tools/stack.h>	/* stack-manipulation macros	*/
#undef  stack_cls		/* Make all stacks static 	*/
#define stack_cls static

#include "parser.h"
#include "llout.h"

/*  ACTS.C	Action routines used by both llama and occs. These build
 *		up the symbol table from the input specification.
 */

void	find_problems	P(( SYMBOL *sym 			)); /* local */
int	c_identifier	P(( char *name				));

/* Prototypes for public functions are in parser.h */
/*----------------------------------------------------------------------*/
extern int	yylineno;		/* Input line number--created by LeX. */

PRIVATE char	Field_name[NAME_MAX];	/* Field name specified in <name>.    */
PRIVATE int	Goal_symbol_is_next =0; /* If true, the next nonterminal is   */
					/* the goal symbol.		      */
#ifdef OCCS
PRIVATE int 	Associativity;		/* Current associativity direction.   */
PRIVATE int     Prec_lev = 0;		/* Precedence level. Incremented      */
					/* after finding %left, etc.,	      */
					/* but before the names are done.     */
PRIVATE int	Fields_active = 0;	/* Fields are used in the input.      */
					/* (If they're not, then automatic    */
					/* field-name generation, as per      */
#endif					/* %union, is not activated.)         */

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 * The following stuff (that's a technical term) is used for processing nested
 * optional (or repeating) productions defined with the occs [] and []*
 * operators. A stack is kept and, every time you go down another layer of
 * nesting, the current nonterminal is stacked and an new nonterminal is
 * allocated. The previous state is restored when you're done with a level.
 */

#define SSIZE	8		/* Max. optional-production nesting level */
typedef struct _cur_sym_
{
    char	lhs_name[NAME_MAX]; /* Name associated with left-hand side. */
    SYMBOL	*lhs;		    /* Pointer to symbol-table entry for    */
				    /* 		the current left-hand side. */
    PRODUCTION	*rhs;		    /* Pointer to current production.	    */

} CUR_SYM;


CUR_SYM	Stack[ SSIZE ], 	 /* Stack and 				    */
        *Sp = Stack + (SSIZE-1); /* stack pointer. It's inconvenient to use */
				 /* stack.h because stack is of structures. */
/*======================================================================
 * Support routines for actions
 */
#ifdef __TURBOC__
#pragma argsused
#endif

PUBLIC	void print_tok( stream, format, arg )
FILE	*stream;
char	*format;		/* not used here but supplied by pset() */
int	arg;
{
    /* Print one nonterminal symbol to the specified stream.  */

    if     ( arg == -1      ) fprintf(stream, "null "			);
    else if( arg == -2      ) fprintf(stream, "empty "			);
    else if( arg == _EOI_   ) fprintf(stream, "$ "			);
    else if( arg == EPSILON ) fprintf(stream, "<epsilon> "		);
    else	              fprintf(stream, "%s ", Terms[arg]->name	);
}

/*----------------------------------------------------------------------
 * The following three routines print the symbol table. Pterm(), pact(), and
 * pnonterm() are all called indirectly through ptab(), called in
 * print_symbols(). They print the terminal, action, and nonterminal symbols
 * from the symbol table, respectively.
 */

PUBLIC	void pterm( sym, stream )
SYMBOL  *sym;
FILE	*stream;
{
    OX( int i; )
    if( !ISTERM(sym) )
	return;

#   ifdef LLAMA
	fprintf( stream, "%-16.16s  %3d\n", sym->name, sym->val );
#   else
	fprintf( stream, "%-16.16s  %3d    %2d     %c     <%s>\n",
				sym->name,
				sym->val,
				Precedence[sym->val].level ,
				(i = Precedence[sym->val].assoc) ? i : '-',
				sym->field );
#   endif
}
/*----------------------------------------------------------------------*/
PUBLIC	void pact( sym, stream )
SYMBOL  *sym;
FILE	*stream;
{
    if( !ISACT(sym) )
	    return;

    fprintf( stream, "%-5s %3d,",    sym->name, sym->val );
    fprintf( stream, " line %-3d: ", sym->lineno    );
    fputstr( sym->string, 55, stream );
    fprintf( stream, "\n");
}
/*----------------------------------------------------------------------*/
PUBLIC  char *production_str( prod )
PRODUCTION   *prod;
{
    /* return a string representing the production */

    int    	i, nchars, avail;
    static char buf[80];
    char	*p;

    ANSI( nchars = sprintf(buf,"%s ->", prod->lhs->name ); )
    KnR ( 	   sprintf(buf,"%s ->", prod->lhs->name ); )
    KnR ( nchars = strlen (buf			        ); )

    p      = buf + nchars;
    avail  = sizeof(buf) - nchars - 1;

    if( !prod->rhs_len )
	sprintf(p, " (epsilon)" );
    else
	for( i = 0; i < prod->rhs_len && avail > 0 ; ++i )
	{
	    ANSI( nchars = sprintf(p, " %0.*s", avail-2, prod->rhs[i]->name ); )
	    KnR ( 	   sprintf(p, " %0.*s", avail-2, prod->rhs[i]->name ); )
	    KnR ( nchars = strlen (p					    ); )
	    avail -= nchars;
	    p     += nchars;
	}

    return buf;
}
/*----------------------------------------------------------------------*/
PUBLIC	void pnonterm( sym, stream )
SYMBOL  *sym;
FILE	*stream;
{
    PRODUCTION	*p;
    int    	chars_printed;

    stack_dcl( pstack, PRODUCTION *, MAXPROD );

    if( !ISNONTERM(sym) )
	    return;

    fprintf( stream, "%s (%3d)  %s", sym->name, sym->val,
				sym == Goal_symbol ? "(goal symbol)" : "" );

    OX( fprintf( stream, " <%s>\n", sym->field );	)
    LL( fprintf( stream, "\n" );			)

    if( Symbols > 1 )
    {
	/* Print first and follow sets only if you want really verbose output.*/

	fprintf( stream, "   FIRST : " );
	pset( sym->first, (pset_t)print_tok, stream );

	LL(   fprintf(stream, "\n   FOLLOW: ");		)
	LL(   pset( sym->follow, (pset_t)print_tok, stream );	)

	fprintf(stream, "\n");
    }

    /* Productions are put into the SYMBOL in reverse order because it's easier
     * to tack them on to the beginning of the linked list. It's better to print
     * them in forward order, however, to make the symbol table more readable.
     * Solve this problem by stacking all the productions and then popping
     * elements to print them. Since the pstack has MAXPROD elements, it's not
     * necessary to test for stack overflow on a push.
     */

    for( p = sym->productions ; p ; p = p->next )
	push( pstack, p );

    while( !stack_empty( pstack ) )
    {
	p = pop(pstack);
	chars_printed = fprintf(stream, "   %3d: %s",
						p->num, production_str( p ));

	LL(  for( ; chars_printed <= 45; ++chars_printed )	)
	LL(      putc( '.', stream );				)
	LL(  fprintf(stream, "SELECT: ");			)
	LL(  pset( p->select, (pset_t) print_tok, stream );	)

	OX( if( p->prec )					)
	OX( {							)
	OX(     for( ; chars_printed <= 60; ++chars_printed )	)
	OX(          putc( '.', stream );			)
	OX(	if( p->prec )					)
	OX(         fprintf(stream, "PREC %d", p->prec );	)
	OX( }							)

	putc('\n', stream);
    }

    fprintf(stream, "\n");
}
/*----------------------------------------------------------------------*/
PUBLIC	void print_symbols( stream )
FILE	*stream;
{
    /* Print out the symbol table. Nonterminal symbols come first for the sake
     * of the 's' option in yydebug(); symbols other than production numbers can
     * be entered symbolically. ptab returns 0 if it can't print the symbols
     * sorted (because there's no memory. If this is the case, try again but
     * print the table unsorted).
     */

    putc( '\n', stream );

    D( printf("stream        = _iob[%ld] (0x%x)\n", (long)(stream-_iob),\
    								stream ); )
    D( printf("stream->_ptr  = 0x%x\n", stream->_ptr );			  )
    D( printf("stream->_base = 0x%x\n", stream->_base );		  )
    D( printf("stream->_flag = 0x%x\n", stream->_flag );		  )
    D( printf("stream->_file = 0x%x\n", stream->_file );		  )
    D( printf("stream->_cnt  = %d\n",   stream->_cnt );			  )

    fprintf( stream, "---------------- Symbol table ------------------\n" );
    fprintf( stream, "\nNONTERMINAL SYMBOLS:\n\n" );
    if( ptab( Symtab, (ptab_t)pnonterm, stream, 1 ) == 0 )
    	ptab( Symtab, (ptab_t)pnonterm, stream, 0 );

    fprintf( stream, "\nTERMINAL SYMBOLS:\n\n");
    OX( fprintf( stream, "name             value  prec  assoc   field\n"); )
    LL( fprintf( stream, "name             value\n"); 			   )

    if( ptab( Symtab, (ptab_t)pterm, stream, 1 ) == 0 )
    	ptab( Symtab, (ptab_t)pterm, stream, 0 );

    LL(  fprintf( stream, "\nACTION SYMBOLS:\n\n");			  )
    LL(  if( !ptab( Symtab, (ptab_t)pact, stream, 1 ) )			  )
    LL(       ptab( Symtab, (ptab_t)pact, stream, 0 );			  )
    LL(  fprintf( stream, "----------------------------------------\n" ); )
}
/*----------------------------------------------------------------------
 * Problems() and find_problems work together to find unused symbols and
 * symbols that are used but not defined.
 */

PRIVATE	void find_problems( sym )
SYMBOL  *sym;
{
    if( !sym->used && sym!=Goal_symbol )
	error( WARNING,  "<%s> not used (defined on line %d)\n",
						    sym->name, sym->set );
    if( !sym->set && !ISACT(sym) )
	error( NONFATAL, "<%s> not defined (used on line %d)\n",
						    sym->name, sym->used );
}

PUBLIC	int problems()
{
    /* Find, and print an error message, for all symbols that are used but not
     * defined, and for all symbols that are defined but not used. Return the
     * number of errors after checking.
     */

    ptab( Symtab, (ptab_t)find_problems, NULL, 0 );
    return yynerrs;
}
/*----------------------------------------------------------------------*/
   /* Don't need an explicit hash function because the name is at the
    * top of the structure. Here's what it would look like if you moved
    * the field:
    */
#ifdef NEVER
  PRIVATE int hash_funct( p )
  SYMBOL *p;
  {
      if( !*p->name )
  	lerror( FATAL, "Illegal empty symbol name\n" );

      return hash_add( p->name );
  }
#endif

PUBLIC	void init_acts()
{
    /* Various initializations that can't be done at compile time. Call this
     * routine before starting up the parser. The hash-table size (157) is
     * an arbitrary prime number, roughly the number symbols expected in the
     * table. Note that using hash_pjw knocks about 25% off the execution
     * time with the examples in the book (as compared to hash_add.)
     */

    static SYMBOL   bogus_symbol;

    strcpy( bogus_symbol.name, "End of Input" );
    Terms[0] 	 = &bogus_symbol;

    Symtab	 = maketab( 157, hash_pjw, strcmp );
    LL( Synch  	 = newset(); )
}
/*----------------------------------------------------------------------*/
PUBLIC	SYMBOL *make_term( name )		 /* Make a terminal symbol */
char	*name;
{
    SYMBOL	*p;

    if( !c_identifier(name) )
	lerror(NONFATAL, "Token names must be legitimate C identifiers\n");

    else if( p = (SYMBOL *) findsym(Symtab, name) )
	lerror(WARNING, "Terminal symbol <%s> already declared\n", name );
    else
    {
	if( Cur_term >= MAXTERM )
	    lerror(FATAL, "Too many terminal symbols (%d max.).\n", MAXTERM );

	p = (SYMBOL *) newsym( sizeof(SYMBOL) );
	strncpy ( p->name,  name,       NAME_MAX );
	strncpy ( p->field, Field_name, NAME_MAX );
	addsym  ( Symtab, p );

	p->val = ++Cur_term ;
	p->set = yylineno;

	Terms[Cur_term] = p;
    }
    return p;
}
/*----------------------------------------------------------------------*/
PRIVATE c_identifier( name )		/* Return true only if name is  */
char	*name;				/* a legitimate C identifier.	*/
{
    if( isdigit( *name ) )
	return 0;

    for(; *name ; ++name )
	if( !( isalnum(*name) || *name == '_' ))
	    return 0;

    return 1;
}
/*----------------------------------------------------------------------*/
PUBLIC void	first_sym()
{
    /*  This routine is called just before the first rule following the
     *  %%. It's used to point out the goal symbol;
     */

    Goal_symbol_is_next = 1;
}
/*----------------------------------------------------------------------*/
PUBLIC  SYMBOL	*new_nonterm( name, is_lhs )
char	*name;
int	is_lhs;
{
    /* Create, and initialize, a new nonterminal. is_lhs is used to
     * differentiate between implicit and explicit declarations. It's 0 if the
     * nonterminal is added because it was found on a right-hand side. It's 1 if
     * the nonterminal is on a left-hand side.
     *
     * Return a pointer to the new symbol or NULL if an attempt is made to use a
     * terminal symbol on a left-hand side.
     */

    SYMBOL	*p;

    if( p = (SYMBOL *) findsym( Symtab, name ) )
    {
	if( !ISNONTERM( p ) )
	{
	    lerror(NONFATAL, "Symbol on left-hand side must be nonterminal\n");
	    p = NULL;
	}