mkred.c

一个非常好的检索工具

/* $Id: mkred.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
/*
 This software is subject to the terms of the IBM Jikes Compiler
 License Agreement available at the following URL:
 http://www.ibm.com/research/jikes.
 Copyright (C) 1983, 1999, International Business Machines Corporation
 and others.  All Rights Reserved.
 You must accept the terms of that agreement to use this software.
*/
static char hostfile[] = __FILE__;

#include "common.h"
#include "reduce.h"
#include "header.h"

/***********************************************************************/
/* STACK_ROOT is used in la_traverse to construct a stack of symbols.  */
/* The boolean vector SINGLE_COMPLETE_ITEM identifies states whose     */
/* kernel consists of a single final item and other conditions allows  */
/* us to compute default reductions for such states.                   */
/* The vector LA_BASE is used in COMPUTE_READ and TRACE_LALR_PATH to   */
/* identify states whose read sets can be completely computed from     */
/* their kernel items.                                                 */
/***********************************************************************/
static struct node *stack_root = NULL;
static BOOLEAN *single_complete_item;
static int *la_base;

/*****************************************************************************/
/*                                 LPGACCESS:                                */
/*****************************************************************************/
/* Given a STATE_NO and an ITEM_NO, ACCESS computes the set of states where  */
/* the rule from which ITEM_NO is derived was introduced through closure.    */
/*****************************************************************************/
struct node *lpgaccess(int state_no, int item_no)
{
    int i;

    BOOLEAN end_node;

    struct node *access_root,
                *head,
                *tail,
                *q,
                *p,
                *s;

/****************************************************************/
/* Build a list pointed to by ACCESS_ROOT originally consisting */
/* only of STATE_NO.                                            */
/****************************************************************/
    access_root = Allocate_node();
    access_root -> value = state_no;
    access_root -> next = NULL;

    for (i = item_table[item_no].dot; i > 0; i--)/*distance to travel is DOT */
    {
        head = access_root;  /* Save old ACCESS_ROOT */
        access_root = NULL;  /* Initialize ACCESS_ROOT for new list */
        for (p = head; p != NULL; tail = p, p = p -> next)
        {
            /***********************************************************/
            /* Compute set of states with transition into p->value.    */
            /***********************************************************/
            for (end_node = ((s = in_stat[p -> value]) == NULL);
                 ! end_node;
                 end_node = (s == in_stat[p -> value]))
            {
                s = s -> next;

                q = Allocate_node();
                q -> value = s -> value;
                q -> next = access_root;
                access_root = q;
            }
        }

        free_nodes(head, tail);    /* free previous list */
     }

     return(access_root);
}


/*****************************************************************************/
/*                              TRACE_LALR_PATH:                             */
/*****************************************************************************/
/* Given an item of the form: [x .A y], where x and y are arbitrary strings, */
/* and A is a non-terminal, we pretrace the path(s) in the automaton  that   */
/* will be followed in computing the look-ahead set for that item in         */
/* STATE_NO.  A number is assigned to all pairs (S, B), where S is a state,  */
/* and B is a non-terminal, involved in the paths. GOTO_INDX points to the   */
/* GOTO_ELEMENT of (STATE_NO, A).                                            */
/*****************************************************************************/
static void trace_lalr_path(int state_no, int goto_indx)
{
    int i,
        symbol,
        item,
        state;

    struct goto_header_type go_to;

    BOOLEAN contains_empty;

    struct node *p,
                *r,
                *t,
                *w;

/*********************************************************************/
/*  If STATE is a state number we first check to see if its base     */
/* look-ahead set is a special one that does not contain EMPTY and   */
/* has already been assigned a slot that can be reused.              */
/* ((LA_BASE[STATE] != OMEGA) signals this condition.)               */
/* NOTE that look-ahead follow sets are shared only when the maximum */
/* look-ahead level allowed is 1 and single productions will not be  */
/* removed. If either (or both) of these conditions is true, we need */
/* to have a unique slot assigned to each pair [S, A] (where S is a  */
/* state, and A is a non-terminal) in the automaton.                 */
/*********************************************************************/
    go_to = statset[state_no].go_to;
    state = GOTO_ACTION(go_to, goto_indx);
    if (state > 0)
    {
        if (la_base[state] != OMEGA &&
            lalr_level == 1 && (! single_productions_bit))
        {
            GOTO_LAPTR(go_to, goto_indx) = la_base[state];
            return;
        }
        r = statset[state].kernel_items;
    }
    else
        r = adequate_item[-state];

/***********************************************************************/
/* At this point, R points to a list of items which are the successors */
/* of the items needed to initialize the Look-ahead follow sets.  If   */
/* anyone of these items contains EMPTY, we trace the Digraph for other*/
/* look-ahead follow sets that may be needed, and signal this fact     */
/* using the variable CONTAINS_EMPTY.                                  */
/***********************************************************************/
    la_top++;   /* allocate new slot */
    INT_CHECK(la_top);
    GOTO_LAPTR(go_to, goto_indx) = la_top;
    contains_empty = FALSE;

    for (; r != NULL;  r = r -> next)
    {
        item = r -> value - 1;
        if (IS_IN_SET(first, item_table[item].suffix_index, empty))
        {
            contains_empty = TRUE;
            symbol = rules[item_table[item].rule_number].lhs;
            w = lpgaccess(state_no, item);
            for (t = w; t != NULL; p = t, t = t -> next)
            {
                struct goto_header_type go_to;

                go_to = statset[t -> value].go_to;

                for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
                    ;

                if (GOTO_LAPTR(go_to, i) == OMEGA)
                    trace_lalr_path(t -> value, i);
            }

            free_nodes(w, p);
        }
    }

/********************************************************************/
/* If the look-ahead follow set involved does not contain EMPTY, we */
/* mark the state involved (STATE) so that other look-ahead follow  */
/* sets which may need this set may reuse the same one.             */
/* NOTE that if CONTAINS_EMPTY is false, then STATE has to denote a */
/* state number (positive value) and not a rule number (negative).  */
/********************************************************************/
    if (! contains_empty)
        la_base[state] = GOTO_LAPTR(go_to, goto_indx);

    return;
}


/*****************************************************************************/
/*                               COMPUTE_READ:                               */
/*****************************************************************************/
/* COMPUTE_READ computes the number of intermediate look-ahead sets that     */
/* will be needed (in LA_TOP), allocates space for the sets(LA_SET), and    */
/* initializes them.                                                         */
/*  By intermediate look-ahead set, we mean the set of terminals that may    */
/* follow a non-terminal in a given state.                                   */
/*  These sets are initialized to the set of terminals that can immediately  */
/* follow the non-terminal in the state to which it can shift (READ set).    */
/*****************************************************************************/
static void compute_read(void)
{
    int state_no,
        item_no,
        rule_no,
        lhs_symbol,
        state,
        i,
        j,
        la_ptr;

    struct node *p,
                *q,
                *s,
                *v;

    if (lalr_level > 1 || single_productions_bit)
    {
        read_set = (SET_PTR)
                   calloc(num_states + 1,
                          sizeof(BOOLEAN_CELL) * term_set_size);
        if (read_set == NULL)
            nospace(__FILE__, __LINE__);
    }

/************************************************************************/
/*  We traverse all the states and for all complete items that requires */
/* a look-ahead set, we retrace the state digraph (with the help of the */
/* routine TRACE_LALR_PATH) and assign a unique number to all look-ahead*/
/* follow sets that it needs. A look-ahead follow set is a set of       */
/* terminal symbols associated with a pair [S, A], where S is a state,  */
/* and A is a non-terminal:                                             */
/*                                                                      */
/* [S, A] --> Follow-set                                                */
/* Follow-set = {t | t is a terminal that can be shifted on after       */
/*                      execution of a goto action on A in state S}.    */
/*                                                                      */
/* Each follow set is initialized with the set of terminals that can be */
/* shifted on in state S2, where GOTO(S, A) = S2. After initialization  */
/* a follow set F that does not contain the special terminal symbol     */
/* EMPTY is marked with the help of the array LA_BASE, and if the       */
/* highest level of look-ahead allowed is 1, then only one such set is  */
/* allocated, and shared for all pairs (S, B) whose follow set is F.    */
/************************************************************************/
    la_top = 0;
    la_base = (int *) calloc(num_states + 1, sizeof(int));
    if (la_base == NULL)
        nospace(__FILE__, __LINE__);

    for ALL_STATES(i)
        la_base[i] = OMEGA;

    for ALL_STATES(state_no)
    {
        for (p = ((lalr_level <= 1 && single_complete_item[state_no])
                  ? NULL
                  : statset[state_no].complete_items);
             p != NULL; p = p -> next)
        {
            item_no = p -> value;
            rule_no = item_table[item_no].rule_number;
            lhs_symbol = rules[rule_no].lhs;
            if (lhs_symbol != accept_image)
            {
                v = lpgaccess(state_no, item_no);
                for (s = v; s != NULL; q = s, s = s -> next)
                {
                    struct goto_header_type go_to;

                    go_to = statset[s -> value].go_to;
                    for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
                        ;

                    if (GOTO_LAPTR(go_to, i) == OMEGA)
                        trace_lalr_path(s -> value, i);
                }

                free_nodes(v, q);
            }
        }

    /***********************************************************************/
    /*  If the look-ahead level is greater than 1 or single productions    */
    /* actions are to be removed when possible, then we have to compute    */
    /* a Follow-set for all pairs [S, A] in the state automaton. Therefore,*/
    /* we also have to consider Shift-reduce actions as reductions, and    */
    /* trace back to their roots as well.                                  */
    /* Note that this is not necessary for Goto-reduce actions. Since      */
    /* they terminate with a non-terminal, and that non-terminal is        */
    /* followed by the empty string, and we know that it must produce a    */
    /* rule that either ends up in a reduction, a shift-reduce, or another */
    /* goto-reduce. It will therefore be taken care of automatically by    */
    /* transitive closure.                                                 */
    /***********************************************************************/
        if (lalr_level > 1 || single_productions_bit)
        {
            struct shift_header_type sh;
            struct goto_header_type  go_to;

            sh = shift[statset[state_no].shift_number];
            for (j = 1; j <= sh.size; j++)
            {
                if (SHIFT_ACTION(sh, j) < 0)
                {
                    rule_no = - SHIFT_ACTION(sh, j);
                    lhs_symbol = rules[rule_no].lhs;