mkred.c

一个非常好的检索工具

                    item_no = adequate_item[rule_no] -> value - 1;
                    v = lpgaccess(state_no, item_no);
                    for (s = v; s != NULL; q = s, s = s -> next)
                    {
                        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);
                }
            }

        /*******************************************************************/
        /* We also need to compute the set of terminal symbols that can be */
        /* read in a state entered via a terminal transition.              */
        /*******************************************************************/
            if (lalr_level > 1 && state_no != 1)
            {
                q = statset[state_no].kernel_items;
                item_no = q -> value - 1;
                if (item_table[item_no].symbol IS_A_TERMINAL)
                {
                    ASSIGN_SET(read_set, state_no, first,
                               item_table[item_no].suffix_index);
                    for (q = q -> next; q != NULL; q = q -> next)
                    {
                        item_no = q -> value - 1;
                        SET_UNION(read_set, state_no, first,
                                  item_table[item_no].suffix_index);
                    }
                }
            }
        }
    }


/*********************************************************************/
/*   We now allocate space for LA_INDEX and LA_SET, and initialize   */
/* all its elements as indicated in reduce.h. The array LA_BASE is   */
/* used to keep track of Follow sets that have been initialized. If  */
/* another set needs to be initialized with a value that has been    */
/* already computed, LA_BASE is used to retrieve the value.          */
/*********************************************************************/
    for ALL_STATES(i)
        la_base[i] = OMEGA;

    la_index = Allocate_short_array(la_top + 1);

    la_set = (SET_PTR)
             calloc(la_top + 1, term_set_size * sizeof(BOOLEAN_CELL));
    if (la_set == NULL)
        nospace(__FILE__, __LINE__);

    for ALL_STATES(state_no)
    {
        struct goto_header_type go_to;

        go_to = statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
        {
            la_ptr = GOTO_LAPTR(go_to, i);
            if (la_ptr != OMEGA)   /* Follow Look-ahead needed */
            {
                state = GOTO_ACTION(go_to, i);
                if (state > 0)
                {
                    if (la_base[state] != OMEGA)  /* already computed */
                    {
                        la_index[la_ptr] = la_index[la_base[state]];
                        ASSIGN_SET(la_set, la_ptr,
                                   la_set, la_base[state]);
                        q = NULL;
                    }
                    else
                    {
                        la_base[state] = la_ptr;
                        q = statset[state].kernel_items;
                    }
                }
                else
                    q = adequate_item[-state];
                if (q != NULL)
                {
                    item_no = q -> value - 1;
                    /* initialize with first item */
                    ASSIGN_SET(la_set, la_ptr,
                               first, item_table[item_no].suffix_index);
                    for (q = q -> next; q != NULL; q = q -> next)
                    {
                        item_no = q -> value - 1;
                        SET_UNION(la_set, la_ptr, first,
                                  item_table[item_no].suffix_index);
                    }
                    if (IS_IN_SET(la_set, la_ptr, empty))
                        la_index[la_ptr] = OMEGA;
                    else
                        la_index[la_ptr] = INFINITY;
                    if (lalr_level > 1 || single_productions_bit)
                    {
                        if(state > 0)
                        {
                            ASSIGN_SET(read_set, state, la_set, la_ptr);
                        }
                    }
                }
            }
        }
    }

    ffree(la_base);

    return;
}


/*****************************************************************************/
/*                                LA_TRAVERSE:                               */
/*****************************************************************************/
/* LA_TRAVERSE takes two major arguments: STATE_NO, and an index (GOTO_INDX) */
/* that points to the GOTO_ELEMENT array in STATE_NO for the non-terminal    */
/* left hand side of an item for which look-ahead is to be computed. The     */
/* look-ahead of an item of the form [x. A y] in state STATE_NO is the set   */
/* of terminals that can appear immediately after A in the context summarized*/
/* by STATE_NO. When a look-ahead set is computed, the result is placed in   */
/* an allocation of LA_ELEMENT pointed to by the LA_PTR field of the         */
/* GOTO_ELEMENT array.                                                       */
/*                                                                           */
/* The same digraph algorithm used in MKFIRST is used for this computation.  */
/*                                                                           */
/*****************************************************************************/
void la_traverse(int state_no, int goto_indx, int *stack_top)
{
    int indx;

    int symbol,
        item,
        state,
        i,
        la_ptr;

    struct goto_header_type go_to;

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

    go_to = statset[state_no].go_to;
    la_ptr =  GOTO_LAPTR(go_to, goto_indx);

    s = Allocate_node();    /* Push LA_PTR down the stack */
    s -> value = la_ptr;
    s -> next = stack_root;
    stack_root = s;

    indx = ++(*stack_top); /* one element was pushed into the stack */
    la_index[la_ptr] = indx;

/**********************************************************************/
/* Compute STATE, action to perform on Goto symbol in question. If    */
/* STATE is positive, it denotes a state to which to shift. If it is  */
/* negative, it is a rule on which to perform a Goto-Reduce.          */
/**********************************************************************/
    state = GOTO_ACTION(go_to, goto_indx);
    if (state > 0)     /* Not a Goto-Reduce action */
        r = statset[state].kernel_items;
    else
        r = adequate_item[-state];

    for (; r != NULL; r = r -> next)
    {  /* loop over items [A -> x LHS_SYMBOL . y] */
        item = r -> value - 1;
        if IS_IN_SET(first, item_table[item].suffix_index, empty)
        {
            symbol = rules[item_table[item].rule_number].lhs;
            w = lpgaccess(state_no, item); /* states where RULE was  */
                                     /* introduced through closure   */
            for (t = w; t != NULL; s = t, t = t -> next)
            {
                struct goto_header_type go_to;

                /**********************************************************/
                /* Search for GOTO action in access-state after reducing  */
                /* RULE to its left hand side (SYMBOL). Q points to the   */
                /* GOTO_ELEMENT in question.                              */
                /**********************************************************/
                go_to = statset[t -> value].go_to;
                for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
                    ;
                if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
                    la_traverse(t -> value, i, stack_top);
                SET_UNION(la_set, la_ptr,
                          la_set, GOTO_LAPTR(go_to, i));
                la_index[la_ptr] = MIN(la_index[la_ptr],
                                       la_index[GOTO_LAPTR(go_to, i)]);
            }

            free_nodes(w, s);
        }
    }

    if (la_index[la_ptr] == indx) /* Top of a SCC */
    {
        s = stack_root;

        for (i = stack_root -> value; i != la_ptr;
             stack_root = stack_root -> next, i = stack_root -> value)
        {
            ASSIGN_SET(la_set, i, la_set, la_ptr);
            la_index[i] = INFINITY;
            (*stack_top)--; /* one element was popped from the stack; */
        }
        la_index[la_ptr] = INFINITY;
        r = stack_root; /* mark last element that is popped and ... */
        stack_root = stack_root -> next; /* ... pop it! */
        (*stack_top)--; /* one element was popped from the stack; */

        free_nodes(s, r);
    }

    return;
}

/*****************************************************************************/
/*                               COMPUTE_LA:                                 */
/*****************************************************************************/
/* COMPUTE_LA takes as argument a state number (STATE_NO), an item number    */
/* (ITEM_NO), and a set (LOOK_AHEAD).  It computes the look-ahead set of     */
/* terminals for the given item in the given state and places the answer in  */
/* the set LOOK_AHEAD.                                                       */
/*****************************************************************************/
void compute_la(int state_no, int item_no, SET_PTR look_ahead)
{
    int lhs_symbol,
        i;

    struct node *r,
                *s,
                *v;

    stack_root = NULL;
    lhs_symbol = rules[item_table[item_no].rule_number].lhs;
    if (lhs_symbol == accept_image)
    {
        ASSIGN_SET(look_ahead, 0,
                   first, item_table[item_no-1].suffix_index);
        return;
    }

    INIT_SET(look_ahead);  /* initialize set */

    v = lpgaccess(state_no, item_no);
    for (s = v; s != NULL; r = s, s = s -> next)
    {
        struct  goto_header_type go_to;

        /*****************************************************************/
        /* Search for GOTO action in Access-State after reducing rule to */
        /* its left hand side(LHS_SYMBOL). Q points to the state.        */
        /*****************************************************************/
        go_to = statset[s -> value].go_to;
        for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
            ;

        /***********************************************************/
        /* If look-ahead after left hand side is not yet computed, */
        /* LA_TRAVERSE the graph to compute it.                    */
        /***********************************************************/
        if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
        {
            int stack_top = 0;
            la_traverse(s -> value, i, &stack_top);
        }
        SET_UNION(look_ahead, 0, la_set, GOTO_LAPTR(go_to, i));
    }

    RESET_BIT(look_ahead, empty); /* empty not valid look-ahead */
    free_nodes(v, r);

    return;
}


/**********************************************************************/
/*                            BUILD_IN_STAT:                          */
/**********************************************************************/
/* We construct the IN_STAT map which is the inverse of the transition*/
/* map formed by GOTO and SHIFT maps.                                 */
/* This map is implemented as a table of pointers that can be indexed */
/* by the states to a circular list of integers representing other    */
/* states that contain transitions to the state in question.          */
/**********************************************************************/
static void build_in_stat(void)
{
    struct shift_header_type sh;
    struct goto_header_type  go_to;
    struct node *q;
    int state_no,
        i,
        n;