lalr1.c

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

/****************************************************************************
*
*                            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:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include "yacc.h"
#include "alloc.h"

#define INFINITY        32767

static a_look **stk, **top;

static void Reads( a_look *x )
{
    a_shift_action *tx;
    a_look *y;
    int k;

    *top = x;
    x->depth = k = ++top - stk;
    for( tx = x->trans->state->trans; tx->sym; ++tx ) {
        if( !tx->sym->pro ) {
            SetBit( x->follow, tx->sym->idx );
        }
    }
    for( y = x->trans->state->look; y->trans; ++y ) {
        if( y->trans->sym->nullable ) {
            if( y->depth == 0 ) {
                Reads( y );
            }
            if( y->depth < x->depth ) {
                x->depth = y->depth;
            }
            Union( x->follow, y->follow );
        }
    }
    if( x->depth == k ) {
        do {
            (*--top)->depth = INFINITY;
            Assign( (*top)->follow, x->follow );
        } while( *top != x );
    }
}

static void CalcReads( void )
{
    a_state *x;
    a_look *p;

    for( x = statelist; x; x = x->next ) {
        for( p = x->look; p->trans; ++p ) {
            if( !p->depth ) {
                Reads( p );
            }
        }
    }
}

static void Nullable( void )
{
    a_sym *sym;
    a_pro *pro;
    an_item *p;
    bool nullable_added;

    for( sym = symlist; sym; sym = sym->next ) {
        sym->nullable = FALSE;
    }
    do {
        nullable_added = FALSE;
        for( sym = symlist; sym; sym = sym->next ) {
            if( !sym->nullable ) {
                for( pro = sym->pro; pro; pro = pro->next ) {
                    for( p = pro->item; p->p.sym; ++p ) {
                        if( !p->p.sym->nullable ) {
                            goto next_production;
                        }
                    }
                    /* all of the RHS symbols are nullable */
                    /* (the vacuous case means the LHS is nullable) */
                    sym->nullable = TRUE;
                    nullable_added = TRUE;
                    next_production:;
                }
            }
        }
    } while( nullable_added != FALSE );
}

static void Includes( a_look *x )
{
    a_look *y;
    a_link *link;
    int k;

    *top = x;
    x->depth = k = ++top - stk;
    for( link = x->include; link; link = link->next ) {
        y = link->el;
        if( y->depth == 0 ) {
            Includes( y );
        }
        if( y->depth < x->depth ) {
            x->depth = y->depth;
        }
        Union( x->follow, y->follow );
    }
    if( x->depth == k ) {
        do {
            (*--top)->depth = INFINITY;
            Assign( (*top)->follow, x->follow );
        } while( *top != x );
    }
}

static void CalcIncludes( void )
{
    a_state *x, *y;
    a_shift_action *tx;
    a_look *p, *q;
    a_sym *sym;
    a_pro *pro;
    an_item *nullable, *item;
    a_link *free;

    for( x = statelist; x; x = x->next ) {
        for( p = x->look; p->trans; ++p ) {
            p->depth = 0;
            for( pro = p->trans->sym->pro; pro; pro = pro->next ) {
                nullable = pro->item;
                for( item = pro->item; (sym = item->p.sym); ++item ) {
                    if( !sym->nullable ) {
                        nullable = item;
                    }
                }
                y = x;
                for( item = pro->item; (sym = item->p.sym); ++item ) {
                    if( !sym->pro ) {
                        for( tx = y->trans; tx->sym != sym; ++tx );
                        y = tx->state;
                    } else {
                        for( q = y->look; q->trans->sym != sym; ++q );
                        if( item >= nullable ) {
                            free = CALLOC( 1, a_link );
                            free->el = p;
                            free->next = q->include;
                            q->include = free;
                        }
                        y = q->trans->state;
                    }
                }
            }
        }
    }
    for( x = statelist; x; x = x->next ) {
        for( p = x->look; p->trans; ++p ) {
            if( !p->depth ) {
                Includes( p );
            }
        }
    }
}

static void Lookback( void )
{
    a_state *x, *y;
    a_shift_action *tx;
    a_look *p;
    a_reduce_action *rx;
    a_sym *sym;
    a_pro *pro;
    an_item *item;

    for( x = statelist; x; x = x->next ) {
        for( p = x->look; p->trans; ++p ) {
            for( pro = p->trans->sym->pro; pro; pro = pro->next ) {
                y = x;
                for( item = pro->item; (sym = item->p.sym); ++item ) {
                    for( tx = y->trans; tx->sym != sym; ++tx );
                    y = tx->state;
                }
                for( rx = y->redun; rx->pro !=NULL && rx->pro != pro; ++rx );
                Union( rx->follow, p->follow );
            }
        }
    }
}

static a_pro *extract_pro( an_item *p )
{
    an_item *q;

    for( q = p; q->p.sym; ++q );
    return( q[1].p.pro );
}

static void check_for_user_hooks( a_state *state, a_shift_action *saction,
                                  index_t rule )
{
    int min_max_set;
    int all_match;
    unsigned min;
    unsigned max;
    unsigned index;
    a_name name;
    a_pro *pro;
    a_SR_conflict *conflict;
    a_SR_conflict_list *cx;
    a_SR_conflict_list *last;
    a_sym *sym;

    if( state->kersize < 2 ) {
        return;
    }
    if( state->name.item[0] == NULL || !IsState( *state->name.item[0] ) ) {
        sym = saction->sym;
        min_max_set = 0;
        min = UINT_MAX;
        max = 0;
        for( name.item = state->name.item; *name.item; ++name.item ) {
            pro = extract_pro( *name.item );
            if( pro->SR_conflicts == NULL ) {
                /* production doesn't contain any conflicts */
                return;
            }
            for( cx = pro->SR_conflicts; cx != NULL; cx = cx->next ) {
                conflict = cx->conflict;
                if( conflict->sym != sym ) {
                    continue;
                }
                index = conflict->id;
                if( index < min ) {
                    min_max_set = 1;
                    min = index;
                }
                if( index > max ) {
                    min_max_set = 1;
                    max = index;
                }
            }
            if( ! min_max_set ) {
                /* production doesn't contain a matching conflict */
                return;
            }
        }
        for( index = min; index <= max; ++index ) {
            last = NULL;
            all_match = 1;
            for( name.item = state->name.item; *name.item; ++name.item ) {
                pro = extract_pro( *name.item );
                for( cx = pro->SR_conflicts; cx != NULL; cx = cx->next ) {
                    conflict = cx->conflict;
                    if( conflict->id != index ) {