mkred.c

一个非常好的检索工具

    for ALL_STATES(state_no)
    {
        n = statset[state_no].shift_number;
        sh = shift[n];
        for (i = 1; i <= sh.size; ++i)
        {
            n = SHIFT_ACTION(sh, i);
            if (n > 0 && n <= num_states) /* A shift action? */
            {
                q = Allocate_node();
                q -> value = state_no;
                if (in_stat[n] == NULL)
                    q -> next = q;
                else
                {
                    q -> next = in_stat[n] -> next;
                    in_stat[n] -> next = q;
                }
                in_stat[n] = q;
            }
        }

        go_to = statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
        {
            n = GOTO_ACTION(go_to, i);
            if (n > 0) /* A goto action */
            {
                q = Allocate_node();
                q -> value = state_no;
                if (in_stat[n] == NULL)
                    q -> next = q;
                else
                {
                    q -> next = in_stat[n] -> next;
                    in_stat[n] -> next = q;
                }
                in_stat[n] = q;
            }
        }
    }

    return;
}


/*****************************************************************************/
/*                                MKRDCTS:                                   */
/*****************************************************************************/
/* MKRDCTS constructs the REDUCE map and detects conflicts in the grammar.   */
/* When constructing an LALR parser, the subroutine COMPUTE_LA is invoked to */
/* compute the lalr look-ahead sets.  For an SLR parser, the FOLLOW map      */
/* computed earlier in the procedure MKFIRST is used.                        */
/*                                                                           */
/* For a complete description of the lookahead algorithm used in this        */
/* program, see Charles, PhD thesis, NYU 1991.                               */
/*****************************************************************************/
void mkrdcts(void)
{
    short *symbol_list,
          *rule_count;

    int symbol_root,
        reduce_size,
        state_no,
        item_no,
        rule_no,
        symbol,
        default_rule,
        i,
        n;

    struct node **action;

    struct node *p,
                *q,
                *r,
                *item_ptr;

    BOOLEAN *no_shift_on_error_sym;
    SET_PTR look_ahead;

/**********************************************************************/
/* Set up a pool of temporary space. If LALR(k), k > 1 is requested,  */
/* INIT_LALRK_PROCESS sets up the necessary environment for the       */
/* computation of multiple lookahead.                                 */
/**********************************************************************/
    reset_temporary_space();

    init_lalrk_process();

/**********************************************************************/
/* IN_STAT is used to construct a reverse transition map. See         */
/* BUILD_IN_STAT for more detail.                                     */
/*                                                                    */
/* RULE_COUNT is an array used to count the number of reductions on   */
/* particular rules within a given state.                             */
/*                                                                    */
/* NO_SHIFT_ON_ERROR_SYM is a vector used to identify states that     */
/* contain shift actions on the %ERROR symbol.  Such states are marked*/
/* only when DEFAULT_OPT is 5.                                        */
/*                                                                    */
/* SYMBOL_LIST is used to construct temporary lists of terminals on   */
/* which reductions are defined.                                      */
/*                                                                    */
/* When default actions are requested, the vector SINGLE_COMPLETE_ITEM*/
/* is used to identify states that contain exactly one final item.    */
/* NOTE that when the READ_REDUCE options is turned on, the LR(0)     */
/* automaton constructed contains no such state.                      */
/*                                                                    */
/* ACTION is an array that is used as the base for a mapping from     */
/* each terminal symbol into a list of actions that can be executed   */
/* on that symbol in a given state.                                   */
/*                                                                    */
/* LOOK_AHEAD is used to compute lookahead sets.                      */
/**********************************************************************/
    in_stat = (struct node **)
              calloc(num_states + 1, sizeof(struct node *));
    if (in_stat == NULL)
        nospace(__FILE__, __LINE__);

    rule_count = Allocate_short_array(num_rules + 1);
    no_shift_on_error_sym = Allocate_boolean_array(num_states + 1);
    symbol_list = Allocate_short_array(num_terminals + 1);
    single_complete_item = Allocate_boolean_array(num_states + 1);

    action = (struct node **)
             calloc(num_terminals + 1, sizeof(struct node *));
    if (action == NULL)
        nospace(__FILE__, __LINE__);

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

    /****************************************************************/
    /* If we will be removing single productions, we need to keep   */
    /* track of all (state, symbol) pairs on which a conflict is    */
    /* detected. The structure conflict_symbols is used as a base   */
    /* to construct that map. See ADD_CONFLICT_SYMBOL in resolve.c. */
    /* NOTE that this allocation automatically initialized all      */
    /* elements of the conflict_symbols array to NULL.              */
    /****************************************************************/
    if (single_productions_bit)
    {
        conflict_symbols = (struct node **)
                           calloc(num_states + 1, sizeof(struct node *));
        if (conflict_symbols == NULL)
            nospace(__FILE__, __LINE__);
    }

    /**********************************************************************/
    /* First, construct the IN_STAT map. Next, iterate over the states to */
    /* construct two boolean vectors.  One indicates whether there is a   */
    /* shift action on the ERROR symbol when the DEFAULT_OPT is 5.  The   */
    /* other indicates whether it is all right to take default action in  */
    /* states containing exactly one final item.                          */
    /*                                                                    */
    /* We also check whether the grammar is LR(0). I.e., whether it needs */
    /* any look-ahead at all.                                             */
    /**********************************************************************/
    build_in_stat();

    for ALL_STATES(state_no)
    {
        struct shift_header_type sh;

        no_shift_on_error_sym[state_no] = TRUE;

        if (default_opt == 5)
        {
            n = statset[state_no].shift_number;
            sh = shift[n];
            for (i = 1; i <= sh.size; ++i)
            {
                if (SHIFT_SYMBOL(sh, i) == error_image)
                    no_shift_on_error_sym[state_no] = FALSE;
            }
        }

    /**********************************************************************/
    /*   Compute whether this state is a final state.  I.e., a state that */
    /* contains only a single complete item. If so, mark it as a default  */
    /* state. Note that if the READ-REDUCE option is used, the automaton  */
    /* will not contain such states. Also, states are marked only when    */
    /* default actions are requested.                                     */
    /**********************************************************************/
        item_ptr = statset[state_no].kernel_items;
        item_no = item_ptr -> value;
        single_complete_item[state_no] =
               ((! read_reduce_bit) &&
                (! single_productions_bit) &&
                (table_opt != OPTIMIZE_TIME) &&
                (table_opt != OPTIMIZE_SPACE) &&
                (default_opt > 0) &&
                (item_ptr  -> next == NULL) &&
                (item_table[item_no].symbol == empty));

    /**********************************************************************/
    /* If a state has a complete item, and more than one kernel item      */
    /* which is different from the complete item, then this state         */
    /* requires look-ahead for the complete item.                         */
    /**********************************************************************/
        if (highest_level == 0)
        {
            r = statset[state_no].complete_items;
            if (r != NULL)
            {
                if (item_ptr -> next != NULL ||
                    item_ptr -> value != r -> value)
                    highest_level = 1;
            }
        }
    }

    /****************************************************************/
    /* We call COMPUTE_READ to perform the following tasks:         */
    /* 1) Count how many elements are needed in LA_ELEMENT: LA_TOP  */
    /* 2) Allocate space for and initialize LA_SET and LA_INDEX     */
    /****************************************************************/
    if (! slr_bit)
        compute_read();

    /****************************************************************/
    /* Allocate space for REDUCE which will be used to map each     */
    /* into its reduce map. We also initialize RULE_COUNT which     */
    /* will be used to count the number of reduce actions on each   */
    /* rule with in a given state.                                  */
    /****************************************************************/
    reduce = (struct reduce_header_type *)
             calloc(num_states + 1, sizeof(struct reduce_header_type));
    if (reduce == NULL)
        nospace(__FILE__, __LINE__);

    for ALL_RULES(i)
        rule_count[i] = 0;

    /****************************************************************/
    /* We are now ready to construct the reduce map. First, we      */
    /* initialize MAX_LA_STATE to NUM_STATES. If no lookahead       */
    /* state is added (the grammar is LALR(1)) this value will not  */
    /* change. Otherwise, MAX_LA_STATE is incremented by 1 for each */
    /* lookahead state added.                                       */
    /****************************************************************/
    max_la_state = num_states;

    /****************************************************************/
    /* We iterate over the states, compute the lookahead sets,      */
    /* resolve conflicts (if multiple lookahead is requested) and/or*/
    /* report the conflicts if requested...                         */
    /****************************************************************/
    for ALL_STATES(state_no)
    {
        struct reduce_header_type red;

        default_rule = OMEGA;
        symbol_root = NIL;

        item_ptr = statset[state_no].complete_items;
        if (item_ptr != NULL)
        {
    /**********************************************************************/
    /* Check if it is possible to take default reduction. The DEFAULT_OPT */
    /* parameter indicates what kind of default options are requested.    */
    /* The various values it can have are:                                */
    /*                                                                    */
    /*    a)   0 => no default reduction.                                 */
    /*    b)   1 => default reduction only on adequate states. I.e.,      */
    /*              states with only one complete item in their kernel.   */
    /*    c)   2 => Default on all states that contain exactly one        */
    /*              complete item not derived from an empty rule.         */
    /*    d)   3 => Default on all states that contain exactly one        */
    /*              complete item including items from empty rules.       */
    /*    e)   4 => Default reduction on all states that contain exactly  */
    /*              one item. If a state contains more than one item we   */
    /*              take Default on the item that generated the most      */
    /*              reductions. If there is a tie, one is selected at     */
    /*              random.                                               */
    /*    f)   5 => Same as 4 except that no default actions are computed */
    /*              for states that contain a shift action on the ERROR   */
    /*              symbol.                                               */
    /*                                                                    */
    /*  In the code below, we first check for category 3.  If it is not   */
    /* satisfied, then we check for the others. Note that in any case,    */
    /* default reductions are never taken on the ACCEPT rule.             */
    /*                                                                    */
    /**********************************************************************/
            item_no = item_ptr -> value;
            rule_no = item_table[item_no].rule_number;
            symbol = rules[rule_no].lhs;
            if (single_complete_item[state_no] && symbol != accept_image)
            {
                default_rule = rule_no;
                item_ptr = NULL; /* No need to check for conflicts */
            }

        /******************************************************************/
        /* Iterate over all complete items in the state, build action     */
        /* map, and check for conflicts.                                  */
        /******************************************************************/
            for (; item_ptr != NULL; item_ptr = item_ptr -> next)
            { /* for all complete items */
                item_no = item_ptr -> value;