produce.c

一个非常好的检索工具

                print_name_map(symbol);
        }
        for ALL_SYMBOLS(symbol)
        {
            if (symbol != accept_image &&
                symno[symbol].name_index == symno[accept_image].name_index)
                print_name_map(symbol);
        }
    }

    if (scopes_bit)
        process_scopes();

    ffree(stack);
    ffree(index_of);
    ffree(names_map);
    ffree(name_used);
    nt_list += (num_terminals + 1);
    ffree(nt_list);
    ffree(set);
    produces += ((num_terminals + 1) * non_term_set_size);
    ffree(produces);
    direct_produces += (num_terminals + 1);
    ffree(direct_produces);
    ffree(goto_domain);

    return;
}


/******************************************************************/
/*                     COMPUTE_PRODUCES:                          */
/******************************************************************/
/* This procedure is used to compute the transitive closure of    */
/* the PRODUCES, LEFT_PRODUCES and RIGHT_MOST_PRODUCES maps.      */
/******************************************************************/
static void compute_produces(int symbol)
{
    int indx;
    int new_symbol;

    struct node *p,
                *q;

    stack[++top] = symbol;
    indx = top;
    index_of[symbol] = indx;

    for (p = direct_produces[symbol]; p != NULL; q = p, p = p -> next)
    {
        new_symbol = p -> value;
        if (index_of[new_symbol] == OMEGA)  /* first time seen? */
            compute_produces(new_symbol);
        index_of[symbol] = MIN(index_of[symbol], index_of[new_symbol]);
        NTSET_UNION(produces, symbol, produces, new_symbol);
    }
    if (direct_produces[symbol] != NULL)
        free_nodes(direct_produces[symbol], q);

    if (index_of[symbol] == indx)  /*symbol is SCC root */
    {
        for (new_symbol = stack[top];
             new_symbol != symbol; new_symbol = stack[--top])
        {
            ASSIGN_NTSET(produces, new_symbol, produces, symbol);
            index_of[new_symbol] = INFINITY;
        }

        index_of[symbol] = INFINITY;
        top--;
    }

    return;
}



/******************************************************************/
/*                       PRINT_NAME_MAP:                          */
/******************************************************************/
/* This procedure prints the name associated with a given symbol. */
/* The same format that was used in the procedure DISPLAY_INPUT   */
/* to print aliases is used to print name mappings.               */
/******************************************************************/
static void print_name_map(int symbol)
{
    int len;

    char line[PRINT_LINE_SIZE],
         tok[SYMBOL_SIZE + 1];

    restore_symbol(tok, RETRIEVE_STRING(symbol));

    len = PRINT_LINE_SIZE - 5;
    print_large_token(line, tok, "", len);
    strcat(line, " ::= ");
    restore_symbol(tok, RETRIEVE_NAME(symno[symbol].name_index));
    if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 1)
    {
        fprintf(syslis, "\n%s", line);
        ENDPAGE_CHECK;
        len = PRINT_LINE_SIZE - 4;
        print_large_token(line, tok, "    ", len);
    }
    else
       strcat(line, tok);

    fprintf(syslis, "\n%s", line);
    ENDPAGE_CHECK;

    return;
}


/******************************************************************/
/*                         PROCESS_SCOPES:                        */
/******************************************************************/
/* Compute set of "scopes" and use it to construct SCOPE map.     */
/******************************************************************/
static void process_scopes(void)
{
    short *prefix_index,
          *suffix_index,
          *state_index;

    struct node **states_of;

    int num_state_sets = 0,
        i,
        j,
        k,
        n;

    short max_prefix_length = 0,
          dot_symbol,
          nt,
          symbol,
          item_root,
          item_no,
          rule_no,
          state_no,
          nt_root;

    BOOLEAN end_node;

    struct node *p,
                *q;

    prefix_index = Allocate_short_array(num_items + 1);
    suffix_index = Allocate_short_array(num_items + 1);
    item_of = Allocate_short_array(num_non_terminals);
    item_of -= (num_terminals + 1);
    next_item = Allocate_short_array(num_items + 1);

    symbol_seen = Allocate_boolean_array(num_non_terminals);
    symbol_seen -= (num_terminals + 1);
    states_of = (struct node **)
                calloc(num_non_terminals, sizeof(struct node *));
    states_of -= (num_terminals + 1);
    state_index = Allocate_short_array(num_non_terminals);
    state_index -= (num_terminals + 1);
    scope_element = (struct scope_elmt *)
                    calloc(num_items + 1, sizeof(struct scope_elmt));

/********************************************************************/
/* Initially, PRODUCES was used to compute the right-most-produces  */
/* map.  We save that map map and make it reflexive.  Recall that   */
/* RIGHT_PRODUCES is a mapping from each nonterminal B into the set */
/* of nonterminals A such that:                                     */
/*                                                                  */
/*    A =>rm* B                                                     */
/*                                                                  */
/* Next, reallocate PRODUCES and initialize it in order to          */
/* construct the LEFT_PRODUCES map. Initially, CALLOC sets PRODUCES */
/* to the empty map.                                                */
/* LEFT_PRODUCES is a mapping  from each nonterminal A into the set */
/* of nonterminals B such that:                                     */
/*                                                                  */
/*    A =>lm* B x                                                   */
/*                                                                  */
/* for some arbitrary string x.                                     */
/*                                                                  */
/* Since A ->* A for all A,  we insert A in PRODUCES(A)  (but not   */
/* in the linked list).                                             */
/*                                                                  */
/********************************************************************/
    right_produces = produces;
    produces = (SET_PTR)
               calloc(num_non_terminals,
                      non_term_set_size * sizeof(BOOLEAN_CELL));
    if (produces == NULL)
        nospace(__FILE__, __LINE__);
    produces -= ((num_terminals + 1) * non_term_set_size);

    for ALL_NON_TERMINALS(nt)
    {
        NTSET_BIT_IN(right_produces, nt, nt - num_terminals);
        NTSET_BIT_IN(produces, nt, nt - num_terminals);

        direct_produces[nt] = NULL;

        for (end_node = ((p = clitems[nt]) == NULL);
             ! end_node; end_node = (p == clitems[nt]))
        {
            p = p -> next;
            for (item_no = p -> value;
                 item_table[item_no].symbol IS_A_NON_TERMINAL;
                 item_no++)
            {
                symbol = item_table[item_no].symbol;
                if (! IS_IN_NTSET(produces, nt, symbol - num_terminals))
                {
                    NTSET_BIT_IN(produces, nt, symbol - num_terminals);
                    q = Allocate_node();
                    q -> value = symbol;
                    q -> next = direct_produces[nt];
                    direct_produces[nt] = q;
                }
                if (! null_nt[symbol])
                    break;
            }
        }
    }

    /****************************************************************/
    /* Complete the construction of the LEFT_produces map for       */
    /* non_terminals using the digraph algorithm.                   */
    /****************************************************************/
    for ALL_NON_TERMINALS(nt)
        index_of[nt] = OMEGA;

    top = 0;
    for ALL_NON_TERMINALS(nt)
    {
        if (index_of[nt] == OMEGA)
            compute_produces(nt);
    }
    left_produces = produces;

/********************************************************************/
/* Allocate and initialize the PRODUCES array to construct the      */
/* PRODUCES map.  After allocation, CALLOC sets all sets to empty.  */
/* Since A ->* A for all A,  we insert A in PRODUCES(A)  (but not   */
/* in the linked list).                                             */
/********************************************************************/
    produces = (SET_PTR)
               calloc(num_non_terminals,
                      non_term_set_size * sizeof(BOOLEAN_CELL));
    if (produces == NULL)
        nospace(__FILE__, __LINE__);
    produces -= ((num_terminals + 1) * non_term_set_size);

    for ALL_NON_TERMINALS(nt)
    {
        NTSET_BIT_IN(produces, nt, nt - num_terminals);

        direct_produces[nt] = NULL;

        for (end_node = ((p = clitems[nt]) == NULL);
             ! end_node; end_node = (p == clitems[nt]))
        {
            p = p -> next;
            for (item_no = p -> value;
                 item_table[item_no].symbol != empty; item_no++)
            {
                symbol = item_table[item_no].symbol;
                if (symbol IS_A_NON_TERMINAL)
                {
                    if (! IS_IN_NTSET(produces, nt, symbol - num_terminals))
                    {
                        NTSET_BIT_IN(produces, nt, symbol - num_terminals);
                        q = Allocate_node();
                        q -> value = symbol;
                        q -> next = direct_produces[nt];
                        direct_produces[nt] = q;
                    }
                }
            }
        }
    }

    /****************************************************************/
    /* Complete the construction of the PRODUCES map for            */
    /* non_terminals using the digraph algorithm.                   */
    /*                                                              */
    /* Since $ACC =>* x A y for all nonterminal A in the grammar, a */
    /* single call to COMPUTE_PRODUCES does the trick.              */
    /****************************************************************/
    for ALL_NON_TERMINALS(nt)
        index_of[nt] = OMEGA;
    top = 0;
    compute_produces(accept_image);

/********************************************************************/
/* Construct a mapping from each non_terminal A into the set of     */
/* items of the form [B  ->  x . A y].                              */
/********************************************************************/
    for ALL_NON_TERMINALS(nt)
        item_of[nt] = NIL;

    for ALL_ITEMS(item_no)
    {
        dot_symbol = item_table[item_no].symbol;
        if (dot_symbol IS_A_NON_TERMINAL)
        {
            next_item[item_no] = item_of[dot_symbol];
            item_of[dot_symbol] = item_no;
        }
    }

/********************************************************************/
/* Construct a list of scoped items in ITEM_LIST.                   */
/* Scoped items are derived from rules of the form  A -> x B y such */
/* that B =>* w A z, %empty not in FIRST(y), and it is not the case */
/* that x = %empty and B ->* A v.                                   */
/* Scoped items may also be identified by the user, using %error    */
/* productions.                                                     */
/* As scoped items are added to the list, we keep track of the      */
/* longest prefix encountered.  This is subsequently used to        */
/* bucket sort the scoped items in descending order of the length    */
/* of their prefixes.                                               */
/********************************************************************/
    for ALL_ITEMS(item_no)
        item_list[item_no] = OMEGA;

    item_root = NIL;
    for ALL_ITEMS(item_no)
    {
        dot_symbol = item_table[item_no].symbol;
        if (dot_symbol == error_image)
        {
            if (item_table[item_no].dot != 0 &&
                (! IS_IN_SET(first,
                             item_table[item_no].suffix_index, empty)))
            {
                if (item_list[item_no] == OMEGA)
                {
                    item_list[item_no] = item_root;
                    item_root = item_no;
                    max_prefix_length = MAX(max_prefix_length,
                                            item_table[item_no].dot);
                }
            }
        }
        else if (dot_symbol IS_A_NON_TERMINAL)
        {
            symbol = rules[item_table[item_no].rule_number].lhs;
            if (! IS_IN_SET(first, item_table[item_no].suffix_index,
                            empty) &&
                IS_IN_NTSET(produces, dot_symbol, symbol - num_terminals))
            {
                if (is_scope(item_no))
                {
                    for (i = item_no + 1; ;i++)
                    {
                        symbol = item_table[i].symbol;
                        if (symbol IS_A_TERMINAL)
                            break;
                        if (! null_nt[symbol])
                            break;
                    }
                    if (symbol IS_A_NON_TERMINAL)
                    {
                        for ALL_NON_TERMINALS(nt)
                            symbol_seen[nt] = FALSE;
                        symbol = get_shift_symbol(symbol);
                    }

                    if (symbol != empty && item_list[i] == OMEGA)
                    {
                        item_list[i] = item_root;
                        item_root = i;
                        max_prefix_length = MAX(max_prefix_length,
                                                item_table[i].dot);
                    }
                }
            }
        }
    }

/*********************************************************************/
/* In this loop, the prefix and suffix string for each scope in      */