lalr1.c

开放源码的编译器open watcom 1.6.0版的源代码

                        continue;
                    }
                    if( conflict->sym != sym ) {
                        continue;
                    }
                    break;
                }
                if( cx == NULL ) {
                    all_match = 0;
                    break;
                }
                last = cx;
            }
            if( all_match ) {
                /* found the desired S/R conflict */
                Ambiguous( *state );
                conflict = last->conflict;
                conflict->state = state;
                conflict->shift = saction->state;
                conflict->reduce = rule;
                return;
            }
        }
    }
}

static void resolve( a_state *x, short *work, a_reduce_action **reduce )
{
    a_shift_action *tx, *ux;
    a_reduce_action *rx;
    short int *p, *w;
    int i;
    a_prec symprec, proprec, prevprec;


    w = work;
    for( rx = x->redun; rx->pro; ++rx ) {
        p = Members( rx->follow, setmembers );
        while( --p >= setmembers ) {
            if( reduce[*p] ) {
                prevprec = reduce[*p]->pro->prec;
                proprec = rx->pro->prec;
                if( !prevprec.prec || !proprec.prec
                ||  prevprec.prec == proprec.prec ) {
                    *w++ = *p;
                    /* resolve to the earliest production */
                    if( rx->pro->pidx >= reduce[*p]->pro->pidx ) {
                        continue;
                    }
                } else if( prevprec.prec > proprec.prec ) {
                    /* previous rule had higher precedence so leave it alone */
                    continue;
                }
            }
            reduce[*p] = rx;
        }
    }
    while( --w >= work ) {
        if( *w == errsym->token ) continue;
        printf( "r/r conflict in state %d on %s:\n", x->sidx, symtab[*w]->name);
        ++RR_conflicts;
        for( rx = x->redun; rx->pro; ++rx ) {
            if( IsBitSet( rx->follow, *w ) ) {
                showitem( rx->pro->item, "" );
            }
        }
        printf( "\n" );
        for( rx = x->redun; rx->pro; ++rx ) {
            if( IsBitSet( rx->follow, *w ) ) {
                ShowSentence( x, symtab[*w], rx->pro, NULL );
            }
        }
        printf( "---\n\n" );
    }
    for( tx = ux = x->trans; tx->sym; ++tx ) {
        i = tx->sym->idx;
        if( i >= nterm || !reduce[i] ) {
            *ux++ = *tx;
        } else {
            /* shift/reduce conflict detected */
            check_for_user_hooks( x, tx, reduce[i]->pro->pidx );
            symprec = tx->sym->prec;
            proprec = reduce[i]->pro->prec;
            if( !symprec.prec || !proprec.prec ) {
                if( tx->sym != errsym ) {
                    printf( "s/r conflict in state %d on %s:\n",
                    x->sidx, tx->sym->name );
                    ++SR_conflicts;
                    printf( "\tshift to %d\n", tx->state->sidx );
                    showitem( reduce[i]->pro->item, "" );
                    printf( "\n" );
                    ShowSentence( x, tx->sym, reduce[i]->pro, NULL );
                    ShowSentence( x, tx->sym, NULL, tx->state );
                    printf( "---\n\n" );
                }
                *ux++ = *tx;
                reduce[i] = NULL;
            } else {
                if( symprec.prec > proprec.prec ) {
                    *ux++ = *tx;
                    reduce[i] = NULL;
                } else if( symprec.prec == proprec.prec ) {
                    if( symprec.assoc == R_ASSOC ) {
                        *ux++ = *tx;
                        reduce[i] = NULL;
                    } else if( symprec.assoc == NON_ASSOC ) {
                        ux->sym = tx->sym;
                        ux->state = errstate;
                        ++ux;
                        reduce[i] = NULL;
                    }
                }
            }
        }
    }
    ux->sym = NULL;
    for( rx = x->redun; rx->pro; ++rx ) {
        Clear( rx->follow );
    }
    for( i = 0; i < nterm; ++i ) {
        if( reduce[i] ) {
            SetBit( reduce[i]->follow, i );
            reduce[i] = NULL;
        }
    }
}

static void Conflict( void )
{
    a_word *set;
    a_state *x;
    a_shift_action *tx;
    a_reduce_action *rx;
    a_reduce_action **reduce;
    short *work;
    int i;

    set = CALLOC( wperset, a_word );
    reduce = CALLOC( nterm, a_reduce_action * );
    work = CALLOC( nterm, short );
    for( x = statelist; x; x = x->next ) {
        Clear( set );
        for( tx = x->trans; tx->sym; ++tx ) {
            if( !tx->sym->pro ) {
                SetBit( set, tx->sym->idx );
            }
        }
        for( rx = x->redun; rx->pro; ++rx ) {
            for( i = 0; i < wperset; ++i ) {
                if( rx->follow[i] & set[i] ) {
                    resolve( x, work, reduce );
                    goto continu;
                }
                set[i] |= rx->follow[i];
            }
        }
        continu:;
    }
    free( set );
    free( reduce );
}

void lalr1( void )
{
    a_state *x;
    a_look *look, *lk;
    a_shift_action *tx;
    a_reduce_action *rx;
    a_word *lp, *lset, *rp, *rset;

    InitSets( nterm );
    lk = look = CALLOC( nvtrans + nstate, a_look );
    lp = lset = CALLOC( nvtrans*wperset, a_word );
    rp = rset = CALLOC( nredun*wperset, a_word );
    for( x = statelist; x; x = x->next ) {
        x->look = lk;
        for( tx = x->trans; tx->sym; ++tx ) {
            if( tx->sym->pro ) {
                lk->trans = tx;
                lk->follow = lp;
                lp += wperset;
                ++lk;
            }
        }
        ++lk;
        for( rx = x->redun; rx->pro; ++rx ) {
            rx->follow = rp;
            rp += wperset;
        }
    }
    top = stk = CALLOC( nvtrans, a_look * );
    Nullable();
    CalcReads();
    CalcIncludes();
    Lookback();
    if( lk - look != nvtrans + nstate ) {
        puts( "internal error" );
    }
    if( lp - lset != nvtrans * wperset ) {
        puts( "internal error" );
    }
    if( rp - rset != nredun * wperset ) {
        puts( "internal error" );
    }
    free( look );
    free( lset );
    free( stk );
    Conflict();
    nbstate = nstate;
}

void showstates( void )
{
    int i;

    for( i = 0; i < nstate; ++i ) {
        printf( "\n" );
        showstate( statetab[i] );
    }
}

void showstate( 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:\n", x->sidx );
    col = printf( "  parent states:" );
    for( parent = x->parents; parent != NULL; parent = parent->next ) {
        col += printf( " %d", parent->state->sidx );
        if( col > 79 ) {
            printf( "\n" );
            col = 0;
        }
    }
    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' );
}