genfast.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 585 行 · 第 1/2 页

    }
    return( 0 );
}

static unsigned *orderActionVectors( action_t **av, unsigned size )
{
    av_info **a;
    av_info *p;
    action_t *v;
    unsigned num_entries;
    unsigned max;
    unsigned min;
    unsigned i, j;
    unsigned *map;

    a = MALLOC( nstate, av_info * );
    for( j = 0; j < nstate; ++j ) {
        v = av[j];
        p = MALLOC( 1, av_info );
        a[j] = p;
        max = 0;
        min = size;
        num_entries = 0;
        for( i = 0; i < size; ++i ) {
            if( v[i] != ACTION_NULL ) {
                if( num_entries == 0 ) {
                    min = i;
                }
                ++num_entries;
                max = i;
            }
        }
        p->min = min;
        p->max = max;
        p->num_entries = num_entries;
        p->index = j;
        p->action_vector = av[j];
    }
    qsort( a, nstate, sizeof( av_info * ), cmp_action );
    map = MALLOC( nstate, unsigned );
    for( i = 0; i < nstate; ++i ) {
        map[i] = a[i]->index;
        av[i] = a[i]->action_vector;
        free( a[i] );
        a[i] = NULL;
    }
    free( a );
    return( map );
}

static void createYACCTables( void )
{
    unsigned i;
    unsigned j;
    unsigned asize;
    unsigned index;
    unsigned mask;
    unsigned token;
    unsigned vsize;
    unsigned bsize;
    unsigned *mapping;
    value_size bitv_base_size;
    byte *state_vector;
    byte *bvector;
    compressed_action * ca;
    unsigned num_actions;
    short *p;
    unsigned *base;
    unsigned *abase;
    unsigned *gbase;
    action_t *state_actions;
    action_t *avector;
    action_t **all_actions;
    a_state *state;
    a_shift_action *saction;
    a_reduce_action *raction;
    a_sym *sym;
    a_pro *pro;
    an_item *first_item;
    an_item *item;
    unsigned empty_actions;
    unsigned *defaction;
    index_t state_idx;

    bvector = NULL;
    bsize = 0;
    vsize = ( maxTerminal + (8-1) ) / 8 + 1;
    state_vector = MALLOC( vsize, byte );
    base = CALLOC( nstate, unsigned );
    for( i = 0; i < nstate; ++i ) {
        state = statetab[i];
        memset( state_vector, 0, vsize );
        // iterate over all shifts in state
        for( saction = state->trans; ; ++saction ) {
            sym = saction->sym;
            if( sym == NULL ) break;
            if( sym->pro != NULL ) {
                // we only want terminals
                continue;
            }
            if( saction->is_default ) {
                // we want these to be default actions
                continue;
            }
            token = sym->token;
            index = token >> 3;
            mask = 1 << ( token & 0x07 );
            state_vector[index] |= mask;
        }
        // iterate over all reductions in state
        for( raction = state->redun; ; ++raction ) {
            pro = raction->pro;
            if( pro == NULL ) break;
            if( state->default_reduction == raction ) continue;
            for( p = Members( raction->follow, setmembers ); --p >= setmembers; ) {
                token = symtab[*p]->token;
                index = token >> 3;
                mask = 1 << ( token & 0x07 );
                state_vector[index] |= mask;
            }
        }
        base[i] = insertIntoBitVector( &bvector, &bsize, state_vector, vsize );
    }
    defaction = CALLOC( nstate, unsigned );
    all_actions = MALLOC( nstate, action_t * );
    for( i = 0; i < nstate; ++i ) {
        state = statetab[i];
        state_actions = MALLOC( maxTerminal, action_t );
        all_actions[i] = state_actions;
        for( j = 0; j < maxTerminal; ++j ) {
            state_actions[j] = ACTION_NULL;
        }
        // iterate over all shifts in state
        for( saction = state->trans; ; ++saction ) {
            sym = saction->sym;
            if( sym == NULL ) break;
            if( sym->pro != NULL ) continue;
            state_idx = saction->state->sidx;
            if( saction->is_default ) {
                defaction[ i ] = state_idx;
                continue;
            }
            token = sym->token;
            state_actions[token] = state_idx;
        }
        // iterate over all reductions in state
        for( raction = state->redun; ; ++raction ) {
            pro = raction->pro;
            if( pro == NULL ) break;
            if( state->default_reduction == raction ) {
                defaction[i] = reduceaction( state, raction );
                continue;
            }
            for( p = Members( raction->follow, setmembers ); --p >= setmembers; ) {
                token = symtab[*p]->token;
                state_actions[token] = reduceaction( state, raction );
            }
        }
    }
    mapping = orderActionVectors( all_actions, maxTerminal );
    avector = NULL;
    asize = 0;
    ca = CALLOC( maxTerminal, compressed_action );
    abase = CALLOC( nstate, unsigned );
    for( i = 0; i < nstate; ++i ) {
        num_actions = actcompress( ca, all_actions[i], maxTerminal );
        abase[mapping[i]] = insertIntoActionVector( &avector, &asize,
                                        ca, num_actions, maxTerminal );
        free( all_actions[i] );
        all_actions[i] = NULL;
    }
    free( mapping );
    free( ca );
    for( i = 0; i < nstate; ++i ) {
        state = statetab[i];
        state_actions = MALLOC( maxNonTerminal, action_t );
        all_actions[i] = state_actions;
        for( j = 0; j < maxNonTerminal; ++j ) {
            state_actions[j] = ACTION_NULL;
        }
        // iterate over all shifts in state
        for( saction = state->trans; ; ++saction ) {
            sym = saction->sym;
            if( sym == NULL ) break;
            if( sym->pro == NULL ) continue;
            token = sym->token;
            state_actions[token] = saction->state->sidx;
        }
    }
    mapping = orderActionVectors( all_actions, maxNonTerminal );
    ca = CALLOC( maxNonTerminal, compressed_action );
    gbase = CALLOC( nstate, unsigned );
    for( i = 0; i < nstate; ++i ) {
        num_actions = actcompress( ca, all_actions[i], maxNonTerminal );
        gbase[mapping[i]] = insertIntoActionVector( &avector, &asize,
                                        ca, num_actions, maxNonTerminal );
        free( all_actions[i] );
        all_actions[i] = NULL;
    }
    free( mapping );
    free( ca );
    putcomment( "index by state to get default action for state" );
    begtab( "YYACTIONTYPE", "yydefaction" );
    for( i = 0; i < nstate; ++i ) {
        puttab( FITS_A_WORD, defaction[i] );
    }
    endtab();
    free( defaction );
    bitv_base_size = FITS_A_WORD;
    if( bsize < 257 ) {
        bitv_base_size = FITS_A_BYTE;
    }
    putcomment( "index by state to get offset into bit vector" );
    begtab( "YYBITBASETYPE", "yybitbase" );
    for( i = 0; i < nstate; ++i ) {
        puttab( bitv_base_size, base[i] );
    }
    endtab();
    putcomment( "index by token (from state base) to see if token is valid in state" );
    begtab( "YYBITTYPE", "yybitcheck" );
    for( i = 0; i < bsize; ++i ) {
        puttab( FITS_A_BYTE, bvector[i] );
    }
    endtab();
    putcomment( "index by state to get offset into action vector" );
    begtab( "YYACTIONBASETYPE", "yyactionbase" );
    for( i = 0; i < nstate; ++i ) {
        puttab( FITS_A_WORD, abase[i] );
    }
    endtab();
    putcomment( "index by state to get offset into action vector" );
    begtab( "YYACTIONBASETYPE", "yygotobase" );
    for( i = 0; i < nstate; ++i ) {
        puttab( FITS_A_WORD, gbase[i] );
    }
    endtab();
    putcomment( "index by token (from state base) to get action for state" );
    empty_actions = 0;
    begtab( "YYACTIONTYPE", "yyaction" );
    for( i = 0; i < asize; ++i ) {
        if( avector[i] == ACTION_NULL ) {
            ++empty_actions;
        }
        puttab( FITS_A_WORD, avector[i] );
    }
    endtab();
    putcomment( "index by rule to get length of rule" );
    begtab( "YYPLENTYPE", "yyplentab" );
    for( i = 0; i < npro; ++i ) {
        first_item = protab[i]->item;
        for( item = first_item; item->p.sym; ++item )
          /* do nothing */;
        puttab( FITS_A_BYTE, item - first_item );
    }
    endtab();
    putcomment( "index by rule to get left hand side token" );
    begtab( "YYPLHSTYPE", "yyplhstab" );
    for( i = 0; i < npro; ++i ) {
        puttab( FITS_A_WORD, protab[i]->sym->token );
    }
    endtab();
    free( all_actions );
    free( base );
    free( abase );
    free( gbase );
    free( bvector );
    free( avector );
    free( state_vector );
    dumpstatistic( "bytes used in tables", bytesused );
    dumpstatistic( "table space utilization", 100 - ( empty_actions * 100L / asize ) );
}

void GenFastTables( void )
{
    assignAllTokenValues();
    putnum( "YYNOACTION", 0 );
    putnum( "YYEOFTOKEN", eofsym->token );
    putnum( "YYERRTOKEN", errsym->token );
    putnum( "YYETOKEN", errsym->token );
    putnum( "YYSTART", startstate->sidx );
    putnum( "YYSTOP", eofsym->enter->sidx );
    putnum( "YYERR", errstate->sidx );
    putnum( "YYUSED", nstate );
    if( keyword_id_low != 0 && default_shiftflag ) {
        putnum( "YYKEYWORD_ID_LOW", keyword_id_low );
        putnum( "YYKEYWORD_ID_HIGH", keyword_id_high );
    }
    putambigs( NULL );
    createYACCTables();
    puttokennames( 0, FITS_A_WORD );
}