produce.c

一个非常好的检索工具

/* $Id: produce.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
/*
 This software is subject to the terms of the IBM Jikes Compiler
 License Agreement available at the following URL:
 http://www.ibm.com/research/jikes.
 Copyright (C) 1983, 1999, International Business Machines Corporation
 and others.  All Rights Reserved.
 You must accept the terms of that agreement to use this software.
*/
static char hostfile[] = __FILE__;

#include <string.h>
#include "common.h"
#include "header.h"

static short *stack,
             *index_of,
             *nt_list,
             *item_list,
             *item_of,
             *next_item,
             *scope_table;

static int scope_top = 0;

static struct node **direct_produces;

static struct scope_elmt
{
    short link,
          item,
          index;
} *scope_element;

static BOOLEAN *symbol_seen;

static SET_PTR produces,
               right_produces,
               left_produces;

static int top;

static void compute_produces(int symbol);
static void print_name_map(int symbol);
static void process_scopes(void);
static BOOLEAN is_scope(int item_no);
static BOOLEAN scope_check(int lhs_symbol, int target, int source);
static insert_prefix(int item_no);
static BOOLEAN is_prefix_equal(int item_no, int item_no2);
static insert_suffix(int item_no);
static BOOLEAN is_suffix_equal(int item_no1, int item_no2);
static void print_scopes(void);
static get_shift_symbol(int lhs_symbol);

/****************************************************************************/
/*                              PRODUCE:                                    */
/****************************************************************************/
/* This procedure computes for each state the set of non-terminal symbols   */
/* that are required as candidates for secondary error recovery.  If the    */
/* option NAMES=OPTIMIZED is requested, the NAME map is optimized and SYMNO */
/* is updated accordingly.                                                  */
/****************************************************************************/
void produce(void)
{
    /*****************************************************************/
    /* TOP, STACK, and INDEX are used for the digraph algorithm      */
    /* in the routines COMPUTE_PRODUCES.                             */
    /*                                                               */
    /* The array PRODUCES is used to construct two maps:             */
    /*                                                               */
    /* 1) PRODUCES, a mapping from each non-terminal A to the set of */
    /* non-terminals C such that:                                    */
    /*                                                               */
    /*                   A  =>*  x C w                               */
    /*                                                               */
    /* 2) RIGHT_MOST_PRODUCES, a mapping from each non-terminal A to */
    /* the set of non-terminals C such that:                         */
    /*                                                               */
    /*                   C =>+ A x   and   x =>* %empty.             */
    /*                                                               */
    /* NOTE: This is really a reverse right-most produces mapping,   */
    /*       since given the above rule, we say that                 */
    /*       C right-most produces A.                                */
    /*                                                               */
    /*****************************************************************/

    int state_no,
        state,
        nt_root,
        item_no,
        item_root,
        rule_no,
        symbol,
        nt,
        i,
        n;

    short *names_map;

    struct node **goto_domain,
                *p,
                *q;

    BOOLEAN *name_used,
             end_node;

    SET_PTR set;

    stack = Allocate_short_array(num_symbols + 1);
    index_of = Allocate_short_array(num_symbols + 1);
    names_map = Allocate_short_array(num_names + 1);
    name_used = Allocate_boolean_array(num_names + 1);
    item_list = Allocate_short_array(num_items + 1);
    nt_list = Allocate_short_array(num_non_terminals + 1);
    nt_list -= (num_terminals + 1);
    set = (SET_PTR)
          calloc(1, non_term_set_size * sizeof(BOOLEAN_CELL));
    if (set == NULL)
        nospace(__FILE__, __LINE__);

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

    direct_produces = (struct node **)
                      calloc(num_non_terminals, sizeof(struct node *));
    if (direct_produces == NULL)
        nospace(__FILE__, __LINE__);
    direct_produces -= (num_terminals + 1);

    goto_domain = (struct node **)
                  calloc(num_states + 1, sizeof(struct node *));
    if (goto_domain == NULL)
        nospace(__FILE__, __LINE__);

/*********************************************************************/
/* Note that the space allocated for PRODUCES and DIRECT_PRODUCES    */
/* is automatically initialized to 0 by calloc. Logically, this sets */
/* all the sets in the PRODUCES map to the empty set and all the     */
/* pointers in DIRECT_PRODUCES are set to NULL.                      */
/*                                                                   */
/* Next, PRODUCES is initialized to compute RIGHT_MOST_PRODUCES.     */
/* Also, we count the number of error rules and verify that they are */
/* in the right format.                                              */
/*********************************************************************/
    item_root = NIL;
    for ALL_NON_TERMINALS(nt)
    {
        for (end_node = ((p = clitems[nt]) == NULL);
             ! end_node; end_node = (p == clitems[nt]))
        {
            p = p -> next;
            item_no = p -> value;
            symbol = item_table[item_no].symbol;
            if (symbol IS_A_NON_TERMINAL)
            {
                i = item_table[item_no].suffix_index;
                if (IS_IN_SET(first, i, empty) &&
                    (! IS_IN_NTSET(produces, symbol, nt - num_terminals)))
                {
                    NTSET_BIT_IN(produces, symbol, nt - num_terminals);
                    q = Allocate_node();
                    q -> value = nt;
                    q -> next = direct_produces[symbol];
                    direct_produces[symbol] = q;
                }
            }
            rule_no = item_table[item_no].rule_number;
            for (i = 0; i < RHS_SIZE(rule_no); i++)
            {
                if (item_table[item_no + i].symbol == error_image)
                    break;
            }
            item_no += i;
            symbol = item_table[item_no].symbol;
            if (symbol == error_image)
            {
                if (item_table[item_no + 1].symbol IS_A_NON_TERMINAL && i > 0)
                {
                   symbol = item_table[item_no + 2].symbol;
                   if (symbol == empty)
                       num_error_rules++;
                }
                if (warnings_bit && symbol != empty)
                {
                    item_list[item_no] = item_root;
                    item_root = item_no;
                }
            }
            symbol = eoft_image;
        }
    }

    /*********************************************************************/
    /* If WARNINGS_BIT is on and some error rules are in the wrong,      */
    /* format, report them.                                              */
    /*********************************************************************/
    if (warnings_bit && item_root != NIL)
    {
        PR_HEADING;
        if (item_list[item_root] == NIL)
            fprintf(syslis,
                    "*** This error rule is not in manual format:\n\n");
        else
            fprintf(syslis,
                    "*** These error rules are not in manual format:\n\n");
        for (item_no = item_root;
             item_no != NIL; item_no = item_list[item_no])
        {
            print_item(item_no);
        }
    }

/********************************************************************/
/* Complete the construction of the RIGHT_MOST_PRODUCES map for     */
/* non-terminals using the digraph algorithm.                       */
/* We make sure that each non-terminal A is not present in its own  */
/* PRODUCES set since we are interested in the non-reflexive        */
/* (positive) transitive closure.                                   */
/********************************************************************/
    for ALL_SYMBOLS(i)
        index_of[i] = OMEGA;

    top = 0;
    for ALL_NON_TERMINALS(nt)
    {
        if (index_of[nt] == OMEGA)
            compute_produces(nt);
        NTRESET_BIT_IN(produces, nt, nt - num_terminals);
    }

/********************************************************************/
/* Construct the minimum subset of the domain of the GOTO map       */
/* needed for automatic secondary level error recovery.   For each  */
/* state, we start out with the set of all nonterminals on which    */
/* there is a transition in that state, and pare it down to a       */
/* subset S, by removing all nonterminals B in S such that there    */
/* is a goto-reduce action on B by a single production.  If the     */
/* READ-REDUCE option is not turned on, then, we check whether or   */
/* not the goto action on B is to an LR(0) reduce state.Once we have*/
/* our subset S, we further reduce its size as follows.  For each   */
/* nonterminal A in S such that there exists another nonterminal    */
/* B in S, where B ^= A,  A ->+ Bx  and  x =>* %empty, we remove A  */
/* from S.                                                          */
/* At the end of this process, the nonterminal elements whose       */
/* NT_LIST values are still OMEGA are precisely the nonterminal     */
/* symbols that are never used as candidates.                       */
/********************************************************************/
    for ALL_NON_TERMINALS(i)
        nt_list[i] = OMEGA;
    nt_list[accept_image] = NIL;

    for ALL_STATES(state_no)
    {
        struct goto_header_type go_to;

        go_to = statset[state_no].go_to;
        nt_root = NIL;
        INIT_NTSET(set);

        for (i = 1; i <= go_to.size; i++)
        {
            symbol = GOTO_SYMBOL(go_to, i);
            state = GOTO_ACTION(go_to, i);
            if (state < 0)
                rule_no = -state;
            else
            {
                q = statset[state].kernel_items;
                item_no = q -> value;
                if (q -> next != NULL)
                    rule_no = 0;
                else
                    rule_no = item_table[item_no].rule_number;
            }
            if (rule_no == 0 || RHS_SIZE(rule_no) != 1)
            {
                nt_list[symbol] = nt_root;
                nt_root = symbol;
                NTSET_UNION(set, 0, produces, symbol);
            }
        }

        goto_domain[state_no] = NULL;
        for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
        {
            if (! IS_ELEMENT(set, symbol - num_terminals))
            {
                q = Allocate_node();
                q -> value = symbol;
                q -> next = goto_domain[state_no];
                goto_domain[state_no] = q;
                gotodom_size++;
            }
        }
    }

    /********************************************************************/
    /* Allocate and construct the permanent goto domain structure:      */
    /*   GD_INDEX and GD_RANGE.                                         */
    /********************************************************************/
    n = 0;
    gd_index = Allocate_short_array(num_states + 2);
    gd_range = Allocate_short_array(gotodom_size + 1);

    for ALL_STATES(state_no)
    {
        gd_index[state_no] = n + 1;
        for (p = goto_domain[state_no]; p != NULL; q = p, p = p -> next)
            gd_range[++n] = p -> value;

        if (goto_domain[state_no] != NULL)
            free_nodes(goto_domain[state_no], q);
    }
    gd_index[num_states + 1] = n + 1;


/******************************************************************/
/* Remove names assigned to nonterminals that are never used as   */
/* error candidates.                                              */
/******************************************************************/
    if (names_opt == OPTIMIZE_PHRASES)
    {
        /*****************************************************************/
        /* In addition to nonterminals that are never used as candidates,*/
        /* if a nullable nonterminal was assigned a name by default      */
        /* (nonterminals that were "named" by default are identified     */
        /* with negative indices), that name is also removed.            */
        /*****************************************************************/
        for ALL_NON_TERMINALS(symbol)
        {
            if (nt_list[symbol] == OMEGA)
                symno[symbol].name_index = symno[accept_image].name_index;
            else if (symno[symbol].name_index < 0)
            {
                if (null_nt[symbol])
                    symno[symbol].name_index = symno[accept_image].name_index;
                else
                    symno[symbol].name_index = - symno[symbol].name_index;
            }
        }


        /*******************************************************************/
        /* Adjust name map to remove unused elements and update SYMNO map. */
        /*******************************************************************/
        for (i = 1; i <= num_names; i++)
            name_used[i] = FALSE;

        for ALL_SYMBOLS(symbol)
            name_used[symno[symbol].name_index] = TRUE;

        n = 0;
        for (i = 1; i <= num_names; i++)
        {
            if (name_used[i])
            {
                name[++n] = name[i];
                names_map[i] = n;
            }
        }
        num_names = n;

        for ALL_SYMBOLS(symbol)
            symno[symbol].name_index = names_map[symno[symbol].name_index];
    }

    /********************************************************************/
    /* If the option LIST_BIT is ON, print the name map.                */
    /********************************************************************/
    if (list_bit)
    {
        PR_HEADING;
        fprintf(syslis, "\nName map:\n");
        output_line_no += 2;

        for ALL_SYMBOLS(symbol)
        {
            if (symno[symbol].name_index != symno[accept_image].name_index)