remsp.c

一个非常好的检索工具

            if (SHIFT_ACTION(sh, i) > num_states)
                SHIFT_ACTION(sh, i) += (max_sp_state - num_states);
        }
    }

    for (state_no = num_states + 1; state_no <= max_la_state; state_no++)
    {
        if (lastats[state_no].in_state > num_states)
            lastats[state_no].in_state += (max_sp_state - num_states);
    }

    lastats -= (max_sp_state - num_states);
    max_la_state += (max_sp_state - num_states);
    SHORT_CHECK(max_la_state);

    /******************************************************************/
    /* We now permanently construct all the new SP states.            */
    /******************************************************************/
    for (state = sp_state_root; state != NULL; state = state -> next)
    {
        struct action_element *actionp;

        int default_rule,
            reduce_size;

        state_no = state -> state_number;

        /**************************************************************/
        /* These states are identified as special SP states since     */
        /* they have no kernel items. They also have no goto and      */
        /* shift actions.                                             */
        /**************************************************************/
        statset[state_no].kernel_items = NULL;
        statset[state_no].complete_items = state -> complete_items;
        statset[state_no].go_to.size = 0;
        statset[state_no].go_to.map = NULL;
        statset[state_no].shift_number = 0;

        /**************************************************************/
        /* Count the number of actions defined on each rule in the    */
        /* range of the reduce map.                                   */
        /**************************************************************/
        for (p = state -> rule_root; p != NULL; p = p -> next)
            rule_count[p -> value] = 0;

        for (actionp = state -> action_root;
             actionp != NULL; actionp = actionp -> next)
            rule_count[actionp -> action]++;

        /**************************************************************/
        /* Count the total number of reduce actions in the reduce map */
        /* and calculate the default.                                 */
        /**************************************************************/
        reduce_size = 0;
        sp_rule_count = 0;
        for (p = state -> rule_root; p != NULL; rule_tail = p, p = p -> next)
        {
            reduce_size += rule_count[p -> value];
            if (rule_count[p -> value] > sp_rule_count)
            {
                sp_rule_count = rule_count[p -> value];
                default_rule = p -> value;
            }
        }

        free_nodes(state -> rule_root, rule_tail);

        /**************************************************************/
        /* Construct a permanent reduce map for this SP state.        */
        /**************************************************************/
        num_reductions += reduce_size;

        red = Allocate_reduce_map(reduce_size);
        reduce[state_no] = red;
        REDUCE_SYMBOL(red, 0)  = DEFAULT_SYMBOL;
        REDUCE_RULE_NO(red, 0) = default_rule;

        for (actionp = state -> action_root;
             actionp != NULL; actionp = actionp -> next)
        {
            REDUCE_SYMBOL(red, reduce_size)  = actionp -> symbol;
            REDUCE_RULE_NO(red, reduce_size) = actionp -> action;
            reduce_size--;
        }
    }

    /******************************************************************/
    /* We are now ready to update some old actions and add new ones.  */
    /* This may require that we create new shift maps.  We            */
    /* initialize top to 0 so we can use it as an index to allocate   */
    /* elements from new_shift. We also initialize all the elements   */
    /* of shift_table to NIL. Shift_table will be used as the base of */
    /* a hash table for the new shift maps.                           */
    /******************************************************************/
    top = 0;
    for (i = 0; i <= SHIFT_TABLE_UBOUND; i++)
        shift_table[i] = NIL;

    /******************************************************************/
    /* At most, the shift array contains 1..num_states elements. As,  */
    /* each of these elements might be (theoretically) replaced by a  */
    /* new one, we need to double its size.                           */
    /******************************************************************/
    shift = (struct shift_header_type *)
            realloc(shift,
               2 * (num_states + 1) * sizeof(struct shift_header_type));
    if (shift == NULL)
        nospace(__FILE__, __LINE__);

    /******************************************************************/
    /* For each state with updates or new actions, take appropriate   */
    /* actions.                                                       */
    /******************************************************************/
    for ALL_STATES(state_no)
    {
        BOOLEAN any_shift_action;

        /**************************************************************/
        /* Update reduce actions for final items of single productions*/
        /* that are in non-final states.                              */
        /**************************************************************/
        if (update_action[state_no] != NULL)
        {
            struct update_action_element *p;

            red = reduce[state_no];
            for (i = 1; i <= red.size; i++)
                index_of[REDUCE_SYMBOL(red, i)] = i;

            for (p = update_action[state_no]; p != NULL; p = p -> next)
                REDUCE_RULE_NO(red, index_of[p -> symbol]) = p -> action;
        }

        /**************************************************************/
        /* Update initial automaton with transitions into new SP      */
        /* states.                                                    */
        /**************************************************************/
        if (new_action[state_no] != NULL)
        {
            struct action_element *p;

            /**********************************************************/
            /* Mark the index of each symbol on which there is a      */
            /* transition and copy the shift map into the vector      */
            /* shift_transition.                                      */
            /**********************************************************/
            go_to = statset[state_no].go_to;
            for (i = 1; i <= go_to.size; i++)
                index_of[GOTO_SYMBOL(go_to, i)] = i;

            sh = shift[statset[state_no].shift_number];
            for (i = 1; i <= sh.size; i++)
            {
                index_of[SHIFT_SYMBOL(sh, i)] = i;
                shift_transition[SHIFT_SYMBOL(sh, i)] = SHIFT_ACTION(sh, i);
            }

            /**********************************************************/
            /* Iterate over the new action and update the goto map    */
            /* directly for goto actions but update shift_transition  */
            /* for shift actions. Also, keep track as to whether or   */
            /* not there were any shift transitions at all...         */
            /**********************************************************/
            any_shift_action = FALSE;

            for (p = new_action[state_no]; p != NULL; p = p -> next)
            {
                if (p -> symbol IS_A_NON_TERMINAL)
                {
                    if (GOTO_ACTION(go_to, index_of[p -> symbol]) < 0 &&
                        p -> action > 0)
                    {
                        num_goto_reduces--;
                        num_gotos++;
                    }
                    GOTO_ACTION(go_to, index_of[p -> symbol]) = p -> action;
                }
                else
                {
                    if (SHIFT_ACTION(sh, index_of[p -> symbol]) < 0 &&
                        p -> action > 0)
                    {
                        num_shift_reduces--;
                        num_shifts++;
                    }
                    shift_transition[p -> symbol] = p -> action;

                    any_shift_action = TRUE;
                }
            }

            /**********************************************************/
            /* If there were any shift actions, a new shift map may   */
            /* have been created. Hash shift_transition into the      */
            /* shift hash table.                                      */
            /**********************************************************/
            if (any_shift_action)
            {
                struct shift_header_type sh2;
                unsigned long hash_address;

                hash_address = sh.size;
                for (i = 1; i <= sh.size; i++) /* Compute Hash location */
                    hash_address += SHIFT_SYMBOL(sh, i);
                hash_address %= SHIFT_TABLE_SIZE;

            /**************************************************************/
            /* Search HASH_ADDRESS location for shift map that matches    */
            /* the shift map in shift_transition.  If a match is found    */
            /* we leave the loop prematurely, the search index j is not   */
            /* NIL, and it identifies the shift map in the hash table     */
            /* that matched the shift_transition.                         */
            /**************************************************************/
                for (j = shift_table[hash_address];
                     j != NIL; j = new_shift[j].link)
                {
                    sh2 = shift[new_shift[j].shift_number];
                    if (sh.size == sh2.size)
                    {
                        for (i = 1; i <= sh.size; i++)
                            if (SHIFT_ACTION(sh2, i) !=
                                shift_transition[SHIFT_SYMBOL(sh2, i)])
                                    break;
                        if (i > sh.size)
                            break; /* for (j = shift_table[ ... */
                    }
                }

            /**************************************************************/
            /* If j == NIL, the map at hand had not yet being inserted in */
            /* the table, it is inserted.  Otherwise, we have a match,    */
            /* and STATE_NO is reset to share the shift map previously    */
            /* inserted that matches its shift map.                       */
            /**************************************************************/
                if (j == NIL)
                {
                    sh2 = Allocate_shift_map(sh.size);
                    for (i = 1; i <= sh.size; i++)
                    {
                        symbol = SHIFT_SYMBOL(sh, i);
                        SHIFT_SYMBOL(sh2, i) = symbol;
                        SHIFT_ACTION(sh2, i) = shift_transition[symbol];
                    }
                    num_shift_maps++;
                    shift[num_shift_maps] = sh2;

                    statset[state_no].shift_number = num_shift_maps;

                    top++;
                    new_shift[top].shift_number = num_shift_maps;

                    new_shift[top].link = shift_table[hash_address];
                    shift_table[hash_address] = top;
                }
                else
                {
                    statset[state_no].shift_number =
                           new_shift[j].shift_number;
                }
            }
        }
    }

    /******************************************************************/
    /* Free all nodes used in the construction of the conflict_symbols*/
    /* map as this map is no longer useful and its size is based on   */
    /* the base value of num_states.                                  */
    /******************************************************************/
    for ALL_STATES(state_no)
    {
        if (conflict_symbols[state_no] != NULL)
        {
            p = conflict_symbols[state_no] -> next;
            free_nodes(p, conflict_symbols[state_no]);
        }
    }

    /******************************************************************/
    /* All updates have now been made, adjust the number of regular   */
    /* states to include the new SP states.                           */
    /******************************************************************/
    num_states = max_sp_state;

    /******************************************************************/
    /* Free all temporary space allocated earlier.                    */
    /******************************************************************/
    ffree(sp_rules);
    ffree(stack);
    ffree(index_of);
    ffree(next_rule);
    ffree(rule_list);
    ffree(symbol_list);
    ffree(shift_transition);
    ffree(rule_count);
    ffree(new_shift);
    ffree(look_ahead);
    for ALL_SYMBOLS(i)
    {
        if (sp_action[i] != NULL)
        {
            ffree(sp_action[i]);
        }
    }
    ffree(sp_action);
    ffree(is_conflict_symbol);
    ffree(sp_table);
    ffree(new_action);
    ffree(update_action);

    return;
}