remsp.c

一个非常好的检索工具

        /* If the two states are compatible merge them into the map   */
        /* sp_action[SYMBOL]. (Note that this effectively destroys    */
        /* the original map.) Also, keep track of whether or not an   */
        /* actual merging action was necessary with the boolean       */
        /* variable no_overwrite.                                     */
        /**************************************************************/
                if (actionp == NULL) /* compatible states */
                {
                    no_overwrite = TRUE;
                    for (actionp = state -> action_root;
                         actionp != NULL;
                         action_tail = actionp, actionp = actionp -> next)
                    {
                        if (sp_action[symbol][actionp -> symbol] == OMEGA)
                        {
                            sp_action[symbol][actionp -> symbol] =
                                                         actionp -> action;
                            no_overwrite = FALSE;
                        }
                    }

            /**********************************************************/
            /* If the item was not previously associated with this    */
            /* state, add it.                                         */
            /**********************************************************/
                    for (p = state -> complete_items;
                         p != NULL; p = p -> next)
                    {
                        if (p -> value == item_no)
                            break;
                    }
                    if (p == NULL)
                    {
                        p = Allocate_node();
                        p -> value = item_no;
                        p -> next = state -> complete_items;
                        state -> complete_items = p;
                    }

            /**********************************************************/
            /* If the two maps are identical (there was no merging),  */
            /* return the state number otherwise, free the old map    */
            /* and break out of the search loop.                      */
            /**********************************************************/
                    if (no_overwrite &&
                        state -> action_count == sp_action_count)
                        return state -> state_number;

                    free_action_elements(state -> action_root, action_tail);

                    break; /* for (state = sp_table[hash_address]; ... */
                }
            }
        }
    }

    /******************************************************************/
    /* If we did not find a compatible state, construct a new one.    */
    /* Add it to the list of state and add it to the hash table.      */
    /******************************************************************/
    if (state == NULL)
    {
        state = (struct sp_state_element *)
                talloc(sizeof(struct sp_state_element));
        if (state == NULL)
            nospace(__FILE__, __LINE__);

        state -> next = sp_state_root;
        sp_state_root = state;

        state -> link = sp_table[hash_address];
        sp_table[hash_address] = state;

        max_sp_state++;
        state -> state_number = max_sp_state;
        state -> rule_count = sp_rule_count;

        p = Allocate_node();
        p -> value = item_no;
        p -> next = NULL;
        state -> complete_items = p;

        state -> rule_root = NULL;
        for (rule_no = rule_head;
             rule_no != NIL; rule_no = next_rule[rule_no])
        {
            p = Allocate_node();
            p -> value = rule_no;
            p -> next = state -> rule_root;
            state -> rule_root = p;
        }
    }

    /******************************************************************/
    /* If the state is new or had its reduce map merged with another  */
    /* map, we update the reduce map here.                            */
    /******************************************************************/
    state -> action_count = sp_action_count;
    state -> action_root = NULL;
    for ALL_TERMINALS(i)
    {
        struct action_element *actionp;

        if (sp_action[symbol][i] != OMEGA)
        {
            actionp = allocate_action_element();
            actionp -> symbol = i;
            actionp -> action = sp_action[symbol][i];

            actionp -> next = state -> action_root;
            state -> action_root = actionp;
        }
    }

    return state -> state_number;
}


/*****************************************************************************/
/*                       REMOVE_SINGLE_PRODUCTIONS:                          */
/*****************************************************************************/
/* This program is invoked to remove as many single production actions as    */
/* possible for a conflict-free automaton.                                   */
/*****************************************************************************/
void remove_single_productions(void)
{
    struct goto_header_type go_to;
    struct shift_header_type sh;
    struct reduce_header_type red;

    struct sp_state_element *state;
    struct node             *p,
                            *rule_tail;

    int rule_head,
        sp_rule_count,
        sp_action_count,
        rule_no,
        state_no,
        symbol,
        lhs_symbol,
        action,
        item_no,
        i,
        j;

    BOOLEAN end_node;

    short *symbol_list,
          *shift_transition,
          *rule_count;

    short shift_table[SHIFT_TABLE_SIZE];

    struct new_shift_element
    {
        short link,
              shift_number;
    } *new_shift;

    /******************************************************************/
    /* Set up a a pool of temporary space.                            */
    /******************************************************************/
    reset_temporary_space();

    /******************************************************************/
    /* Allocate all other necessary temporary objects.                */
    /******************************************************************/
    sp_rules = Allocate_short_array(num_symbols + 1);
    stack = Allocate_short_array(num_symbols + 1);
    index_of = Allocate_short_array(num_symbols + 1);
    next_rule = Allocate_short_array(num_rules + 1);
    rule_list = Allocate_short_array(num_rules + 1);
    symbol_list = Allocate_short_array(num_symbols + 1);
    shift_transition = Allocate_short_array(num_symbols + 1);
    rule_count = Allocate_short_array(num_rules + 1);

    new_shift = (struct new_shift_element *)
                calloc(max_la_state + 1,
                       sizeof(struct new_shift_element));
    if (new_shift == NULL)
        nospace(__FILE__, __LINE__);

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

    sp_action = (short **)
                calloc(num_symbols + 1, sizeof(short *));
    if (sp_action == NULL)
        nospace(__FILE__, __LINE__);

    is_conflict_symbol = (BOOLEAN *)
                         calloc(num_symbols + 1, sizeof(BOOLEAN));
    if (is_conflict_symbol == NULL)
        nospace(__FILE__, __LINE__);

    sp_table = (struct sp_state_element **)
               calloc(STATE_TABLE_SIZE,
                      sizeof(struct sp_state_element *));
    if (sp_table == NULL)
        nospace(__FILE__, __LINE__);

    new_action = (struct action_element **)
                 calloc(num_states + 1, sizeof(struct action_element *));
    if (new_action == NULL)
        nospace(__FILE__, __LINE__);

    update_action = (struct update_action_element **)
                    calloc(num_states + 1,
                           sizeof(struct update_action_element *));
    if (update_action == NULL)
        nospace(__FILE__, __LINE__);

    /******************************************************************/
    /* Initialize all relevant sets and maps to the empty set.        */
    /******************************************************************/
    rule_root = NIL;
    symbol_root = NIL;

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

    for ALL_SYMBOLS(i)
    {
        symbol_list[i] = OMEGA;
        sp_rules[i]    = NIL;
        sp_action[i]   = NULL;
    }

    /******************************************************************/
    /* Construct a set of all symbols used in the right-hand side of  */
    /* single production in symbol_list. The variable symbol_root     */
    /* points to the root of the list. Also, construct a mapping from */
    /* each symbol into the set of single productions of which it is  */
    /* the right-hand side. sp_rules is the base of that map and the  */
    /* relevant sets are stored in the vector next_rule.              */
    /******************************************************************/
    for ALL_RULES(rule_no)
    {
        if (rules[rule_no].sp)
        {
            i = rhs_sym[rules[rule_no].rhs];
            next_rule[rule_no] = sp_rules[i];
            sp_rules[i] = rule_no;
            if (symbol_list[i] == OMEGA)
            {
                symbol_list[i] = symbol_root;
                symbol_root = i;
            }
        }
    }

    /******************************************************************/
    /* Initialize the index_of vector and clear the stack (top).      */
    /* Next, iterate over the list of right-hand side symbols used in */
    /* single productions and invoke compute_sp_map to partially      */
    /* order these symbols (based on the ::= (or ->) relationship) as */
    /* well as their associated rules. (See compute_sp_map for detail)*/
    /* As the list of rules is constructed as a circular list to keep */
    /* it in proper order, it is turned into a linear list here.      */
    /******************************************************************/
    for (i = symbol_root; i != NIL; i = symbol_list[i])
        index_of[i] = OMEGA;
    top = 0;
    for (i = symbol_root; i != NIL; i = symbol_list[i])
    {
        if (index_of[i] == OMEGA)
            compute_sp_map(i);
    }

    if (rule_root != NIL) /* make rule_list non-circular */
    {
        rule_no = rule_root;
        rule_root = rule_list[rule_no];
        rule_list[rule_no] = NIL;
    }

    /******************************************************************/
    /* Clear out all the sets in sp_rules and using the new revised   */
    /* list of SP rules mark the new set of right-hand side symbols.  */
    /* Note this code is important for consistency in case we are     */
    /* removing single productions in an automaton containing         */
    /* conflicts. If an automaton does not contain any conflict, the  */
    /* new set of SP rules is always the same as the initial set.     */
    /******************************************************************/
    for (i = symbol_root; i != NIL; i = symbol_list[i])
        sp_rules[i] = NIL;

    top = 0;
    for (rule_no = rule_root;
         rule_no != NIL; rule_no = rule_list[rule_no])
    {
        top++;

        i = rhs_sym[rules[rule_no].rhs];
        sp_rules[i] = OMEGA;
    }

    /******************************************************************/
    /* Initialize the base of the hash table for the new SP states.   */
    /* Initialize the root pointer for the list of new states.        */
    /* Initialize max_sp_state to num_states. It will be incremented  */
    /* each time a new state is constructed.                          */
    /* Initialize the update_action table.                            */
    /* Initialize the is_conflict_symbol array for non_terminals.     */
    /* Since nonterminals are not used as lookahead symbols, they are */
    /* never involved in conflicts.                                   */
    /* Initialize the set/list (symbol_root, symbol_list) to the      */
    /* empty set/list.                                                */
    /******************************************************************/
    for (i = 0; i < STATE_TABLE_SIZE; i++)
        sp_table[i] = NULL;

    sp_state_root = NULL;