spacetab.c

一个非常好的检索工具

        for (q = new_state_element_reduce_nodes[i];
             q != NULL; tail = q, q = q -> next)
        {
            rule_no = q -> value;
            reduce_size += rule_count[rule_no];
            if ((rule_count[rule_no] > k) && (rule_no != 0)
                && ! shift_on_error_symbol[state_subset_root])
            {
                k = rule_count[rule_no];
                default_rule = rule_no;
            }
        }
        default_saves += k;
        reduce_size -= k;

/*********************************************************************/
/* If STATE_ROOT is not NIL then there are states in the group that  */
/* did not meet the compatibility test.  Throw those states back in  */
/* front of MULTI_ROOT as a group.                                   */
/*********************************************************************/
        if (state_root != NIL)
        {
            top++;
            new_state_element[top].thread = new_state_element[i].thread;
            new_state_element[i].thread = top;
            if (state_root > (int) num_states)
                new_state_element[top].shift_number =
                          lastats[state_root].shift_number;
            else
                new_state_element[top].shift_number =
                                     statset[state_root].shift_number;
            new_state_element_reduce_nodes[top] =
                                     new_state_element_reduce_nodes[i];
            new_state_element[top].image = state_root;
        }
        else
            free_nodes(new_state_element_reduce_nodes[i], tail);

/*********************************************************************/
/* Create Reduce map for the newly created terminal state.           */
/* We may assume that SYMBOL field of defaults is already set to     */
/* the DEFAULT_SYMBOL value.                                         */
/*********************************************************************/
        new_red = Allocate_reduce_map(reduce_size);

        REDUCE_SYMBOL(new_red, 0) = DEFAULT_SYMBOL;
        REDUCE_RULE_NO(new_red, 0) = default_rule;
        for ALL_TERMINALS(symbol)
        {
            if (reduce_action[symbol] != OMEGA)
            {
                if (reduce_action[symbol] != default_rule)
                {
                    REDUCE_SYMBOL(new_red, reduce_size) = symbol;
                    if (reduce_action[symbol] == 0)
                        REDUCE_RULE_NO(new_red, reduce_size) = accept_act;
                    else
                        REDUCE_RULE_NO(new_red, reduce_size) =
                                       reduce_action[symbol];
                    reduce_size--;
                }
            }
        }
        new_state_element[i].reduce = new_red;
        new_state_element[i].image = state_subset_root;
    }

/*********************************************************************/
/* We now process groups of states that have reductions to a single  */
/* rule.  Those states are fully compatible, and the default is the  */
/* rule in question.                                                 */
/* Any of the REDUCE_ELEMENT maps that belongs to a state in the     */
/* group of states being processed may be reused for the new  merged */
/* state.                                                            */
/*********************************************************************/
    for (i = single_root; i != NIL; i = new_state_element[i].thread)
    {
        state_no = new_state_element[i].image;
        q = new_state_element_reduce_nodes[i];
        rule_no = q -> value;
        free_nodes(q, q);
        if (rules[rule_no].lhs == accept_image)
        {
            red = reduce[state_no];
            reduce_size = red.size;

            new_red = Allocate_reduce_map(reduce_size);

            REDUCE_SYMBOL(new_red, 0) = DEFAULT_SYMBOL;
            REDUCE_RULE_NO(new_red, 0) = error_act;

            for (j = 1; j <= reduce_size; j++)
            {
                REDUCE_SYMBOL(new_red, j) = REDUCE_SYMBOL(red, j);
                REDUCE_RULE_NO(new_red, j) = accept_act;
            }
        }
        else
        {
            for ALL_TERMINALS(j)
                reduce_action[j] = OMEGA;

            for (; state_no != NIL; state_no = state_list[state_no])
            {
                if (state_no > (int) num_states)
                    red = lastats[state_no].reduce;
                else
                    red = reduce[state_no];
                for (j = 1; j <= red.size; j++)
                {
                    symbol = REDUCE_SYMBOL(red, j);
                    if (reduce_action[symbol] == OMEGA)
                    {
                        reduce_action[symbol] = rule_no;
                        default_saves++;
                    }
                    else
                       num_reductions_saved++;
                }
            }

            new_red = Allocate_reduce_map(0);

            REDUCE_SYMBOL(new_red, 0) = DEFAULT_SYMBOL;
            REDUCE_RULE_NO(new_red, 0) = rule_no;
        }
        new_state_element[i].reduce = new_red;
    }

/*********************************************************************/
/* Groups of states that have no reductions are also compatible.     */
/* Their default is ERROR_ACTION.                                    */
/*********************************************************************/
    for (i = empty_root; i != NIL; i = new_state_element[i].thread)
    {
        state_no = new_state_element[i].image;
        if (state_no > (int) num_states)
            red = lastats[state_no].reduce;
        else
            red = reduce[state_no];
        REDUCE_SYMBOL(red, 0) = DEFAULT_SYMBOL;
        REDUCE_RULE_NO(red, 0) = error_act;
        new_state_element[i].reduce = red;
    }

    num_terminal_states = top;

    frequency_symbol = Allocate_short_array(num_terminals + 1);
    frequency_count = Allocate_short_array(num_terminals + 1);
    row_size = Allocate_short_array(max_la_state + 1);

    if (shift_default_bit)
        merge_shift_domains();

/*********************************************************************/
/* We now reorder the terminal states based on the number of actions */
/* in them, and remap the terminal symbols if they were not already  */
/* remapped in the previous block for the SHIFT_CHECK vector.        */
/*********************************************************************/
    for ALL_TERMINALS(symbol)
    {
        frequency_symbol[symbol] = symbol;
        frequency_count[symbol] = 0;
    }

    for (i = 1; i <= num_terminal_states; i++)
    {
        ordered_state[i] = i;
        row_size[i] = 0;
        sh = shift[new_state_element[i].shift_number];
        for (j = 1; j <= sh.size; j++)
        {
            symbol = SHIFT_SYMBOL(sh, j);
            if ((! shift_default_bit) ||
                (SHIFT_ACTION(sh, j) != shiftdf[symbol]))
            {
                row_size[i]++;
                frequency_count[symbol]++;
            }
        }

        for (state_no = state_list[new_state_element[i].image];
             state_no != NIL; state_no = state_list[state_no])
        {
            num_shifts_saved += row_size[i];
        }

        /***********************************************/
        /* Note that the Default action is skipped !!! */
        /***********************************************/
        red = new_state_element[i].reduce;
        for (j = 1; j <= red.size; j++)
        {
            symbol = REDUCE_SYMBOL(red, j);
            row_size[i]++;
            frequency_count[symbol]++;
        }
    }
    sprintf(msg_line,
            "Number of unique terminal states: %d",
            num_terminal_states);
    PRNT(msg_line);
    sprintf(msg_line, "Number of Shift actions saved by merging: %d",
                      num_shifts_saved);
    PRNT(msg_line);
    sprintf(msg_line, "Number of Reduce actions saved by merging: %d",
                      num_reductions_saved);
    PRNT(msg_line);
    sprintf(msg_line, "Number of Reduce saved by default: %d",
                      default_saves);
    PRNT(msg_line);

    sortdes(ordered_state, row_size, 1, num_terminal_states,
            num_terminals);

    if (! shift_default_bit)
    {
        sortdes(frequency_symbol, frequency_count, 1, num_terminals,
                num_terminal_states);
        for ALL_TERMINALS(symbol)
            symbol_map[frequency_symbol[symbol]] =  symbol;
        symbol_map[DEFAULT_SYMBOL] = DEFAULT_SYMBOL;
        eoft_image = symbol_map[eoft_image];
        if (error_maps_bit)
        {
            error_image = symbol_map[error_image];
            eolt_image = symbol_map[eolt_image];
        }
        for (i = 1; i <= num_shift_maps; i++)
        {
            sh = shift[i];
            for (j = 1; j <= sh.size; j++)
                SHIFT_SYMBOL(sh, j) = symbol_map[SHIFT_SYMBOL(sh, j)];
        }

        for (state_no = 1; state_no <= num_terminal_states; state_no++)
        {
            red = new_state_element[state_no].reduce;
            for (i = 1; i <= red.size; i++)
                REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
        }

/*********************************************************************/
/* If ERROR_MAPS are requested, we also have to remap the original   */
/* REDUCE maps.                                                      */
/*********************************************************************/
        if (error_maps_bit)
        {
            for ALL_STATES(state_no)
            {
                red = reduce[state_no];
                for (i = 1; i <= red.size; i++)
                    REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
            }
        }
    }
    num_table_entries = num_shifts + num_shift_reduces + num_reductions
                        - num_shifts_saved - num_reductions_saved
                        - default_saves + num_terminal_states;

    ffree(rule_count);
    ffree(reduce_action);
    ffree(row_size);
    ffree(frequency_count);
    ffree(frequency_symbol);
    ffree(shift_on_error_symbol);
    ffree(new_state_element_reduce_nodes);

    return;
}


/*********************************************************************/
/*                           OVERLAP_T_ROWS:                         */
/*********************************************************************/
/* We now compute the starting position for each terminal state just */
/* as we did for the non-terminal states.                            */
/* The starting positions are stored in the vector TERM_STATE_INDEX. */
/*********************************************************************/
static void overlap_t_rows(void)
{
    struct shift_header_type  sh;
    struct reduce_header_type red;

    short *terminal_list;

    int root_symbol,
        symbol,
        i,
        k,
        k_bytes,
        percentage,
        state_no,
        old_size,
        max_indx,
        indx;

    long num_bytes;

    terminal_list = Allocate_short_array(num_terminals + 1);
    term_state_index = Allocate_int_array(max_la_state + 1);

    increment_size = MAX((num_table_entries * increment / 100),
                         (num_terminals + 1));
    old_size = table_size;
    table_size = MIN((num_table_entries + increment_size), MAX_TABLE_SIZE);
    if ((int) table_size > old_size)
    {
        ffree(previous);
        ffree(next);
        next = Allocate_int_array(table_size + 1);
        previous = Allocate_int_array(table_size + 1);
    }
    else
        table_size = old_size;

    first_index = 1;
    previous[first_index] = NIL;
    next[first_index] = first_index + 1;
    for (indx = 2; indx < (int) table_size; indx++)
    {
        next[indx] = indx + 1;
        previous[indx] = indx - 1;
    }
    last_index = table_size;
    previous[last_index] = last_index - 1;
    next[last_index] = NIL;

    max_indx = first_index;

    for (k = 1; k <= num_terminal_states; k++)
    {
        state_no = ordered_state[k];
/*********************************************************************/
/* For the terminal table, we are dealing with two lists, the SHIFT  */
/* list, and the REDUCE list. Those lists are merged together first  */
/* in TERMINAL_LIST.  Since we have to iterate over the list twice,  */
/* this merging makes things easy.                                   */
/*********************************************************************/
        root_symbol = NIL;
        sh = shift[new_state_element[state_no].shift_number];
        for (i = 1; i <= sh.size; i++)
        {
            symbol = SHIFT_SYMBOL(sh, i);
            if (! shift_default_bit ||
                (SHIFT_ACTION(sh, i) != shiftdf[symbol]))
            {
                terminal_list[symbol] = root_symbol;
                root_symbol = symbol;
            }
        }

        red = new_state_element[state_no].reduce;
        for (i = 1; i <= red.size; i++)
        {
            terminal_list[REDUCE_SYMBOL(red, i)] = root_symbol;
            root_symbol = REDUCE_SYMBOL(red, i);
        }