elimunit.c

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

    for( raction = state->redun; ; ++raction ) {
        pro = raction->pro;
        if( pro == NULL ) break;
        if( save_pro != NULL ) {
            /* state contains at least two reductions */
            return( NULL );
        }
        if( ! pro->unit ) {
            /* state contains at least one reduction by a non-unit production */
            return( NULL );
        }
        save_pro = pro;
    }
    if( save_pro == NULL ) {
        /* should never execute this but just in case... */
        return( NULL );
    }
    return( save_pro->sym );
}

static void removeParent( a_state *child, a_state *parent )
{
    a_parent **prev;
    a_parent *curr;

    if( child->parents == NULL ) {
        return;
    }
    prev = &(child->parents);
    for( curr = *prev; curr != NULL; curr = curr->next ) {
        if( curr->state == parent ) {
            *prev = curr->next;
            free( curr );
            break;
        }
        prev = &(curr->next);
    }
    if( child->parents == NULL ) {
        ++deadStates;
        Dead( *child );
    }
}

static a_state *onlyShiftsOnTerminals( a_state *state )
{
    a_shift_action *saction;
    a_sym *shift_sym;

    /*
        If there are shifts on non-terminals then the unit reduction
        is important because it moves to the correct state for more
        reductions.  We cannot remove this unit reduction.
    */
    saction = state->trans;
    for(;;) {
        shift_sym = saction->sym;
        if( shift_sym == NULL ) break;
        if( shift_sym->pro != NULL ) {
            return( NULL );
        }
        ++saction;
    }
    return( state );
}

static int immediateShift( a_state *state, a_reduce_action *raction, a_pro *pro )
{
    a_sym *unit_lhs;
    a_sym *term_sym;
    a_state *after_lhs_state;
    a_state *final_state;
    a_state *check_state;
    a_parent *parent;
    a_word *follow;
    short *terminal;
    int change_occurred;

    /*
        requirements:
        (1) state must have a reduction by a unit production (L1 <- r1) on
            a set of tokens (s)
        (2) all parents must shift to a state where a shift on a terminal
            in s ends up in a new state that is the same for all parents

        action:
            add shift on terminal to common parent shift state
    */
    //dumpInternalState( state );
    follow = raction->follow;
    unit_lhs = pro->sym;
    change_occurred = 0;
    terminal = Members( follow, setmembers );
    while( --terminal >= setmembers ) {
        term_sym = symtab[ *terminal ];
        check_state = NULL;
        for( parent = state->parents; parent != NULL; parent = parent->next ) {
            after_lhs_state = findNewShiftState( parent->state, unit_lhs );
            after_lhs_state = onlyShiftsOnTerminals( after_lhs_state );
            if( after_lhs_state == NULL ) {
                check_state = NULL;
                break;
            }
            final_state = findNewShiftState( after_lhs_state, term_sym );
            if( final_state == NULL ) {
                check_state = NULL;
                break;
            }
            if( check_state != NULL && check_state != final_state ) {
                check_state = NULL;
                break;
            }
            check_state = final_state;
        }
        if( check_state != NULL ) {
            /* all shifts in *terminal ended up in the same state! */
            state->trans = addShiftAction( term_sym, check_state, state->trans );
            ClearBit( follow, *terminal );
            change_occurred = 1;
            ++changeOccurred;
        }
    }
    if( Empty( follow ) ) {
        state->redun = removeReduceAction( raction, state->redun );
        change_occurred = 1;
    }
    return( change_occurred );
}

static int multiUnitReduce( a_state *state, a_reduce_action *raction, a_pro *pro, a_word *reduce_set )
{
    a_pro *new_pro;

    /*
        requirements:
        (1) state must have a reduction by a unit production (L1 <- r1) on
            a set of tokens (s)
        (2) all parents must reduce by an unit production (L2 <- L1) on
            a set of tokens (t)

        action:
            change state to reduce (L2<-r1) instead of (L1<-r1) on t
            (if s != t, we have to add a new reduce action)
    */
    Assign( reduce_set, raction->follow );
    new_pro = analyseParents( state, pro, reduce_set );
    if( new_pro != NULL ) {
        /* parents satisfied all the conditions */
        if( Equal( reduce_set, raction->follow ) ) {
            raction->pro = new_pro;
        } else {
            AndNot( raction->follow, reduce_set );
            state->redun = addReduceAction( new_pro, reduce_set, state->redun );
        }
        ++changeOccurred;
        return( 1 );
    }
    return( 0 );
}

static int shiftToSingleReduce( a_state *state, a_shift_action *saction )
{
    a_state *sub_state;
    a_sym *new_lhs;
    int made_change;

    /*
        requirements:
        (1) state (s1) must have a shift on token (t) into a state (s2)
            that only has one action and it must be a reduction by
            an unit production
            (after which state (s1) will shift into state (s3))

        action:
            change shift action for token (t) to shift into state (s3)
    */
    made_change = 0;
    for(;;) {
        sub_state = saction->state;
        new_lhs = onlyOneReduction( sub_state );
        if( new_lhs == NULL ) break;
        saction->state = findNewShiftState( state, new_lhs );
        removeParent( sub_state, state );
        made_change = 1;
        ++changeOccurred;
    }
    saction->units_checked = TRUE;
    return( made_change );
}

static void tryElimination( a_state *state, a_word *reduce_set )
{
    a_reduce_action *raction;
    a_pro *pro;

    if( IsDead( *state ) ) {
        return;
    }
    if( IsAmbiguous( *state ) ) {
        return;
    }
    // iterate over all reductions in state
    for(;;) {
        for( raction = state->redun; ; ++raction ) {
            pro = raction->pro;
            if( pro == NULL ) break;
            if( pro->unit ) {
                if( multiUnitReduce( state, raction, pro, reduce_set ) ) {
                    /* state->redun could have changed */
                    break;
                }
                if( immediateShift( state, raction, pro ) ) {
                    /* state->redun could have changed */
                    break;
                }
            }
        }
        if( pro == NULL ) break;
    }
}

static void tossSingleReduceStates( a_state *state )
{
    a_shift_action *saction;
    a_sym *shift_sym;

    if( IsDead( *state ) ) {
        return;
    }
    /* iterate over all shifts in the state */
    for( saction = state->trans; ; ++saction ) {
        shift_sym = saction->sym;
        if( shift_sym == NULL ) break;
        if( saction->units_checked ) continue;
        shiftToSingleReduce( state, saction );
    }
}

void EliminateUnitReductions( void )
/**********************************/
{
    unsigned sum;
    a_word *reduce_set;
    int i;

    sum = 0;
    do {
        changeOccurred = 0;
        for( i = 0; i < nstate; ++i ) {
            tossSingleReduceStates( statetab[i] );
        }
        sum += changeOccurred;
    } while( changeOccurred );
    reduce_set = CALLOC( wperset, a_word );
    do {
        changeOccurred = 0;
        for( i = 0; i < nstate; ++i ) {
            tryElimination( statetab[i], reduce_set );
        }
        sum += changeOccurred;
    } while( changeOccurred );
    free( reduce_set );
    dumpstatistic( "unit reduction states removed", deadStates );
    dumpstatistic( "unit reduction optimizations", sum );
}