spacetab.c

一个非常好的检索工具

/*                        MERGE_SIMILAR_T_ROWS:                      */
/*********************************************************************/
/* We now try to merge states in the terminal table that are similar.*/
/* Two states S1 and S2 are said to be similar if they contain the   */
/* same shift actions and they reduce to the same set of rules.  In  */
/* addition,  there must not exist a terminal symbol "t" such that:  */
/* REDUCE(S1, t) and REDUCE(S2, t) are defined, and                  */
/* REDUCE(S1, t) ^= REDUCE(S2, t)                                    */
/*********************************************************************/
static void merge_similar_t_rows(void)
{
    struct shift_header_type  sh;
    struct reduce_header_type red;

    short *table;

    int i,
        j,
        rule_no,
        state_no;

   unsigned long hash_address;

   struct node *q,
               *r,
               *tail,
               *reduce_root;

    table = Allocate_short_array(num_shift_maps + 1);

    empty_root = NIL;
    single_root = NIL;
    multi_root = NIL;
    top = 0;

    for (i = 1; i <= (int) max_la_state; i++)
        shift_on_error_symbol[i] = FALSE;

    for (i = 0; i <= num_shift_maps; i++)
        table[i] = NIL;

/*********************************************************************/
/* We now hash all the states into TABLE, based on their shift map   */
/* number.                                                           */
/* The rules in the range of the REDUCE MAP are placed in sorted     */
/* order in a linear linked list headed by REDUCE_ROOT.              */
/*********************************************************************/
    for (state_no = 1; state_no <= (int) max_la_state; state_no++)
    {
        reduce_root = NULL;
        if (state_no > (int) num_states)
            red = lastats[state_no].reduce;
        else
            red = reduce[state_no];

        for (i = 1; i <= red.size; i++)
        {
            rule_no = REDUCE_RULE_NO(red, i);

            for (q = reduce_root; q != NULL; tail = q, q = q -> next)
            { /* Is it or not in REDUCE_ROOT list? */
                if (q -> value == rule_no)
                    goto continue_traverse_reduce_map;
                if (q -> value > rule_no)
                    break;
            }

            r = Allocate_node(); /* Add element to REDUCE_ROOT list */
            r -> value = rule_no;
            if (q == reduce_root)
            {
                r -> next = reduce_root;
                reduce_root = r;
            }
            else
            {
                r -> next = q;
                tail -> next = r;
            }
continue_traverse_reduce_map:;
        }

/*********************************************************************/
/*   We compute the HASH_ADDRESS,  mark if the state has a shift     */
/* action on the ERROR symbol, and search the hash TABLE to see if a */
/* state matching the description is already in there.               */
/*********************************************************************/
        if (state_no > (int) num_states)
            hash_address = lastats[state_no].shift_number;
        else
        {
            if (default_opt == 5)
            {
                sh = shift[statset[state_no].shift_number];
                for (j = 1; (j <= sh.size) &&
                            (! shift_on_error_symbol[state_no]); j++)
                    shift_on_error_symbol[state_no] =
                          (SHIFT_SYMBOL(sh, j) == error_image);
            }
            hash_address = statset[state_no].shift_number;
        }

        for (i = table[hash_address]; i != NIL; i = new_state_element[i].link)
        {
            for (r = reduce_root, q = new_state_element_reduce_nodes[i];
                 (r != NULL) && (q != NULL);
                 r = r -> next, q = q -> next)
            {
                if (r -> value != q -> value)
                    break;
            }

            if (r == q)
                break;
        }

/*********************************************************************/
/* If the state is a new state to be inserted in the table, we now   */
/* do so,  and place it in the proper category based on its reduces, */
/* In any case, the IMAGE field is updated, and so is the relevant   */
/* STATE_LIST element.                                               */
/*                                                                   */
/* If the state contains a shift action on the error symbol and also */
/* contains reduce actions,  we allocate a new element for it and    */
/* place it in the list headed by MULTI_ROOT.  Such states are not   */
/* merged, because we do not take default reductions in them.        */
/*********************************************************************/
        if (shift_on_error_symbol[state_no] && (reduce_root != NULL))
        {
            top++;
            if (i == NIL)
            {
                new_state_element[top].link = table[hash_address];
                table[hash_address] = top;
            }

            new_state_element[top].thread = multi_root;
            multi_root = top;

            new_state_element[top].shift_number = hash_address;
            new_state_element_reduce_nodes[top] = reduce_root;
            state_list[state_no] = NIL;
            new_state_element[top].image = state_no;
        }
        else if (i == NIL)
        {
            top++;
            new_state_element[top].link = table[hash_address];
            table[hash_address] = top;
            if (reduce_root == NULL)
            {
                new_state_element[top].thread = empty_root;
                empty_root = top;
            }
            else if (reduce_root -> next == NULL)
            {
                new_state_element[top].thread = single_root;
                single_root = top;
            }
            else
            {
                new_state_element[top].thread = multi_root;
                multi_root = top;
            }
            new_state_element[top].shift_number = hash_address;
            new_state_element_reduce_nodes[top] = reduce_root;
            state_list[state_no] = NIL;
            new_state_element[top].image = state_no;
        }
        else
        {
            state_list[state_no] = new_state_element[i].image;
            new_state_element[i].image = state_no;

            for (r = reduce_root; r != NULL; tail = r, r = r -> next)
                ;
            if (reduce_root != NULL)
                free_nodes(reduce_root, tail);
        }
    }

    ffree(table);

    return;
}


/*********************************************************************/
/*                       MERGE_SHIFT_DOMAINS:                        */
/*********************************************************************/
/*    If shift-default actions are requested, the shift actions      */
/* associated with each state are factored out of the Action matrix  */
/* and all identical rows are merged.  This merged matrix is used to */
/* create a boolean vector that may be used to confirm whether or not*/
/* there is a shift action in a given state S on a given symbol t.   */
/* If we can determine that there is a shift action on a pair (S, t) */
/* we can apply shift default to the Shift actions just like we did  */
/* for the Goto actions.                                             */
/*********************************************************************/
static void merge_shift_domains(void)
{
    short *shift_domain_link,
          *ordered_shift,
          *terminal_list,
          *temp_shift_default;

    short shift_domain_table[SHIFT_TABLE_SIZE];

    struct shift_header_type  sh;
    struct reduce_header_type red;

    BOOLEAN *shift_symbols;

    unsigned long hash_address;

    int i,
        j,
        indx,
        max_indx,
        k_bytes,
        old_table_size,
        k,
        percentage,
        shift_size,
        shift_no,
        symbol,
        state_no;

    long num_bytes;

/*********************************************************************/
/* Some of the rows in the shift action map have already been merged */
/* by the merging of compatible states... We simply need to increase */
/* the size of the granularity by merging these new terminal states  */
/* based only on their shift actions.                                */
/*                                                                   */
/* The array SHIFT_DOMAIN_TABLE is used as the base for a hash table.*/
/* Each submap represented by a row of the shift action map is hashed*/
/* into this table by summing the terminal symbols in its domain.    */
/* The submap is then entered in the hash table and assigned a unique*/
/* number if such a map was not already placed in the hash table.    */
/* Otherwise, the number assigned to the previous submap is also     */
/* associated with the new submap.                                   */
/*                                                                   */
/* The vector SHIFT_IMAGE is used to keep track of the unique number */
/* associated with each unique shift submap.                         */
/* The vector REAL_SHIFT_NUMBER is the inverse of SHIFT_IMAGE. It is */
/* used to associate each unique number to its shift submap.         */
/* The integer NUM_TABLE_ENTRIES is used to count the number of      */
/* elements in the new merged shift map.                             */
/*                                                                   */
/* The arrays ORDERED_SHIFT and ROW_SIZE are also initialized here.  */
/* They are used to sort the rows of the shift actions map later...  */
/*********************************************************************/
    shift_domain_link = Allocate_short_array(num_terminal_states + 1);
    ordered_shift = Allocate_short_array(num_shift_maps + 1);
    terminal_list = Allocate_short_array(num_terminals + 1);
    shift_image = Allocate_short_array(max_la_state + 1);
    real_shift_number = Allocate_short_array(num_shift_maps + 1);
    shift_symbols = Allocate_boolean_array(num_terminals + 1);

    shift_check_index = Allocate_int_array(num_shift_maps + 1);

    for (i = 0; i <= SHIFT_TABLE_UBOUND; i++)
       shift_domain_table[i] = NIL;

    num_table_entries = 0;
    shift_domain_count = 0;

    for (state_no = 1; state_no <= num_terminal_states; state_no++)
    {
        shift_no = new_state_element[state_no].shift_number;
        for (i = 1; i <=num_terminals; i++)
            shift_symbols[i] = FALSE;

        sh = shift[shift_no];
        shift_size = sh.size;
        hash_address = shift_size;
        for (i = 1; i <= shift_size; i++)
        {
            symbol = SHIFT_SYMBOL(sh, i);
            hash_address += symbol;
            shift_symbols[symbol] = TRUE;
        }

        hash_address %= SHIFT_TABLE_SIZE;

        for (i = shift_domain_table[hash_address];
             i != NIL; i = shift_domain_link[i])
        {
            sh = shift[new_state_element[i].shift_number];
            if (sh.size == shift_size)
            {
                for (j = 1; j <= shift_size; j++)
                    if (! shift_symbols[SHIFT_SYMBOL(sh, j)])
                        break;
                if (j > shift_size)
                {
                    shift_image[state_no] = shift_image[i];
                    goto continu;
                }
            }
        }
        shift_domain_link[state_no] = shift_domain_table[hash_address];
        shift_domain_table[hash_address] = state_no;

        shift_domain_count++;
        shift_image[state_no] = shift_domain_count;

        real_shift_number[shift_domain_count] = shift_no;

        ordered_shift[shift_domain_count] = shift_domain_count;
        row_size[shift_domain_count] = shift_size;
        num_table_entries += shift_size;
continu:;
    }

/*********************************************************************/
/*   Compute the frequencies, and remap the terminal symbols         */
/* accordingly.                                                      */
/*********************************************************************/
    for ALL_TERMINALS(symbol)
    {
        frequency_symbol[symbol] = symbol;
        frequency_count[symbol] = 0;
    }

    for (i = 1; i <= shift_domain_count; i++)
    {
        shift_no = real_shift_number[i];
        sh = shift[shift_no];
        for (j = 1; j <= sh.size; j++)
        {
            symbol = SHIFT_SYMBOL(sh, j);
            frequency_count[symbol]++;
        }
    }

    sortdes(frequency_symbol, frequency_count, 1, num_terminals,
            shift_domain_count);

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