tabutil.c

一个非常好的检索工具

        non_terminal_ubound;

    long num_bytes;

    char tok[SYMBOL_SIZE + 1];

    terminal_ubound = (table_opt == OPTIMIZE_TIME
                                 ?  num_symbols
                                 :  num_terminals);

    non_terminal_ubound = (table_opt == OPTIMIZE_TIME
                                     ?  num_symbols
                                     :  num_non_terminals);

    symbol_root = Allocate_short_array(num_symbols + 1);
    symbol_count = Allocate_short_array(num_symbols + 1);
    state_start = Allocate_short_array(num_states + 2);
    state_stack = Allocate_short_array(num_states + 1);
    term_list = Allocate_short_array(num_symbols + 1);

    PRNT("\nError maps storage:");

/*********************************************************************/
/* The FOLLOW map is written out as two vectors where the first      */
/* vector indexed by a Symbol gives the starting location in the     */
/* second vector where the elements of the follow set of that symbol */
/* starts.  Note that since the terminal and non-terminal symbols    */
/* have been intermixed, the FOLLOW map is written out with the      */
/* complete set of symbols as its domain even though it is only      */
/* defined on non-terminals.                                         */
/*                                                                   */
/* We now compute and write the starting location for each symbol.   */
/* The offset for the first symbol is 1,  and hence does not         */
/* have to be computed.  However,  we compute an extra offset to     */
/* indicate the extent of the last symbol.                           */
/*********************************************************************/
    for (symbol = 1; symbol <= non_terminal_ubound; symbol++)
    {
        symbol_count[symbol] = 0;
        symbol_root[symbol] = OMEGA;
    }

    for ALL_NON_TERMINALS(lhs_symbol)
    {
        if (table_opt == OPTIMIZE_TIME)
            symbol = symbol_map[lhs_symbol];
        else
            symbol = symbol_map[lhs_symbol] - num_terminals;
        symbol_root[symbol] = lhs_symbol;
        for ALL_TERMINALS(i)
        {
            if IS_IN_SET(follow, (lhs_symbol + 1), (i + 1))
               symbol_count[symbol]++;
        }
    }

    offset = 1;
    k = 1;
    field(offset, 6);     /* Offset of the first state */
    for (symbol = 1; symbol <= non_terminal_ubound; symbol++)
    {
        offset += symbol_count[symbol];
        field(offset, 6);
        k++;
        if (k == 12)
        {
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            k = 0;
        }
    }
    if (k != 0)
    {
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /***************************************************************/
    /*  We now write the elements in the range of the FOLLOW map.  */
    /***************************************************************/
    k = 0;
    for (symbol = 1; symbol <= non_terminal_ubound; symbol++)
    {
        lhs_symbol = symbol_root[symbol];
        if (lhs_symbol != OMEGA)
        {
            for ALL_TERMINALS(i)
            {
                if IS_IN_SET(follow, (lhs_symbol + 1), (i + 1))
                {
                    field(symbol_map[i], 4);
                    k++;
                    if (k == 18)
                    {
                        *output_ptr++ = '\n';
                        BUFFER_CHECK(systab);
                        k = 0;
                    }
                }
            }
        }
    }
    if (k != 0)
    {
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /*****************************************************************/
    /* Compute and list amount of space required for the Follow map. */
    /*****************************************************************/
    if (table_opt == OPTIMIZE_TIME)
    {
        num_bytes = 2 * (num_symbols + offset);
        if (byte_bit)
        {
            if (last_non_terminal <= 255)
                num_bytes = num_bytes - offset + 1;
        }
    }
    else
    {
        num_bytes = 2 * (num_non_terminals + offset);
        if (byte_bit)
        {
            if (num_terminals <= 255)
                num_bytes = num_bytes - offset + 1;
        }
    }
    sprintf(msg_line,
            "    Storage required for FOLLOW map: %d Bytes",
            num_bytes);
    PRNT(msg_line);

    /**************************************************************/
    /* We now write out the states in sorted order: SORTED_STATE. */
    /**************************************************************/
    k = 0;
    for ALL_STATES(i)
    {
        field(ordered_state[i], 6);
        k++;
        if (k == 12)
        {
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            k = 0;
        }
    }
    if (k != 0)
    {
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /*****************************************************************/
    /* Compute and list space required for SORTED_STATE map.         */
    /*****************************************************************/
    num_bytes = 2 * num_states;
    sprintf(msg_line,
            "    Storage required for SORTED_STATE map: %d Bytes",
            num_bytes);
    PRNT(msg_line);

    /********************************************************************/
    /* We now write a vector parallel to SORTED_STATE that gives us the */
    /* original number associated with the state: ORIGINAL_STATE.       */
    /********************************************************************/
    k = 0;
    for (i = 1; i <= (int) num_states; i++)
    {
        field(state_list[i], 6);
        k++;
        if (k == 12)
        {
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            k = 0;
        }
    }
    if (k != 0)
    {
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /*****************************************************************/
    /* Compute and list space required for ORIGINAL_STATE map.       */
    /*****************************************************************/
    num_bytes = 2 * num_states;
    sprintf(msg_line,
            "    Storage required for ORIGINAL_STATE map: %d Bytes",
            num_bytes);
    PRNT(msg_line);

    /********************************************************************/
    /* We now construct a bit map for the set of terminal symbols that  */
    /* may appear in each state. Then, we invoke PARTSET to apply the   */
    /* Partition Heuristic and print it.                                */
    /********************************************************************/
    as_size = Allocate_short_array(num_states + 1);

    if (table_opt == OPTIMIZE_TIME)
    {
        original = Allocate_short_array(num_symbols + 1);

        /*************************************************************/
        /* In a compressed TIME table, the terminal and non-terminal */
        /* symbols are mixed together when they are remapped.        */
        /* We shall now recover the original number associated with  */
        /* each terminal symbol since it lies very nicely in the     */
        /* range 1..NUM_TERMINALS.  This will save a considerable    */
        /* amount of space in the bit_string representation of sets  */
        /* as well as time when operations are performed on those    */
        /* bit-strings.                                              */
        /*************************************************************/
        for ALL_TERMINALS(symbol)
            original[symbol_map[symbol]] = symbol;
    }

/***********************************************************************/
/* NOTE that the arrays ACTION_SYMBOLS and NACTION_SYMBOLS are global  */
/* variables that are allocated in the procedure PROCESS_TABLES by     */
/* calloc which automatically initializes them to 0.                   */
/***********************************************************************/
    for ALL_STATES(state_no)
    {
        struct shift_header_type  sh;
        struct reduce_header_type red;

        sh = shift[statset[state_no].shift_number];
        as_size[state_no] = sh.size;
        for (i = 1; i <= sh.size; i++)
        {
            if (table_opt == OPTIMIZE_TIME)
                symbol = original[SHIFT_SYMBOL(sh, i)];
            else
                symbol = SHIFT_SYMBOL(sh, i);
            SET_BIT_IN(action_symbols, state_no, symbol);
        }

        red = reduce[state_no];
        as_size[state_no] += red.size;
        for (i = 1; i <= red.size; i++)
        {
            if (table_opt == OPTIMIZE_TIME)
                symbol = original[REDUCE_SYMBOL(red, i)];
            else
                symbol = REDUCE_SYMBOL(red, i);
            SET_BIT_IN(action_symbols, state_no, symbol);
        }
    }

    partset(action_symbols, as_size, state_list, state_start,
            state_stack, num_terminals);

    ffree(action_symbols);

    /*********************************************************************/
    /* We now write the starting location for each state in the domain   */
    /* of the ACTION_SYMBOL map.                                         */
    /* The starting locations are contained in the STATE_START vector.   */
    /*********************************************************************/
    offset = state_start[num_states + 1];
    k = 0;
    for ALL_STATES(i)
    {
        field(ABS(state_start[state_list[i]]), 6);
        k++;
        if (k == 12)
        {
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            k = 0;
        }
    }
    field(offset, 6);
    k++;
    *output_ptr++ = '\n';
    BUFFER_CHECK(systab);

    /**************************************************************/
    /* Compute and write out the range of the ACTION_SYMBOLS map. */
    /**************************************************************/
    action_symbols_range = Allocate_short_array(offset);

    compute_action_symbols_range(state_start, state_stack,
                                 state_list, action_symbols_range);

    k = 0;
    for (i = 0; i < (offset - 1); i++)
    {
        field(action_symbols_range[i], 4);
        k++;
        if (k == 18)
        {
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            k = 0;
        }
    }
    if (k != 0)
    {
        *output_ptr++ = '\n';
        BUFFER_CHECK(systab);
    }

    /*************************************************************/
    /* Compute and list space required for ACTION_SYMBOLS map.   */
    /*************************************************************/
    num_bytes = 2 * (num_states + offset);
    if (byte_bit)
    {
        if (offset <= 255)
            num_bytes -= (num_states + 1);
        if (((table_opt == OPTIMIZE_TIME) && (last_terminal <= 255)) ||
            ((table_opt != OPTIMIZE_TIME) && (num_terminals <= 255)))
            num_bytes -= (offset - 1);
    }
    sprintf(msg_line,
            "    Storage required for ACTION_SYMBOLS map: "
            "%ld Bytes", num_bytes);
    PRNT(msg_line);

    ffree(action_symbols_range);

/***********************************************************************/
/* We now repeat the same process for the domain of the GOTO table.    */
/***********************************************************************/
    for ALL_STATES(state_no)
    {
        as_size[state_no] = gd_index[state_no + 1] - gd_index[state_no];
        for (i = gd_index[state_no]; i < gd_index[state_no + 1]; i++)
        {
            symbol = gd_range[i] - num_terminals;
            NTSET_BIT_IN(naction_symbols, state_no, symbol);
        }
    }

    partset(naction_symbols, as_size, state_list, state_start,
            state_stack, num_non_terminals);

    ffree(as_size);
    ffree(naction_symbols);

    for (i = 1; i <= gotodom_size; i++)  /* Remap non-terminals */
    {
        if (table_opt == OPTIMIZE_TIME)
            gd_range[i] = symbol_map[gd_range[i]];
        else
            gd_range[i] = symbol_map[gd_range[i]] - num_terminals;
    }

    /*****************************************************************/
    /* We now write the starting location for each state in the      */
    /* domain of the NACTION_SYMBOLS map. The starting locations are */
    /* contained in the STATE_START vector.                          */
    /*****************************************************************/
    offset = state_start[num_states + 1];

    k = 0;
    for ALL_STATES(i)
    {
        field(ABS(state_start[state_list[i]]), 6);
        k++;
        if (k == 12)
        {
            *output_ptr++ = '\n';
            BUFFER_CHECK(systab);
            k = 0;
        }
    }
    field(offset, 6);
    k++;
    *output_ptr++ = '\n';
    BUFFER_CHECK(systab);

    /**************************************************************/
    /* Compute and write out the range of the NACTION_SYMBOLS map.*/
    /**************************************************************/
    naction_symbols_range = Allocate_short_array(offset);

    compute_naction_symbols_range(state_start, state_stack,
                                  state_list, naction_symbols_range);

    k = 0;
    for (i = 0; i < (offset - 1); i++)
    {