spacetab.c

一个非常好的检索工具

    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)];
        }
    }

    /************************************************************/
    /* Remap the SHIFT_DEFAULT map.                             */
    /************************************************************/
    temp_shift_default = Allocate_short_array(num_terminals + 1);
    for ALL_TERMINALS(symbol)
        temp_shift_default[symbol_map[symbol]] = shiftdf[symbol];
    ffree(shiftdf);
    shiftdf = temp_shift_default;

/*********************************************************************/
/* We now compute the starting position for each Shift check row     */
/* as we did for the terminal states.  The starting positions are    */
/* stored in the vector SHIFT_CHECK_INDEX.                           */
/*********************************************************************/
    sortdes(ordered_shift, row_size, 1, shift_domain_count, num_terminals);

    increment_size = MAX((num_table_entries / 100 * increment),
                         (num_terminals + 1));
    old_table_size = table_size;
    table_size = MIN((num_table_entries + increment_size), MAX_TABLE_SIZE);
    if ((int) table_size > old_table_size)
    {
        ffree(previous);
        ffree(next);
        previous = Allocate_int_array(table_size + 1);
        next = Allocate_int_array(table_size + 1);
    }
    else
        table_size = old_table_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;

/*********************************************************************/
/* Look for a suitable index where to overlay the shift check row.   */
/*********************************************************************/
    for (k = 1; k <= shift_domain_count; k++)
    {
        shift_no = ordered_shift[k];
        sh = shift[real_shift_number[shift_no]];
        indx = first_index;

look_for_match_in_sh_chk_tab:
        if (indx == NIL)
            indx = table_size + 1;
        if (indx + num_terminals > (int) table_size)
            reallocate();
        for (i = 1; i <= sh.size; i++)
        {
            symbol = SHIFT_SYMBOL(sh, i);
            if (next[indx + symbol] == OMEGA)
            {
               indx = next[indx];
               goto look_for_match_in_sh_chk_tab;
            }
        }

/*********************************************************************/
/* INDX marks the starting position for the row, remove all the      */
/* positions that are claimed by that shift check row.               */
/* If a position has the value 0,   then it is the starting position */
/* of a Shift row that was previously processed, and that element    */
/* has already been removed from the list of available positions.    */
/*********************************************************************/
        for (j = 1; j <= sh.size; j++)
        {
            symbol = SHIFT_SYMBOL(sh, j);
            i = indx + symbol;
            if (next[i] != 0)
            {
                if (i == last_index)
                {
                    last_index = previous[last_index];
                    next[last_index] = NIL;
                }
                else
                {
                    next[previous[i]] = next[i];
                    previous[next[i]] = previous[i];
                }
            }
            next[i] = OMEGA;
        }

/*********************************************************************/
/* We now remove the starting position itself from the list without  */
/* marking it as taken, since it can still be used for a shift check.*/
/* MAX_INDX is updated if required.                                  */
/* SHIFT_CHECK_INDEX(SHIFT_NO) is properly set to INDX as the        */
/* starting position of STATE_NO.                                    */
/*********************************************************************/
        if (first_index == last_index)
            first_index = NIL;
        else if (indx == first_index)
        {
            first_index = next[first_index];
            previous[first_index] = NIL;
        }
        else if (indx == last_index)
        {
            last_index = previous[last_index];
            next[last_index] = NIL;
        }
        else
        {
            next[previous[indx]] = next[indx];
            previous[next[indx]] = previous[indx];
        }
        next[indx] = 0;

        if (indx > max_indx)
            max_indx = indx;
        shift_check_index[shift_no] = indx;
    }

/*********************************************************************/
/* Update all counts, and report statistics.                         */
/*********************************************************************/
    shift_check_size = max_indx + num_terminals;

    printf("\n");
    sprintf(msg_line,"Length of Shift Check Table: %d",shift_check_size);
    PRNT(msg_line);

    sprintf(msg_line,"Number of entries in Shift Check Table: %d",
            num_table_entries);
    PRNT(msg_line);

    for (k = shift_check_size; k >= max_indx; k--)
        if (next[k] == OMEGA)
            break;
    percentage = (((long) k - num_table_entries) * 1000)
                 / num_table_entries;

    sprintf(msg_line,"Percentage of increase: %d.%d%%",
            (percentage/10),(percentage % 10));
    PRNT(msg_line);

    if (byte_bit)
    {
        num_bytes = shift_check_size;
        if (num_terminals > 255)
            num_bytes +=shift_check_size;
    }
    else
        num_bytes = 2 * shift_check_size;
    num_bytes += 2 * (num_terminal_states + num_terminals);

    k_bytes = (num_bytes / 1024) + 1;

    sprintf(msg_line,
            "Storage required for Shift Check Table: %ld Bytes, %dK",
            num_bytes, k_bytes);
    PRNT(msg_line);
    total_bytes += num_bytes;

    ffree(ordered_shift);
    ffree(terminal_list);
    ffree(shift_symbols);
    ffree(shift_domain_link);

    return;
}


/*********************************************************************/
/*                         OVERLAY_SIM_T_ROWS:                       */
/*********************************************************************/
/* By now, similar states have been grouped together, and placed in  */
/* one of three linear linked lists headed by the root pointers:     */
/* MULTI_ROOT, SINGLE_ROOT, and EMPTY_ROOT.                          */
/* We iterate over each of these lists and construct new states out  */
/* of these groups of similar states when they are compatible. Then, */
/* we remap the terminal symbols.                                    */
/*********************************************************************/
static void overlay_sim_t_rows(void)
{
    int j,
        k,
        i,
        rule_no,
        state_no,
        symbol,
        default_rule,
        state_subset_root,
        state_set_root,
        state_root,
        reduce_size,
        num_shifts_saved = 0,
        num_reductions_saved = 0,
        default_saves = 0;

    short *rule_count,
          *reduce_action;

    struct shift_header_type  sh;
    struct reduce_header_type red;
    struct reduce_header_type new_red;

    struct node *q,
                *tail;

    rule_count = Allocate_short_array(num_rules + 1);
    reduce_action = Allocate_short_array(num_terminals + 1);

/*********************************************************************/
/*     We first iterate over the groups of similar states in the     */
/* MULTI_ROOT list.  These states have been grouped together,        */
/* because they have the same Shift map, and reduce to the same      */
/* rules, but we must check that they are fully compatible by making */
/* sure that no two states contain reduction to a different rule on  */
/* the same symbol.                                                  */
/*     The idea is to take a state out of the group, and merge with  */
/* it as many other compatible states from the group as possible.    */
/* remaining states from the group that caused clashes are thrown    */
/* back into the MULTI_ROOT list as a new group of states.           */
/*********************************************************************/
    for (i = multi_root; i != NIL; i = new_state_element[i].thread)
    {
        for (q = new_state_element_reduce_nodes[i]; q != NULL; q = q -> next)
        {
            rule_count[q -> value] = 0;
        }

/*********************************************************************/
/* REDUCE_ACTION is used to keep track of reductions that are to be  */
/* applied on terminal symbols as the states are merged.  We pick    */
/* out the first state (STATE_NO) from the group of states involved, */
/* initialize REDUCE_ACTION with its reduce map, and count the number*/
/* of reductions associated with each rule in that state.            */
/*********************************************************************/
        state_no = new_state_element[i].image;
        if (state_no > (int) num_states)
            red = lastats[state_no].reduce;
        else
            red = reduce[state_no];

        for ALL_TERMINALS(j)
            reduce_action[j] = OMEGA;
        for (j = 1; j <= red.size; j++)
        {
            rule_no = REDUCE_RULE_NO(red, j);
            reduce_action[REDUCE_SYMBOL(red, j)] = rule_no;
            rule_count[rule_no]++;
        }

/*********************************************************************/
/* STATE_SET_ROOT is used to traverse the rest of the list that form */
/* the group of states being processed.  STATE_SUBSET_ROOT is used   */
/* to construct the new list that will consist of all states in the  */
/* group that are compatible starting with the initial state.        */
/* STATE_ROOT is used to construct a list of all states in the group */
/* that are not compatible with the initial state.                   */
/*********************************************************************/
        state_set_root = state_list[state_no];
        state_subset_root = state_no;
        state_list[state_subset_root] = NIL;
        state_root = NIL;

        for (state_no = state_set_root;
             state_no != NIL; state_no = state_set_root)
        {
            state_set_root = state_list[state_set_root];

/*********************************************************************/
/* We traverse the reduce map of the state taken out from the group  */
/* and check to see if it is compatible with the subset being        */
/* constructed so far.                                               */
/*********************************************************************/
            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)
                {
                    if (reduce_action[symbol] != REDUCE_RULE_NO(red, j))
                        break;
                }
            }

/*********************************************************************/
/* If J > Q->REDUCE_ELEMENT.N then we traversed the whole reduce map,*/
/* and all the reductions involved are compatible with the new state */
/* being constructed.  The state involved is added to the subset, the*/
/* rule counts are updated, and the REDUCE_ACTIONS map is updated.   */
/*     Otherwise, we add the state involved to the STATE_ROOT list   */
/* which will be thrown back in the MULTI_ROOT list.                 */
/*********************************************************************/
            if (j > red.size)
            {
                state_list[state_no] = state_subset_root;
                state_subset_root = state_no;
                for (j = 1; j <= red.size; j++)
                {
                    symbol = REDUCE_SYMBOL(red, j);
                    if (reduce_action[symbol] == OMEGA)
                    {
                        rule_no = REDUCE_RULE_NO(red, j);
                        if (rules[rule_no].lhs == accept_image)
                            rule_no = 0;
                        reduce_action[symbol] = rule_no;
                        rule_count[rule_no]++;
                    }
                    else
                        num_reductions_saved++;
                }
            }
            else
            {
                state_list[state_no] = state_root;
                state_root = state_no;
            }
        }

/*********************************************************************/
/* Figure out the best default rule candidate, and update            */
/* DEFAULT_SAVES.                                                    */
/* Recall that all accept actions were changed into reduce actions   */
/* by rule 0.                                                        */
/*********************************************************************/
        k = 0;
        reduce_size = 0;
        default_rule = error_act;