produce.c

一个非常好的检索工具

/* entered into a table.  We also use the SYMBOL_SEEN array to       */
/* identify the set of left-hand side symbols associated with the    */
/* scopes.                                                           */
/*********************************************************************/
    scope_table = Allocate_short_array(SCOPE_SIZE);
    for (i = 0; i < SCOPE_SIZE; i++)
        scope_table[i] = NIL;

    for ALL_NON_TERMINALS(nt)
        symbol_seen[nt] = FALSE;

    for (item_no = item_root; item_no != NIL; item_no = item_list[item_no])
    {
        rule_no = item_table[item_no].rule_number;
        symbol = rules[rule_no].lhs;
        num_scopes = num_scopes + 1;

        symbol_seen[symbol] = TRUE;

        prefix_index[item_no] = insert_prefix(item_no);
        suffix_index[item_no] = insert_suffix(item_no);
    }
    ffree(scope_table);

/*********************************************************************/
/* We now construct a mapping from each nonterminal symbol that is   */
/* the left-hand side of a rule containing scopes into the set of    */
/* states that has a transition on the nonterminal in question.      */
/*********************************************************************/
    nt_root = NIL;
    for ALL_NON_TERMINALS(nt)
        states_of[nt] = NULL;

    for ALL_STATES(state_no)
    {
        struct goto_header_type go_to;

        go_to = statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
        {
            symbol = GOTO_SYMBOL(go_to, i);
            if (symbol_seen[symbol])
            {
                if (states_of[symbol] == NULL)
                {
                    nt_list[symbol] = nt_root;
                    nt_root = symbol;
                    num_state_sets = num_state_sets + 1;
                }
                q = Allocate_node();
                q -> value = state_no;
                q -> next  = states_of[symbol];
                states_of[symbol] = q;
            }
        }
    }

    right_produces += ((num_terminals + 1) * non_term_set_size);
    ffree(right_produces);
    left_produces += ((num_terminals + 1) * non_term_set_size);
    ffree(left_produces);

/*********************************************************************/
/* Next, we used the optimal partition procedure to compress the     */
/* space used by the sets of states, allocate the SCOPE structure    */
/* and store the compressed sets of states in it.                    */
/* We also sort the list of items by the length of their prefixes in */
/* descending order.  This is done primarily as an optimization.     */
/* If a longer prefix matches prior to a shorter one, the parsing    */
/* will terminate quicker.                                           */
/*********************************************************************/
process_scope_states:
    {
        SET_PTR collection;

        short *element_size,
              *list,
              *start,
              *stack,
              *ordered_symbol,
              *state_list,
              *bucket;

        int state_root,
            state_no;

        state_set_size = num_states / SIZEOF_BC
                                    + (num_states % SIZEOF_BC ? 1 : 0);
        collection = (SET_PTR)
                     calloc(num_state_sets + 1,
                            state_set_size * sizeof(BOOLEAN_CELL));
        if (collection == NULL)
            nospace(__FILE__, __LINE__);

        element_size = Allocate_short_array(num_state_sets + 1);
        start = Allocate_short_array(num_state_sets + 2);
        stack = Allocate_short_array(num_state_sets + 1);
        ordered_symbol = Allocate_short_array(num_state_sets + 1);
        list = Allocate_short_array(num_state_sets + 1);
        state_list = Allocate_short_array(num_states + 1);
        bucket = Allocate_short_array(max_prefix_length + 1);

        for (symbol = nt_root, i = 1;
             symbol != NIL; symbol = nt_list[symbol], i++)
        {
            list[i] = i;
            ordered_symbol[i] = symbol;
            EMPTY_COLLECTION_SET(i);
            element_size[i] = 0;
            for (p = states_of[symbol]; p != NULL; p = p -> next)
            {
                element_size[i]++;
                SET_COLLECTION_BIT(i, p -> value);
            }
        }

        partset(collection, element_size, list, start, stack, num_state_sets);

        for (i = 1; i <= num_state_sets; i++)
        {
            symbol = ordered_symbol[i];
            state_index[symbol] = ABS(start[i]);
        }
        scope_state_size = start[num_state_sets + 1] - 1;

        scope = (struct scope_type *)
                calloc(num_scopes + 1, sizeof(struct scope_type));
        if (scope == NULL)
            nospace(__FILE__, __LINE__);
        scope_right_side = Allocate_short_array(scope_rhs_size + 1);
        scope_state = Allocate_short_array(scope_state_size + 1);

        k = 0;
        for (i = 0; i <= (int) num_states; i++)
            state_list[i] = OMEGA;

        for (i = 1; i <= num_state_sets; i++)
        {
            if (start[i] > 0)
            {
                state_root = 0;
                state_list[state_root] = NIL;

                for (end_node = ((j = i) == NIL);
                     ! end_node; end_node = (j == i))
                {
                    j = stack[j];
                    symbol = ordered_symbol[j];
                    for (p = states_of[symbol]; p != NULL; p = p -> next)
                    {
                        state_no = p -> value;
                        if (state_list[state_no] == OMEGA)
                        {
                            state_list[state_no] = state_root;
                            state_root = state_no;
                        }
                    }
                }

                for (state_no = state_root;
                     state_no != NIL; state_no = state_root)
                {
                    state_root = state_list[state_no];
                    state_list[state_no] = OMEGA;
                    k++;
                    scope_state[k] = state_no;
                }
            }
        }

        for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
        {
            for (p = states_of[symbol]; p != NULL; q = p, p = p -> next)
                ;
            free_nodes(states_of[symbol], q);
        }

/***********************************************************************/
/* Use the BUCKET array as a base to partition the scoped items        */
/* based on the length of their prefixes.  The list of items in each   */
/* bucket is kept in the NEXT_ITEM array sorted in descending order    */
/* of the length of the right-hand side of the item.                   */
/* Items are kept sorted in that fashion because when two items have   */
/* the same prefix, we want the one with the shortest suffix to be     */
/* chosen. In other words, if we have two scoped items, say:           */
/*                                                                     */
/*    A ::= x . y       and      B ::= x . z     where |y| < |z|       */
/*                                                                     */
/* and both of them are applicable in a given context with similar     */
/* result, then we always want A ::= x . y to be used.                 */
/***********************************************************************/
        for (i = 1; i <= max_prefix_length; i++)
            bucket[i] = NIL;

        for (item_no = item_root;
             item_no != NIL; item_no = item_list[item_no])
        {
            int tail;

            k = item_table[item_no].dot;
            for (i = bucket[k]; i != NIL; tail = i, i = next_item[i])
            {
                if (RHS_SIZE(item_table[item_no].rule_number) >=
                    RHS_SIZE(item_table[i].rule_number))
                   break;
            }

            next_item[item_no] = i;
            if (i == bucket[k])
                 bucket[k] = item_no;       /* insert at the beginning */
            else next_item[tail] = item_no; /* insert in middle or end */
        }

/*********************************************************************/
/* Reconstruct list of scoped items in sorted order. Since we want   */
/* the items in descending order, we start with the smallest bucket  */
/* proceeding to the largest one and insert the items from each      */
/* bucket in LIFO order in ITEM_LIST.                                */
/*********************************************************************/
        item_root = NIL;
        for (k = 1; k <= max_prefix_length; k++)
        {
            for (item_no = bucket[k];
                 item_no != NIL; item_no = next_item[item_no])
            {
                item_list[item_no] = item_root;
                item_root = item_no;
            }
        }

        ffree(collection);
        ffree(element_size);
        ffree(start);
        ffree(stack);
        ffree(ordered_symbol);
        ffree(state_list);
        ffree(list);
        ffree(bucket);
    } /* End PROCESS_SCOPE_STATES */

/*********************************************************************/
/* Next, we initialize the remaining fields of the SCOPE structure.  */
/*********************************************************************/
    item_no = item_root;
    for (i = 1; item_no != NIL; i++)
    {
        scope[i].prefix = prefix_index[item_no];
        scope[i].suffix = suffix_index[item_no];
        rule_no = item_table[item_no].rule_number;
        scope[i].lhs_symbol = rules[rule_no].lhs;
        symbol = rhs_sym[rules[rule_no].rhs + item_table[item_no].dot];
        if (symbol IS_A_TERMINAL)
            scope[i].look_ahead = symbol;
        else
        {
            for ALL_NON_TERMINALS(j)
                symbol_seen[j] = FALSE;
            scope[i].look_ahead = get_shift_symbol(symbol);
        }
        scope[i].state_set = state_index[scope[i].lhs_symbol];
        item_no = item_list[item_no];
    }

    for (j = 1; j <= scope_top; j++)
    {
        if (scope_element[j].item < 0)
        {
            item_no = -scope_element[j].item;
            rule_no = item_table[item_no].rule_number;
            n = scope_element[j].index;
            for (k = rules[rule_no].rhs+item_table[item_no].dot - 1;
                 k >= rules[rule_no].rhs; /* symbols before dot*/
                 k--)
                scope_right_side[n++] = rhs_sym[k];
        }
        else
        {
            item_no = scope_element[j].item;
            rule_no = item_table[item_no].rule_number;
            n = scope_element[j].index;
            for (k = rules[rule_no].rhs + item_table[item_no].dot;
                 k < rules[rule_no + 1].rhs; /* symbols after dot */
                 k++)
            {
                symbol = rhs_sym[k];
                if (symbol IS_A_NON_TERMINAL)
                {
                    if (! null_nt[symbol])
                        scope_right_side[n++] = rhs_sym[k];
                }
                else if (symbol != error_image)
                    scope_right_side[n++] = rhs_sym[k];
            }
        }
        scope_right_side[n] = 0;
    }

    if (list_bit)
        print_scopes();

    ffree(prefix_index);
    ffree(suffix_index);
    item_of += (num_terminals + 1);
    ffree(item_of);
    ffree(next_item);
    symbol_seen += (num_terminals + 1);
    ffree(symbol_seen);
    states_of += (num_terminals + 1);
    ffree(states_of);
    state_index += (num_terminals + 1);
    ffree(state_index);
    ffree(scope_element);

    return;
}


/*********************************************************************/
/*                              IS_SCOPE:                            */
/*********************************************************************/
/* This procedure checks whether or not an item of the form:         */
/* [A  ->  w B x  where  B ->* y A z  is a valid scope.              */
/*                                                                   */
/* Such an item is a valid scope if the following conditions hold:   */
/*                                                                   */
/* 1) it is not the case that x =>* %empty                           */
/* 2) either it is not the case that w =>* %empty or it is not the   */
/*    case that B =>lm* A.                                           */
/* 3) it is not the case that whenever A is introduced through       */
/*    closure, it is introduced by a nonterminal C where C =>rm* A   */
/*    and C =>rm+ B.                                                 */
/*********************************************************************/
static BOOLEAN is_scope(int item_no)
{
    int i,
        nt,
        lhs_symbol,
        target,
        symbol;

    for (i = item_no - item_table[item_no].dot; i < item_no; i++)
    {
        symbol = item_table[i].symbol;
        if (symbol IS_A_TERMINAL)
            return(TRUE);
        if (! null_nt[symbol])
            return(TRUE);
    }

    lhs_symbol = rules[item_table[item_no].rule_number].lhs;
    target = item_table[item_no].symbol;
    if (IS_IN_NTSET(left_produces, target, lhs_symbol - num_terminals))
        return(FALSE);

    if (item_table[item_no].dot > 0)
        return(TRUE);

    for ALL_NON_TERMINALS(nt)
        symbol_seen[nt] = FALSE;

    return(scope_check(lhs_symbol, target, lhs_symbol));
}

/*********************************************************************/
/*                             SCOPE_CHECK:                          */
/*********************************************************************/
/* Given a nonterminal LHS_SYMBOL and a nonterminal TARGET where,    */
/*                                                                   */
/*                     LHS_SYMBOL ::= TARGET x                       */
/*                                                                   */
/* find out if whenever LHS_SYMBOL is introduced through closure, it */
/* is introduced by a nonterminal SOURCE such that                   */
/*                                                                   */
/*                     SOURCE ->rm* LHS_SYMBOL                       */
/*                                                                   */
/*                               and                                 */
/*                                                                   */
/*                     SOURCE ->rm+ TARGET                           */
/*                                                                   */
/*********************************************************************/
static BOOLEAN scope_check(int lhs_symbol, int target, int source)
{