remsp.c

一个非常好的检索工具

    max_sp_state = num_states;

    for ALL_STATES(state_no)
        update_action[state_no] = NULL;

    for ALL_NON_TERMINALS(i)
        is_conflict_symbol[i] = FALSE;

    symbol_root = NIL;
    for ALL_SYMBOLS(i)
        symbol_list[i] = OMEGA;

    /******************************************************************/
    /* Traverse all regular states and process the relevant ones.     */
    /******************************************************************/
    for ALL_STATES(state_no)
    {
        struct node *item_ptr;

        new_action[state_no] = NULL;

        go_to = statset[state_no].go_to;
        sh = shift[statset[state_no].shift_number];

        /**************************************************************/
        /* If the state has no goto actions, it is not considered, as */
        /* no single productions could have been introduced in it.    */
        /* Otherwise, we initialize index_of to the empty map and     */
        /* presume that symbol_list is initialized to the empty set.  */
        /**************************************************************/
        if (go_to.size > 0)
        {
            for ALL_SYMBOLS(i)
                index_of[i] = OMEGA;

            for ALL_TERMINALS(i)
                is_conflict_symbol[i] = FALSE;
            for (end_node = ((p = conflict_symbols[state_no]) == NULL);
                 ! end_node; end_node = (p == conflict_symbols[state_no]))
            {
                p = p -> next;
                is_conflict_symbol[p -> value] = TRUE;
            }

            /**********************************************************/
            /* First, use index_of to map each nonterminal symbol on  */
            /* which there is a transition in state_no into its index */
            /* in the goto map of state_no.                           */
            /* Note that this initialization must be executed first   */
            /* before we process the next loop, because index_of is   */
            /* a global variable that is used in the routine          */
            /* compute_sp_action.                                     */
            /**********************************************************/
            for (i = 1; i <= go_to.size; i++)
                index_of[GOTO_SYMBOL(go_to, i)] = i;

            /**********************************************************/
            /* Traverse first the goto map, then the shift map and    */
            /* for each symbol that is the right-hand side of a single*/
            /* production on which there is a transition, compute the */
            /* lookahead set that can follow this transition and add  */
            /* the symbol to the set of candidates (in symbol_list).  */
            /**********************************************************/
            for (i = 1; i <= go_to.size; i++)
            {
                symbol = GOTO_SYMBOL(go_to, i);
                if (IS_SP_RHS(symbol))
                {
                    compute_sp_action(state_no, symbol,
                                      GOTO_ACTION(go_to, i));
                    symbol_list[symbol] = symbol_root;
                    symbol_root = symbol;
                }
            }

            for (i = 1; i <= sh.size; i++)
            {
                symbol = SHIFT_SYMBOL(sh, i);
                index_of[symbol] = i;
                if (IS_SP_RHS(symbol))
                {
                    compute_sp_action(state_no, symbol,
                                      SHIFT_ACTION(sh, i));
                    symbol_list[symbol] = symbol_root;
                    symbol_root = symbol;
                }
            }

            /**********************************************************/
            /* We now traverse the set of single productions in order */
            /* and for each rule that was introduced through closure  */
            /* in the state (there is an action on both the left- and */
            /* right-hand side)...                                    */
            /**********************************************************/
            for (rule_no = rule_root;
                 rule_no != NIL; rule_no = rule_list[rule_no])
            {
                symbol = rhs_sym[rules[rule_no].rhs];
                if (symbol_list[symbol] != OMEGA)
                {
                    lhs_symbol = rules[rule_no].lhs;
                    if (index_of[lhs_symbol] != OMEGA)
                    {
                        if (symbol_list[lhs_symbol] == OMEGA)
                        {
                            compute_sp_action(state_no, lhs_symbol,
                                GOTO_ACTION(go_to, index_of[lhs_symbol]));
                            symbol_list[lhs_symbol] = symbol_root;
                            symbol_root = lhs_symbol;
                        }
                /******************************************************/
                /* Copy all reduce actions defined after the          */
                /* transition on the left-hand side into the          */
                /* corresponding action defined after the transition  */
                /* on the right-hand side. If an action is defined    */
                /* for the left-hand side -                           */
                /*                                                    */
                /*     sp_action[lhs_symbol][i] != OMEGA              */
                /*                                                    */
                /* - but not for the right-hand side -                */
                /*                                                    */
                /*     sp_action[symbol][i] == OMEGA                  */
                /*                                                    */
                /* it is an indication that after the transition on   */
                /* symbol, the action on i is a lookahead shift. In   */
                /* that case, no action is copied.                    */
                /******************************************************/
                        for ALL_TERMINALS(i)
                        {
                            if (sp_action[lhs_symbol][i] != OMEGA &&
                                sp_action[symbol][i] != OMEGA)
                                    sp_action[symbol][i] =
                                        sp_action[lhs_symbol][i];
                        }
                    }
                }
            }

            /**********************************************************/
            /* For each symbol that is the right-hand side of some SP */
            /* for which a reduce map is defined, we either construct */
            /* a new state if the transition is into a final state,   */
            /* or we update the relevant reduce action of the state   */
            /* into which the transition is made, otherwise.          */
            /*                                                        */
            /* When execution of this loop is terminated the set      */
            /* symbol_root/symbol_list is reinitialize to the empty   */
            /* set.                                                   */
            /**********************************************************/
            for (symbol = symbol_root;
                 symbol != NIL;
                 symbol_list[symbol] = OMEGA, symbol = symbol_root)
            {
                symbol_root = symbol_list[symbol];

                if (IS_SP_RHS(symbol))
                {
                    if (symbol IS_A_TERMINAL)
                         action = SHIFT_ACTION(sh, index_of[symbol]);
                    else action = GOTO_ACTION(go_to, index_of[symbol]);

                /******************************************************/
                /* If the transition is a lookahead shift, do nothing.*/
                /* If the action is a goto- or shift-reduce, compute  */
                /* the relevant rule and item involved.               */
                /* Otherwise, the action is a shift or a goto. If the */
                /* transition is into a final state then it is        */
                /* processed as the case of read-reduce above. If     */
                /* not, we invoke compute_update_actions to update    */
                /* the relevant actions.                              */
                /******************************************************/
                    if (action > num_states) /* lookahead shift */
                        rule_no = OMEGA;
                    else if (action < 0) /* read-reduce action */
                    {
                        rule_no = -action;
                        item_no = adequate_item[rule_no] -> value;
                    }
                    else                /* transition action  */
                    {
                        item_ptr = statset[action].kernel_items;
                        item_no = item_ptr -> value;
                        if ((item_ptr -> next == NULL) &&
                            (item_table[item_no].symbol == empty))
                             rule_no = item_table[item_no].rule_number;
                        else
                        {
                            compute_update_actions(state_no, action, symbol);
                            rule_no = OMEGA;
                        }
                    }

                /******************************************************/
                /* If we have a valid SP rule we first construct the  */
                /* set of rules in the range of the reduce map of the */
                /* right-hand side of the rule. If that set contains  */
                /* a single rule then the action on the right-hand    */
                /* side is redefined as the same action on the left-  */
                /* hand side of the rule in question. Otherwise, we   */
                /* create a new state for the final item of the SP    */
                /* rule consisting of the reduce map associated with  */
                /* the right-hand side of the SP rule and the new     */
                /* action on the right-hand side is a transition into */
                /* this new state.                                    */
                /******************************************************/
                    if (rule_no != OMEGA)
                    {
                        if (IS_SP_RULE(rule_no))
                        {
                            struct action_element *p;

                            sp_rule_count = 0;
                            sp_action_count = 0;
                            rule_head = NIL;

                            for ALL_RULES(i)
                                next_rule[i] = OMEGA;

                            for ALL_TERMINALS(i)
                            {
                                rule_no = sp_action[symbol][i];
                                if (rule_no != OMEGA)
                                {
                                    sp_action_count++;
                                    if (next_rule[rule_no] == OMEGA)
                                    {
                                        sp_rule_count++;
                                        next_rule[rule_no] = rule_head;
                                        rule_head = rule_no;
                                    }
                                }
                            }

                            if (sp_rule_count == 1 && IS_SP_RULE(rule_head))
                            {
                                lhs_symbol = rules[rule_head].lhs;
                                action = GOTO_ACTION(go_to,
                                                index_of[lhs_symbol]);
                            }
                            else
                            {
                                action = sp_state_map(rule_head,
                                                      item_no,
                                                      sp_rule_count,
                                                      sp_action_count,
                                                      symbol);
                            }

                            p = allocate_action_element();
                            p -> symbol = symbol;
                            p -> action = action;

                            p -> next = new_action[state_no];
                            new_action[state_no] = p;
                        }
                    }
                }
            }
        }
    } /* for ALL_STATES(state_no) */

    /******************************************************************/
    /* We are now ready to extend all global maps based on states and */
    /* permanently install the new states.                            */
    /******************************************************************/
    statset = (struct statset_type *)
              realloc(statset,
                      (max_sp_state + 1) * sizeof(struct statset_type));
    if (statset == NULL)
        nospace(__FILE__, __LINE__);

    reduce = (struct reduce_header_type *)
             realloc(reduce,
                     (max_sp_state + 1) * sizeof(struct reduce_header_type));
    if (reduce == NULL)
        nospace(__FILE__, __LINE__);

    if (gd_index != NULL) /* see routine PRODUCE */
    {
        gd_index = (short *)
                   realloc(gd_index, (max_sp_state + 2) * sizeof(short));
        if (gd_index == NULL)
            nospace(__FILE__, __LINE__);

        /**************************************************************/
        /* Each element gd_index[i] points to the starting location   */
        /* of a slice in another array. The last element of the slice */
        /* can be computed as (gd_index[i+1] - 1). After extending    */
        /* gd_index, we set each new element to point to the same     */
        /* index as its previous element, making it point to a null   */
        /* slice.                                                     */
        /**************************************************************/
        for (state_no = num_states + 2;
             state_no <= max_sp_state + 1; state_no++)
             gd_index[state_no] = gd_index[state_no - 1];
    }

    in_stat = (struct node **)
              realloc(in_stat,
                      (max_sp_state + 1) * sizeof(struct node *));
    if (in_stat == NULL)
        nospace(__FILE__, __LINE__);

    for (state_no = num_states + 1; state_no <= max_sp_state; state_no++)
         in_stat[state_no] = NULL;

    /******************************************************************/
    /* We now adjust all references to a lookahead state. The idea is */
    /* offset the number associated with each lookahead state by the  */
    /* number of new SP states that were added.                       */
    /******************************************************************/
    for (j = 1; j <= num_shift_maps; j++)
    {
        sh = shift[j];
        for (i = 1; i <= sh.size; i++)
        {