mkred.c

一个非常好的检索工具

                rule_no = item_table[item_no].rule_number;

                if (slr_bit)  /* SLR table? use Follow */
                {
                    ASSIGN_SET(look_ahead, 0, follow, rules[rule_no].lhs);
                }
                else
                    compute_la(state_no, item_no, look_ahead);

                for ALL_TERMINALS(symbol) /* for all symbols in la set */
                {
                    if (IS_ELEMENT(look_ahead, symbol))
                    {
                        p = Allocate_node();
                        p -> value = item_no;

                        if (action[symbol] == NULL)
                        {
                            symbol_list[symbol] = symbol_root;
                            symbol_root = symbol;
                        }
                        else
                        {
                            /**********************************************/
                            /* Always place the rule with the largest     */
                            /* right-hand side first in the list.         */
                            /**********************************************/
                            n = item_table[action[symbol]
                                                -> value].rule_number;
                            if (RHS_SIZE(n) >= RHS_SIZE(rule_no))
                            {
                                p -> value = action[symbol] -> value;
                                action[symbol] -> value = item_no;
                            }
                        }

                        p -> next = action[symbol];
                        action[symbol] = p;
                    }
                }
            }

        /******************************************************************/
        /* At this stage, we have constructed the ACTION map for STATE_NO.*/
        /* ACTION is a map from each symbol into a set of final items.    */
        /* The rules associated with these items are the rules by which   */
        /* to reduce when the lookahead is the symbol in question.        */
        /* SYMBOL_LIST/SYMBOL_ROOT is a list of the non-empty elements of */
        /* ACTION. If the number of elements in a set ACTION(t), for some */
        /* terminal t, is greater than one or it is not empty and STATE_NO*/
        /* contains a shift action on t then STATE_NO has one or more     */
        /* conflict(s). The procedure RESOLVE_CONFLICTS takes care of     */
        /* resolving the conflicts appropriately and returns an ACTION    */
        /* map where each element has either 0 (if the conflicts were     */
        /* shift-reduce conflicts, the shift is given precedence) or 1    */
        /* element (if the conflicts were reduce-reduce conflicts, only   */
        /* the first element in the ACTION(t) list is returned).          */
        /******************************************************************/
            if (symbol_root != NIL)
            {
                resolve_conflicts(state_no, action,
                                  symbol_list, symbol_root);

                for (symbol = symbol_root;
                     symbol != NIL; symbol = symbol_list[symbol])
                {
                    if (action[symbol] != NULL)
                    {
                        item_no = action[symbol] -> value;
                        rule_count[item_table[item_no].rule_number]++;
                    }
                }
            }
        }

    /*********************************************************************/
    /* We are now ready to compute the size of the reduce map for        */
    /* STATE_NO (reduce_size) and the default rule.                      */
    /* If the state being processed contains only a single complete item */
    /* then the DEFAULT_RULE was previously computed and the list of     */
    /* symbols is empty.                                                 */
    /* NOTE: a REDUCE_ELEMENT will be allocated for all states, even     */
    /* those that have no reductions at all. This will facilitate the    */
    /* Table Compression routines, for they can assume that such an      */
    /* object exists, and can be used for Default values.                */
    /*********************************************************************/
        reduce_size = 0;
        if (symbol_root != NIL)
        {
        /******************************************************************/
        /* Compute REDUCE_SIZE, the number of reductions in the state and */
        /* DEFAULT_RULE: the rule with the highest number of reductions   */
        /* to it.                                                         */
        /******************************************************************/
            n = 0;
            for (q = statset[state_no].complete_items;
                 q != NULL; q = q -> next)
            {
                item_no = q -> value;
                rule_no = item_table[item_no].rule_number;
                symbol = rules[rule_no].lhs;
                reduce_size += rule_count[rule_no];
                if ((rule_count[rule_no] > n) &&
                    (no_shift_on_error_sym[state_no]) &&
                    (symbol != accept_image))
                {
                    n = rule_count[rule_no];
                    default_rule = rule_no;
                }
            }

            /*********************************************************/
            /*   If the removal of single productions is requested   */
            /* and/or parsing tables will not be output, figure out  */
            /* if the level of the default option requested permits  */
            /* default actions, and compute how many reduce actions  */
            /* can be eliminated as a result.                        */
            /*********************************************************/
            if (default_opt == 0)
                default_rule = OMEGA;
            else if (table_opt != OPTIMIZE_TIME &&
                     table_opt != OPTIMIZE_SPACE &&
                     ! single_productions_bit)
            {
                q = statset[state_no].complete_items;
                if (q -> next == NULL)
                {
                    item_no = q -> value;
                    rule_no = item_table[item_no].rule_number;
                    if (default_opt > 2 ||  /* No empty rule defined */
                        (default_opt == 2 && RHS_SIZE(rule_no) != 0))
                        reduce_size -= n;
                    else
                        default_rule = OMEGA;
                }
                else if (default_opt > 3)
                    reduce_size -= n;
            }
            num_reductions += reduce_size;
        }

        /**************************************************************/
        /*   NOTE that the default fields are set for all states,     */
        /* whether or not DEFAULT actions are requested. This is      */
        /* all right since one can always check whether (DEFAULT > 0) */
        /* before using these fields.                                 */
        /**************************************************************/
        red = Allocate_reduce_map(reduce_size);
        reduce[state_no] = red;

        REDUCE_SYMBOL(red, 0)  = DEFAULT_SYMBOL;
        REDUCE_RULE_NO(red, 0) = default_rule;
        for (symbol = symbol_root;
             symbol != NIL; symbol = symbol_list[symbol])
        {
            if (action[symbol] != NULL)
            {
                rule_no = item_table[action[symbol] -> value].rule_number;
                if (rule_no != default_rule ||
                    table_opt == OPTIMIZE_SPACE ||
                    table_opt == OPTIMIZE_TIME  ||
                    single_productions_bit)
                {
                    REDUCE_SYMBOL(red, reduce_size)  = symbol;
                    REDUCE_RULE_NO(red, reduce_size) = rule_no;
                    reduce_size--;
                }

                free_nodes(action[symbol], action[symbol]);
                action[symbol] = NULL;
            }
        }

        /************************************************************/
        /* Reset RULE_COUNT elements used in this state.            */
        /************************************************************/
        for (q = statset[state_no].complete_items;
             q != NULL; q = q -> next)
        {
            rule_no = item_table[q -> value].rule_number;
            rule_count[rule_no] = 0;
        }
    } /* end for ALL_STATES*/

    printf("\n");
    fprintf(syslis,"\n\n");

/****************************************************************/
/* If the automaton required multiple lookahead, construct the  */
/* permanent lookahead states.                                  */
/****************************************************************/
    if (max_la_state > num_states)
        create_lastats();

/****************************************************************/
/* We are now finished with the LALR(k) construction of the     */
/* automaton. Clear all temporary space that was used in that   */
/* process and calculate the maximum lookahead level that was   */
/* needed.                                                      */
/****************************************************************/
    exit_lalrk_process();
    free_conflict_space();

    lalr_level = highest_level;

/****************************************************************/
/* If the removal of single productions is requested, do that.  */
/****************************************************************/
    if (single_productions_bit)
        remove_single_productions();

/****************************************************************/
/* If either more than one lookahead was needed or the removal  */
/* of single productions was requested, the automaton was       */
/* transformed with the addition of new states and new          */
/* transitions. In such a case, we reconstruct the IN_STAT map. */
/****************************************************************/
    if (lalr_level > 1 || single_productions_bit)
    {
        for ALL_STATES(state_no)
        { /* First, clear out the previous map */
            if (in_stat[state_no] != NULL)
            {
                q = in_stat[state_no] -> next; /* point to root */
                free_nodes(q, in_stat[state_no]);
                in_stat[state_no] = NULL;
            }
        }

        build_in_stat(); /* rebuild in_stat map */
    }

/******************************************************************/
/* Print informational messages and free all temporary space that */
/* was used to compute lookahead information.                     */
/******************************************************************/
    if (not_lrk)
    {
        printf("This grammar is not LR(K).\n");
        fprintf(syslis,"This grammar is not LR(K).\n");
    }
    else if (num_rr_conflicts > 0 || num_sr_conflicts > 0)
    {
        if (! slr_bit)
        {
            if (highest_level != INFINITY)
            {
                printf("This grammar is not LALR(%d).\n",
                       highest_level);
                fprintf(syslis,
                        "This grammar is not LALR(%d).\n",
                        highest_level);
            }
            else
            {
                printf("This grammar is not LALR(K).\n");
                fprintf(syslis,"This grammar is not LALR(K).\n");
            }
        }
        else
        {
            printf("This grammar is not SLR(1).\n");
            fprintf(syslis,"This grammar is not SLR(1).\n");
        }
    }
    else
    {
        if (highest_level == 0)
        {
            printf("This grammar is LR(0).\n");
            fprintf(syslis,"This grammar is LR(0).\n");
        }
        else if (slr_bit)
        {
            printf("This grammar is SLR(1).\n");
            fprintf(syslis,"This grammar is SLR(1).\n");
        }
        else
        {
            printf("This grammar is LALR(%d).\n", highest_level);
            fprintf(syslis,
                    "This grammar is LALR(%d).\n", highest_level);
        }
    }

    ffree(rule_count);
    ffree(no_shift_on_error_sym);
    ffree(symbol_list);
    ffree(single_complete_item);
    ffree(action);
    ffree(look_ahead);
    if (conflict_symbols != NULL)
        ffree(conflict_symbols);
    if (read_set != NULL)
        ffree(read_set);
    if (la_index != NULL)
        ffree(la_index);
    if (la_set != NULL)
        ffree(la_set);

    return;
} /* end mkrdcts */