elimunit.c

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

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  Eliminate unit productions.
*
****************************************************************************/


#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include "yacc.h"
#include "yaccins.h"
#include "alloc.h"

static unsigned changeOccurred;
static unsigned deadStates;

#if 0
void dumpInternalState( a_state *x )
{
    a_parent *parent;
    a_shift_action *tx;
    a_reduce_action *rx;
    unsigned col, new_col;
    short int *p;
    a_name name;

    printf( "state %d: %p (%u)\n", x->sidx, x, x->kersize );
    printf( "  parent states:" );
    col = 4;
    for( parent = x->parents; parent != NULL; parent = parent->next ) {
        printf( " %d(%p)", parent->state->sidx, parent->state );
        --col;
        if( col == 0 ) {
            printf( "\n" );
            col = 5;
        }
    }
    printf( "\n" );
    if( x->name.item[0] == NULL || !IsState( *x->name.item[0] ) ) {
        for( name.item = x->name.item; *name.item; ++name.item ) {
            showitem( *name.item, " ." );
        }
    } else {
        for( name.state = x->name.state; *name.state; ++name.state ) {
            printf( " %d", (*name.state)->sidx );
        }
        printf( "\n" );
    }
    printf( "actions:" );
    col = 8;
    for( tx = x->trans; tx->sym; ++tx ) {
        new_col = col + 1 + strlen( tx->sym->name ) + 1 + 1 + 3;
        if( new_col > 79 ) {
            putchar('\n');
            new_col -= col;
        }
        col = new_col;
        printf( " %s:s%03d", tx->sym->name, tx->state->sidx );
    }
    putchar( '\n' );
    col = 0;
    for( rx = x->redun; rx->pro; ++rx ) {
        for( p = Members( rx->follow, setmembers ); --p >= setmembers; ) {
            new_col = col + 1 + strlen( symtab[*p]->name );
            if( new_col > 79 ) {
                putchar('\n');
                new_col -= col;
            }
            col = new_col;
            printf( " %s", symtab[*p]->name );
        }
        new_col = col + 1 + 5;
        if( new_col > 79 ) {
            putchar('\n');
            new_col -= col;
        }
        col = new_col;
        printf( ":r%03d", rx->pro->pidx );
    }
    putchar( '\n' );
}
#endif

static a_state *findNewShiftState( a_state *state, a_sym *sym )
{
    a_shift_action *saction;
    a_sym *shift_sym;

    saction = state->trans;
    for(;;) {
        shift_sym = saction->sym;
        if( shift_sym == NULL ) break;
        if( shift_sym == sym ) {
            return( saction->state );
        }
        ++saction;
    }
    return( NULL );
}

static a_pro *analyseParents( a_state *state, a_pro *pro, a_word *reduce_set )
{
    a_pro *test_pro;
    a_pro *new_pro;
    a_sym *old_lhs;
    a_state *parent_state;
    a_state *new_state;
    a_parent *parent;
    a_parent *split_parent;
    a_reduce_action *raction;

    split_parent = NULL;
    new_pro = NULL;
    old_lhs = pro->sym;
    for( parent = state->parents; parent != NULL; parent = parent->next ) {
        parent_state = parent->state;
        new_state = findNewShiftState( parent_state, old_lhs );
        if( new_state == NULL ) {
            printf( "error! %u %s %u\n", state->sidx, old_lhs->name, parent_state->sidx );
            exit(1);
        }
        for( raction = new_state->redun; ; ++raction ) {
            test_pro = raction->pro;
            if( test_pro == NULL ) break;
            if( !test_pro->unit ) {
                continue;
            }
            if( EmptyIntersection( reduce_set, raction->follow ) ) {
                continue;
            }
            if( new_pro == NULL ) {
                new_pro = test_pro;
            } else if( new_pro != test_pro ) {
                new_pro = NULL;
                break;
            }
            /* we have a reduce of a unit rule on similar tokens */
            Intersection( reduce_set, raction->follow );
            break;
        }
        if( new_pro == NULL || test_pro == NULL ) {
            split_parent = parent;
        }
    }
    if( Empty( reduce_set ) || split_parent != NULL ) {
        new_pro = NULL;
    }
    return( new_pro );
}

static a_shift_action *addShiftAction( a_sym *sym, a_state *state, a_shift_action *s )
{
    a_shift_action *saction;
    a_shift_action *new_saction;
    int i;

    for( saction = s; saction->sym != NULL; ++saction ) {
    }
    i = saction - s;
    new_saction = realloc( s, ( i + 2 ) * sizeof(a_shift_action) );
    memset( &new_saction[i], 0, sizeof( *new_saction ) * 2 );
    new_saction[i].sym = sym;
    new_saction[i].state = state;
    new_saction[i+1].sym = NULL;
    new_saction[i+1].state = NULL;
    return( new_saction );
}

static a_reduce_action *addReduceAction( a_pro *pro, a_word *follow, a_reduce_action *r )
{
    a_reduce_action *raction;
    a_reduce_action *new_raction;
    a_word *new_follow;
    int i;

    for( raction = r; raction->pro != NULL; ++raction ) {
    }
    i = raction - r;
    new_follow = CALLOC( wperset, a_word );
    Assign( new_follow, follow );
    new_raction = realloc( r, ( i + 2 ) * sizeof(a_reduce_action) );
    new_raction[i].pro = pro;
    new_raction[i].follow = new_follow;
    new_raction[i+1].pro = NULL;
    new_raction[i+1].follow = NULL;
    return( new_raction );
}

static a_reduce_action *removeReduceAction( a_reduce_action *remove, a_reduce_action *r )
{
    a_reduce_action *raction;
    a_reduce_action *copy_raction;

    copy_raction = NULL;
    raction = r;
    for(;;) {
        if( raction == remove ) {
            copy_raction = remove;
        } else {
            if( copy_raction != NULL ) {
                *copy_raction = *raction;
                ++copy_raction;
            }
        }
        if( raction->pro == NULL ) break;
        ++raction;
    }
    return( r );
}

static a_sym *onlyOneReduction( a_state *state )
{
    a_reduce_action *raction;
    a_shift_action *saction;
    a_pro *pro;
    a_pro *save_pro;
    a_sym *shift_sym;

    /*
        We shouldn't kill ambiguous states because a user that has to deal
        with a crazy language (like C++) might want to keep the state around.
        This check has the dual benefit of eliminating a lot of checking
        and solving part of the ambiguous state problem.
    */
    if( state->kersize != 1 ) {
        return( NULL );
    }
    if( IsAmbiguous( *state ) ) {
        /* catch all of the ambiguous states */
        return( NULL );
    }
    /* iterate over all shifts in the state */
    saction = state->trans;
    shift_sym = saction->sym;
    if( shift_sym != NULL ) {
        /* state contains at least one shift */
        return( NULL );
    }
    // iterate over all reductions in state
    save_pro = NULL;