gen.c

操作系统源代码

/* gen - actual generation (writing) of flex scanners */

/*-
 * Copyright (c) 1990 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Vern Paxson.
 * 
 * The United States Government has rights in this work pursuant
 * to contract no. DE-AC03-76SF00098 between the United States
 * Department of Energy and the University of California.
 *
 * Redistribution and use in source and binary forms are permitted provided
 * that: (1) source distributions retain this entire copyright notice and
 * comment, and (2) distributions including binaries display the following
 * acknowledgement:  ``This product includes software developed by the
 * University of California, Berkeley and its contributors'' in the
 * documentation or other materials provided with the distribution and in
 * all advertising materials mentioning features or use of this software.
 * Neither the name of the University nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

#ifndef lint
static char rcsid[] =
    "@(#) $Header: /home/horse/u0/vern/flex/RCS/gen.c,v 2.12 91/03/28 12:01:38 vern Exp $ (LBL)";
#endif

#include "flexdef.h"


/* declare functions that have forward references */

void gen_next_state PROTO((int));
void genecs PROTO(());
void indent_put2s PROTO((char [], char []));
void indent_puts PROTO((char []));


static int indent_level = 0; /* each level is 4 spaces */

#define indent_up() (++indent_level)
#define indent_down() (--indent_level)
#define set_indent(indent_val) indent_level = indent_val

/* *everything* is done in terms of arrays starting at 1, so provide
 * a null entry for the zero element of all C arrays
 */
static char C_short_decl[] = "static const short int %s[%d] =\n    {   0,\n";
static char C_long_decl[] = "static const long int %s[%d] =\n    {   0,\n";
static char C_state_decl[] =
	"static const yy_state_type %s[%d] =\n    {   0,\n";


/* indent to the current level */

void do_indent()

    {
    register int i = indent_level * 4;

    while ( i >= 8 )
	{
	putchar( '\t' );
	i -= 8;
	}
    
    while ( i > 0 )
	{
	putchar( ' ' );
	--i;
	}
    }


/* generate the code to keep backtracking information */

void gen_backtracking()

    {
    if ( reject || num_backtracking == 0 )
	return;

    if ( fullspd )
	indent_puts( "if ( yy_current_state[-1].yy_nxt )" );
    else
	indent_puts( "if ( yy_accept[yy_current_state] )" );

    indent_up();
    indent_puts( "{" );
    indent_puts( "yy_last_accepting_state = yy_current_state;" );
    indent_puts( "yy_last_accepting_cpos = yy_cp;" );
    indent_puts( "}" );
    indent_down();
    }


/* generate the code to perform the backtrack */

void gen_bt_action()

    {
    if ( reject || num_backtracking == 0 )
	return;

    set_indent( 3 );

    indent_puts( "case 0: /* must backtrack */" );
    indent_puts( "/* undo the effects of YY_DO_BEFORE_ACTION */" );
    indent_puts( "*yy_cp = yy_hold_char;" );

    if ( fullspd || fulltbl )
	indent_puts( "yy_cp = yy_last_accepting_cpos + 1;" );
    else
	/* backtracking info for compressed tables is taken \after/
	 * yy_cp has been incremented for the next state
	 */
	indent_puts( "yy_cp = yy_last_accepting_cpos;" );

    indent_puts( "yy_current_state = yy_last_accepting_state;" );
    indent_puts( "goto yy_find_action;" );
    putchar( '\n' );

    set_indent( 0 );
    }


/* genctbl - generates full speed compressed transition table
 *
 * synopsis
 *     genctbl();
 */

void genctbl()

    {
    register int i;
    int end_of_buffer_action = num_rules + 1;

    /* table of verify for transition and offset to next state */
    printf( "static const struct yy_trans_info yy_transition[%d] =\n",
	    tblend + numecs + 1 );
    printf( "    {\n" );
    
    /* We want the transition to be represented as the offset to the
     * next state, not the actual state number, which is what it currently is.
     * The offset is base[nxt[i]] - base[chk[i]].  That's just the
     * difference between the starting points of the two involved states
     * (to - from).
     *
     * first, though, we need to find some way to put in our end-of-buffer
     * flags and states.  We do this by making a state with absolutely no
     * transitions.  We put it at the end of the table.
     */
    /* at this point, we're guaranteed that there's enough room in nxt[]
     * and chk[] to hold tblend + numecs entries.  We need just two slots.
     * One for the action and one for the end-of-buffer transition.  We
     * now *assume* that we're guaranteed the only character we'll try to
     * index this nxt/chk pair with is EOB, i.e., 0, so we don't have to
     * make sure there's room for jam entries for other characters.
     */

    base[lastdfa + 1] = tblend + 2;
    nxt[tblend + 1] = end_of_buffer_action;
    chk[tblend + 1] = numecs + 1;
    chk[tblend + 2] = 1; /* anything but EOB */
    nxt[tblend + 2] = 0; /* so that "make test" won't show arb. differences */

    /* make sure every state has a end-of-buffer transition and an action # */
    for ( i = 0; i <= lastdfa; ++i )
	{
	register int anum = dfaacc[i].dfaacc_state;

	chk[base[i]] = EOB_POSITION;
	chk[base[i] - 1] = ACTION_POSITION;
	nxt[base[i] - 1] = anum;	/* action number */
	}

    for ( i = 0; i <= tblend; ++i )
	{
	if ( chk[i] == EOB_POSITION )
	    transition_struct_out( 0, base[lastdfa + 1] - i );

	else if ( chk[i] == ACTION_POSITION )
	    transition_struct_out( 0, nxt[i] );

	else if ( chk[i] > numecs || chk[i] == 0 )
	    transition_struct_out( 0, 0 );		/* unused slot */

	else	/* verify, transition */
	    transition_struct_out( chk[i], base[nxt[i]] - (i - chk[i]) );
	}


    /* here's the final, end-of-buffer state */
    transition_struct_out( chk[tblend + 1], nxt[tblend + 1] );
    transition_struct_out( chk[tblend + 2], nxt[tblend + 2] );

    printf( "    };\n" );
    printf( "\n" );

    /* table of pointers to start states */
    printf( "static const struct yy_trans_info *yy_start_state_list[%d] =\n",
	    lastsc * 2 + 1 );
    printf( "    {\n" );

    for ( i = 0; i <= lastsc * 2; ++i )
	printf( "    &yy_transition[%d],\n", base[i] );

    dataend();

    if ( useecs )
	genecs();
    }


/* generate equivalence-class tables */

void genecs()

    {
    register int i, j;
    static char C_char_decl[] = "static const %s %s[%d] =\n    {   0,\n";
    int numrows;
    Char clower();

    if ( numecs < csize )
	printf( C_char_decl, "YY_CHAR", "yy_ec", csize );
    else
	printf( C_char_decl, "short", "yy_ec", csize );

    for ( i = 1; i < csize; ++i )
	{
	if ( caseins && (i >= 'A') && (i <= 'Z') )
	    ecgroup[i] = ecgroup[clower( i )];

	ecgroup[i] = abs( ecgroup[i] );
	mkdata( ecgroup[i] );
	}

    dataend();

    if ( trace )
	{
	char *readable_form();

	fputs( "\n\nEquivalence Classes:\n\n", stderr );

	numrows = csize / 8;

	for ( j = 0; j < numrows; ++j )
	    {
	    for ( i = j; i < csize; i = i + numrows )
		{
		fprintf( stderr, "%4s = %-2d", readable_form( i ), ecgroup[i] );

		putc( ' ', stderr );
		}

	    putc( '\n', stderr );
	    }
	}
    }


/* generate the code to find the action number */

void gen_find_action()

    {
    if ( fullspd )
	indent_puts( "yy_act = yy_current_state[-1].yy_nxt;" );

    else if ( fulltbl )
	indent_puts( "yy_act = yy_accept[yy_current_state];" );

    else if ( reject )
	{
	indent_puts( "yy_current_state = *--yy_state_ptr;" );
	indent_puts( "yy_lp = yy_accept[yy_current_state];" );

	puts( "find_rule: /* we branch to this label when backtracking */" );

	indent_puts( "for ( ; ; ) /* until we find what rule we matched */" );

	indent_up();

	indent_puts( "{" );

	indent_puts( "if ( yy_lp && yy_lp < yy_accept[yy_current_state + 1] )" );
	indent_up();
	indent_puts( "{" );
	indent_puts( "yy_act = yy_acclist[yy_lp];" );

	if ( variable_trailing_context_rules )
	    {
	    indent_puts( "if ( yy_act & YY_TRAILING_HEAD_MASK ||" );
	    indent_puts( "     yy_looking_for_trail_begin )" );
	    indent_up();
	    indent_puts( "{" );

	    indent_puts( "if ( yy_act == yy_looking_for_trail_begin )" );
	    indent_up();
	    indent_puts( "{" );
	    indent_puts( "yy_looking_for_trail_begin = 0;" );
	    indent_puts( "yy_act &= ~YY_TRAILING_HEAD_MASK;" );
	    indent_puts( "break;" );
	    indent_puts( "}" );
	    indent_down();

	    indent_puts( "}" );
	    indent_down();

	    indent_puts( "else if ( yy_act & YY_TRAILING_MASK )" );
	    indent_up();
	    indent_puts( "{" );
	    indent_puts(
		"yy_looking_for_trail_begin = yy_act & ~YY_TRAILING_MASK;" );
	    indent_puts(
		"yy_looking_for_trail_begin |= YY_TRAILING_HEAD_MASK;" );

	    if ( real_reject )
		{
		/* remember matched text in case we back up due to REJECT */
		indent_puts( "yy_full_match = yy_cp;" );
		indent_puts( "yy_full_state = yy_state_ptr;" );
		indent_puts( "yy_full_lp = yy_lp;" );
		}

	    indent_puts( "}" );
	    indent_down();

	    indent_puts( "else" );
	    indent_up();
	    indent_puts( "{" );
	    indent_puts( "yy_full_match = yy_cp;" );
	    indent_puts( "yy_full_state = yy_state_ptr;" );
	    indent_puts( "yy_full_lp = yy_lp;" );
	    indent_puts( "break;" );
	    indent_puts( "}" );
	    indent_down();

	    indent_puts( "++yy_lp;" );
	    indent_puts( "goto find_rule;" );
	    }

	else
	    {
	    /* remember matched text in case we back up due to trailing context
	     * plus REJECT
	     */
	    indent_up();
	    indent_puts( "{" );
	    indent_puts( "yy_full_match = yy_cp;" );
	    indent_puts( "break;" );
	    indent_puts( "}" );
	    indent_down();
	    }

	indent_puts( "}" );
	indent_down();

	indent_puts( "--yy_cp;" );

	/* we could consolidate the following two lines with those at
	 * the beginning, but at the cost of complaints that we're
	 * branching inside a loop
	 */
	indent_puts( "yy_current_state = *--yy_state_ptr;" );
	indent_puts( "yy_lp = yy_accept[yy_current_state];" );

	indent_puts( "}" );

	indent_down();
	}

    else
	/* compressed */
	indent_puts( "yy_act = yy_accept[yy_current_state];" );
    }


/* genftbl - generates full transition table
 *
 * synopsis
 *     genftbl();
 */

void genftbl()

    {
    register int i;
    int end_of_buffer_action = num_rules + 1;

    printf( C_short_decl, "yy_accept", lastdfa + 1 );


    dfaacc[end_of_buffer_state].dfaacc_state = end_of_buffer_action;

    for ( i = 1; i <= lastdfa; ++i )
	{
	register int anum = dfaacc[i].dfaacc_state;

	mkdata( anum );

	if ( trace && anum )
	    fprintf( stderr, "state # %d accepts: [%d]\n", i, anum );
	}

    dataend();

    if ( useecs )
	genecs();

    /* don't have to dump the actual full table entries - they were created
     * on-the-fly
     */
    }


/* generate the code to find the next compressed-table state */

void gen_next_compressed_state( char_map )
char *char_map;

    {
    indent_put2s( "register YY_CHAR yy_c = %s;", char_map );

    /* save the backtracking info \before/ computing the next state
     * because we always compute one more state than needed - we
     * always proceed until we reach a jam state
     */
    gen_backtracking();

    indent_puts(
    "while ( yy_chk[yy_base[yy_current_state] + yy_c] != yy_current_state )" );
    indent_up();
    indent_puts( "{" );
    indent_puts( "yy_current_state = yy_def[yy_current_state];" );

    if ( usemecs )