timetab.c

一个非常好的检索工具

        root_symbol = 0;

        default_rule = REDUCE_RULE_NO(red, 0);
        for (i = 1; i <= red.size; i++)
        {
            if (REDUCE_RULE_NO(red, i) != default_rule)
            {
                symbol = REDUCE_SYMBOL(red, i);
                symbol_list[symbol] = root_symbol;
                root_symbol = symbol;
            }
        }

/*********************************************************************/
/* INDX is set to the beginning of the list of available slots and   */
/* we try to determine if it might be a valid starting position. If  */
/* not, INDX is moved to the next element, and we repeat the process */
/* until a valid position is found.                                  */
/*********************************************************************/
        indx = first_index;

look_for_match_in_table:
        if (indx == NIL)
            indx = table_size + 1;
        if (indx + num_symbols > (int) table_size)
            reallocate();

        for (symbol = root_symbol;
             symbol != NIL; symbol = symbol_list[symbol])
        {
            if (next[indx + symbol] == OMEGA)
            {
                indx = next[indx];
                goto look_for_match_in_table;
            }
        }

/*********************************************************************/
/* At this stage, a position(INDX), was found to overlay the row in  */
/* question.  Remove elements associated with all positions that     */
/* will be taken by row from the doubly-linked list.                 */
/* NOTE that since SYMBOLs start at 1, the first index can never be  */
/* a candidate (==> I = INDX + SYMBOL) in this loop.                 */
/*********************************************************************/
        if (indx > max_indx)
            max_indx = indx;

        state_index[state_no] = indx;

        for (symbol = root_symbol;
             symbol != NIL; symbol = symbol_list[symbol])
        {
            i = indx + symbol;
            if (first_index == last_index)
                first_index = NIL;
            else if (i == first_index)
            {
                first_index = next[first_index];
                previous[first_index] = NIL;
            }
            else 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;
        }
    }

/*********************************************************************/
/* Update all global counters, and compute ACCEPT_ACTION and         */
/* ERROR_ACTION.                                                     */
/*********************************************************************/
    table_size = max_indx + num_symbols;
    accept_act = max_indx + num_rules + 1;
    error_act = accept_act + 1;

    for (action_size = table_size; action_size >= max_indx; action_size--)
         if (next[action_size] == OMEGA)
             break;

    printf("\n");
    sprintf(msg_line,"Length of Check table: %ld", table_size);
    PRNT(msg_line);

    sprintf(msg_line,"Length of Action table: %ld", action_size);
    PRNT(msg_line);

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

    percentage = ((action_size - num_entries) * 1000) / num_entries;
    sprintf(msg_line, "Percentage of increase: %d.%d%%",
                      percentage / 10, percentage % 10);
    PRNT(msg_line);

    if (byte_bit)
    {
        num_bytes = 2 * action_size + table_size;
        if ((! goto_default_bit) && (! nt_check_bit))
        {
            for (; (last_symbol >= 1) && (! is_terminal[last_symbol]);
                last_symbol--);
        }
        sprintf(msg_line,
                "Highest symbol in Check Table: %d", last_symbol);
        PRNT(msg_line);
        if (last_symbol > 255)
            num_bytes += table_size;
    }
    else
        num_bytes = 2 * (action_size + table_size);

    if (goto_default_bit)
        num_bytes += ((long) 2 * num_symbols);

    k_bytes = (num_bytes / 1024) + 1;

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

    num_bytes = (long) 4 * num_rules;
    if (byte_bit)
    {
        num_bytes -= num_rules;
        if (num_symbols < 256)
            num_bytes -= num_rules;
    }
    sprintf(msg_line,
            "Storage Required for Rules: %ld Bytes", num_bytes);
    PRNT(msg_line);

    return;
}


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

    struct goto_header_type   go_to;
    struct shift_header_type  sh;
    struct reduce_header_type red;

    int la_shift_count = 0,
        shift_count = 0,
        goto_count = 0,
        default_count = 0,
        reduce_count = 0,
        shift_reduce_count = 0,
        goto_reduce_count = 0;

    int indx,
        la_state_offset,
        act,
        result_act,
        i,
        j,
        k,
        symbol,
        state_no;

    char *tok;

    long offset;

    state_list = Allocate_short_array(max_la_state + 1);

    check = next;
    action = previous;

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

/*********************************************************************/
/* Initialize all unfilled slots with default values.                */
/*********************************************************************/
    indx = first_index;
    for (i = indx; (i != NIL) && (i <= (int) action_size); i = indx)
    {
        indx = next[i];

        check[i] = DEFAULT_SYMBOL;
        action[i] = error_act;
    }
    for (i = (int) action_size + 1; i <= (int) table_size; i++)
        check[i] = DEFAULT_SYMBOL;

/*********************************************************************/
/* We set the rest of the table with the proper table entries.       */
/*********************************************************************/
    for (state_no = 1; state_no <= (int) max_la_state; state_no++)
    {
        indx = state_index[state_no];
        if (state_no > (int) num_states)
        {
            sh = shift[lastats[state_no].shift_number];
            red = lastats[state_no].reduce;
        }
        else
        {
            go_to = statset[state_no].go_to;
            for (j = 1; j <= go_to.size; j++)
            {
                symbol = GOTO_SYMBOL(go_to, j);
                i = indx + symbol;
                if (goto_default_bit || nt_check_bit)
                    check[i] = symbol;
                else
                    check[i] = DEFAULT_SYMBOL;
                act = GOTO_ACTION(go_to, j);
                if (act > 0)
                {
                    action[i] = state_index[act] + num_rules;
                    goto_count++;
                }
                else
                {
                    action[i] = -act;
                    goto_reduce_count++;
                }
            }
            sh = shift[statset[state_no].shift_number];
            red = reduce[state_no];
        }

        for (j = 1; j <= sh.size; j++)
        {
            symbol = SHIFT_SYMBOL(sh, j);
            i = indx + symbol;
            check[i] = symbol;
            act = SHIFT_ACTION(sh, j);
            if (act > (int) num_states)
            {
                result_act = la_state_offset + state_index[act];
                la_shift_count++;
            }
            else if (act > 0)
            {
                result_act = state_index[act] + num_rules;
                shift_count++;
            }
            else
            {
                result_act = -act + error_act;
                shift_reduce_count++;
            }

            if (result_act > (MAX_TABLE_SIZE + 1))
            {
                sprintf(msg_line,
                    "Table contains look-ahead shift entry that is >"
                    " %d; Processing stopped.", MAX_TABLE_SIZE + 1);
                PRNTERR(msg_line);
                return;
            }

            action[i] = result_act;
        }

/*********************************************************************/
/*   We now initialize the elements reserved for reduce actions in   */
/* the current state.                                                */
/*********************************************************************/
        default_rule = REDUCE_RULE_NO(red, 0);
        for (j = 1; j <= red.size; j++)
        {
            if (REDUCE_RULE_NO(red, j) != default_rule)
            {
                symbol = REDUCE_SYMBOL(red, j);
                i = indx + symbol;
                check[i] = symbol;
                act = REDUCE_RULE_NO(red, j);
                if (rules[act].lhs == accept_image)
                    action[i] = accept_act;
                else
                    action[i] = act;
                reduce_count++;
            }
        }

/*********************************************************************/
/*   We now initialize the element reserved for the DEFAULT reduce   */
/* action of the current state.  If error maps are requested,  the   */
/* default slot is initialized to the original state number, and the */
/* corresponding element of the DEFAULT_REDUCE array is initialized. */
/* Otherwise it is initialized to the rule number in question.       */
/*********************************************************************/
        i = indx + DEFAULT_SYMBOL;
        check[i] = DEFAULT_SYMBOL;
        act = REDUCE_RULE_NO(red, 0);
        if (act == OMEGA)
            action[i] = error_act;
        else
        {
            action[i] = act;
            default_count++;
        }
    }

    PRNT("\n\nActions in Compressed Tables:");
    sprintf(msg_line,"     Number of Shifts: %d",shift_count);
    PRNT(msg_line);

    sprintf(msg_line,"     Number of Shift/Reduces: %d",shift_reduce_count);
    PRNT(msg_line);

    if (max_la_state > num_states)
    {
        sprintf(msg_line,
                "     Number of Look-Ahead Shifts: %d", la_shift_count);