spacetab.c

一个非常好的检索工具

/*********************************************************************/
/* Look for a suitable index where to overlay the state.             */
/*********************************************************************/
        indx = first_index;

look_for_match_in_term_table:
        if (indx == NIL)
            indx = table_size + 1;
        if (indx + num_terminals > (int) table_size)
            reallocate();
        for (symbol = root_symbol;
             symbol != NIL; symbol = terminal_list[symbol])
        {
            if (next[indx + symbol] == OMEGA)
            {
                indx = next[indx];
                goto look_for_match_in_term_table;
            }
        }

/*********************************************************************/
/* INDX marks the starting position for the state, remove all the    */
/* positions that are claimed by terminal actions in the state.      */
/*********************************************************************/
        for (symbol = root_symbol;
             symbol != NIL; symbol = terminal_list[symbol])
        {
            i = indx + symbol;
            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, and     */
/* mark it as taken(CHECK(INDX) = OMEGA)                             */
/* MAX_INDX is updated if required.                                  */
/* TERM_STATE_INDEX(STATE_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] = OMEGA;

        if (indx > max_indx)
            max_indx = indx;
        term_state_index[state_no] = indx;
    }

/*********************************************************************/
/* Update all counts, and report statistics.                         */
/*********************************************************************/
    term_check_size = max_indx + num_terminals;
    for (term_action_size = max_indx + num_terminals;
         term_action_size >= max_indx; term_action_size--)
        if (next[term_action_size] == OMEGA)
            break;

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

    sprintf(msg_line, "Length of Terminal Action Table: %d",
                      term_action_size);
    PRNT(msg_line);

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

    percentage = (((long)term_action_size - 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 = 2 * term_action_size + term_check_size;
        if (num_terminals > 255)
            num_bytes += term_check_size;
    }
    else
        num_bytes = 2 * (term_action_size + term_check_size);

    if (shift_default_bit)
        num_bytes += (2 * num_terminal_states);

    k_bytes = (num_bytes / 1024) + 1;

    sprintf(msg_line,
            "Storage required for Terminal Tables: %ld Bytes, %dK",
            num_bytes, k_bytes);
    PRNT(msg_line);

    total_bytes += num_bytes;

/*********************************************************************/
/* Report total number of storage used.                              */
/*********************************************************************/
    k_bytes = (total_bytes / 1024) + 1;
    sprintf(msg_line,
            "Total storage required for Tables: %ld Bytes, %dK",
            total_bytes, k_bytes);
    PRNT(msg_line);

/*********************************************************************/
/* We now write out the tables to the SYSTAB file.                   */
/*********************************************************************/

    table_size = MAX(check_size, term_check_size);
    table_size = MAX(table_size, shift_check_size);
    table_size = MAX(table_size, action_size);
    table_size = MAX(table_size, term_action_size);

    ffree(terminal_list);
    ffree(next);
    ffree(previous);
}


/*********************************************************************/
/*                         PRINT_TABLES:                             */
/*********************************************************************/
/* We now write out the tables to the SYSTAB file.                   */
/*********************************************************************/
static void print_tables(void)
{
    int *check,
        *action;

    int la_state_offset,
        i,
        j,
        k,
        indx,
        act,
        result_act,
        default_count = 0,
        goto_count = 0,
        goto_reduce_count = 0,
        reduce_count = 0,
        la_shift_count = 0,
        shift_count = 0,
        shift_reduce_count = 0,
        rule_no,
        symbol,
        state_no;

    char *tok;

    long offset;

    check = Allocate_int_array(table_size + 1);
    action = Allocate_int_array(table_size + 1);

    /******************************************************************/
    /* Prepare header card with proper information, and write it out. */
    /******************************************************************/
    offset = error_act;
    if (read_reduce_bit)
        offset += num_rules;
    la_state_offset = offset;

    if (offset > (MAX_TABLE_SIZE + 1))
    {
        sprintf(msg_line, "Table contains entries that are > "
                "%d; Processing stopped.", MAX_TABLE_SIZE + 1);
        PRNTERR(msg_line);
        exit(12);
    }

    output_buffer[0] = 'S';
    output_buffer[1] = (goto_default_bit ? '1' : '0');
    output_buffer[2] = (nt_check_bit ? '1' : '0');
    output_buffer[3] = (read_reduce_bit ? '1' : '0');
    output_buffer[4] = (single_productions_bit ? '1' : '0');
    output_buffer[5] = (shift_default_bit ? '1' : '0');
    output_buffer[6] = (rules[1].lhs == accept_image ? '1' : '0');
                       /* are there more than 1 start symbols? */
    output_buffer[7] = (error_maps_bit ? '1' : '0');
    output_buffer[8] = (byte_bit && last_symbol <= 255 ? '1' : '0');
    output_buffer[9] = escape;

    output_ptr = output_buffer + 10;
    field(num_terminals, 5);
    field(num_non_terminals, 5);
    field(num_rules, 5);
    field(num_states, 5);
    field(check_size, 5);
    field(action_size, 5);
    field(term_check_size, 5);
    field(term_action_size, 5);
    field(state_index[1] + num_rules, 5);
    field(eoft_image, 5);
    field(accept_act, 5);
    field(error_act, 5);
    field(la_state_offset, 5);
    field(lalr_level, 5);
    *output_ptr++ = '\n';

    /*********************************************************/
    /* We write the terminal symbols map.                    */
    /*********************************************************/
    for ALL_TERMINALS(symbol)
    {
        int len;

        tok = RETRIEVE_STRING(symbol);
        if (tok[0] == '\n')  /* we're dealing with special symbol?  */
            tok[0] = escape; /* replace initial marker with escape. */
        len = strlen(tok);
        field(symbol_map[symbol], 4);
        field(len, 4);
        if (len <= 64)
            strcpy(output_ptr, tok);
        else
        {
            memcpy(output_ptr, tok, 64);
            output_ptr += 64;
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            tok += 64;

            for (len = strlen(tok); len > 72; len = strlen(tok))
            {
                memcpy(output_ptr, tok, 72);
                output_ptr += 72;
                *output_ptr++ = '\n';
                BUFFER_CHECK(systab);
                tok += 72;
            }
            memcpy(output_ptr, tok, len);
        }
        output_ptr += len;
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /*********************************************************/
    /* We write the non-terminal symbols map.                */
    /*********************************************************/
    for ALL_NON_TERMINALS(symbol)
    {
        int len;

        tok = RETRIEVE_STRING(symbol);
        if (tok[0] == '\n')  /* we're dealing with special symbol?  */
            tok[0] = escape; /* replace initial marker with escape. */
        len = strlen(tok);
        field(symbol_map[symbol]-num_terminals, 4);
        field(len, 4);
        if (len <= 64)
            strcpy(output_ptr, tok);
        else
        {
            memcpy(output_ptr, tok, 64);
            output_ptr += 64;
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            tok += 64;

            for (len = strlen(tok); len > 72; len = strlen(tok))
            {
                memcpy(output_ptr, tok, 72);
                output_ptr += 72;
                *output_ptr++ = '\n';
                BUFFER_CHECK(systab);
                tok += 72;
            }
            memcpy(output_ptr, tok, len);
        }
        output_ptr += len;
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /*********************************************************/
    /* Initialize TABLES with default actions.               */
    /*********************************************************/
    for (i = 1; i <= check_size; i++)
        check[i] = DEFAULT_SYMBOL;

    for (i = 1; i <= (int) action_size; i++)
        action[i] = error_act;

    /********************************************************************/
    /*    Update the default non-terminal action of each state with the */
    /* appropriate corresponding terminal state starting index.         */
    /********************************************************************/
    for (i = 1; i <= num_terminal_states; i++)
    {
        indx = term_state_index[i];
        state_no = new_state_element[i].image;

    /*********************************************************************/
    /*   Update the action link between the non-terminal and terminal    */
    /* tables.  If error-maps are requested, an indirect linking is made */
    /* as follows:                                                       */
    /*  Each non-terminal row identifies its original state number, and  */
    /* a new vector START_TERMINAL_STATE indexable by state numbers      */
    /* identifies the starting point of each state in the terminal table.*/
    /*********************************************************************/
        if (state_no <= (int) num_states)
        {
            for (; state_no != NIL; state_no = state_list[state_no])
            {
                action[state_index[state_no]] = indx;
            }
        }
        else
        {
            for (; state_no != NIL; state_no = state_list[state_no])
            {
                act = la_state_offset + indx;
                state_index[state_no] = act;
            }
        }
    }

    /*********************************************************************/
    /*  Now update the non-terminal tables with the non-terminal actions.*/
    /*********************************************************************/
    for ALL_STATES(state_no)
    {
        struct goto_header_type go_to;

        indx = state_index[state_no];
        go_to = statset[state_no].go_to;
        for (j = 1; j <= go_to.siz