mkstates.c

一个非常好的检索工具

/* $Id: mkstates.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 "common.h"
#include "header.h"

static void mklr0(void);
static struct state_element *lr0_state_map(struct node *kernel);

/****************************************************************************/
/* STATE_ELEMENT is used to represent states. Each state is mapped into a   */
/* unique number. The components QUEUE and LINK are auxiliary:              */
/*   QUEUE is used to form a sequential linked-list of the states ordered   */
/* STATE_NUMBER and identified by the variable STATE_ROOT.                  */
/*   LINK is used to resolve collisions in hashing the states.              */
/* NEXT_SHIFT is used to resolve collisions in hashing SHIFT maps.          */
/****************************************************************************/
struct state_element
{
    struct state_element     *link,
                             *queue,
                             *next_shift;
    struct node              *kernel_items,
                             *complete_items;
    struct shift_header_type lr0_shift;
    struct goto_header_type  lr0_goto;
    short                    shift_number,
                             state_number;
};

static struct state_element **state_table,
                            **shift_table,
                             *state_root,
                             *state_tail;

static short *shift_action;

static struct goto_header_type  no_gotos_ptr;
static struct shift_header_type no_shifts_ptr;

/*****************************************************************************/
/*                              MKSTATS:                                     */
/*****************************************************************************/
/* In this procedure, we first construct the LR(0) automaton.                */
/*****************************************************************************/
void mkstats(void)
{
    int j;

    no_gotos_ptr.size = 0;     /* For states with no GOTOs */
    no_gotos_ptr.map  = NULL;

    no_shifts_ptr.size = 0;    /* For states with no SHIFTs */
    no_shifts_ptr.map  = NULL;

    mklr0();

    if (error_maps_bit &&
        (table_opt == OPTIMIZE_TIME || table_opt == OPTIMIZE_SPACE))
        produce();

    /**********************************************************************/
    /* Free space trapped by the CLOSURE and CLITEMS maps.                */
    /**********************************************************************/
    for ALL_NON_TERMINALS(j)
    {
        struct node *p, *q;

        q = clitems[j];
        if (q != NULL)
        {
            p = q -> next;
            free_nodes(p, q);
        }

        q = closure[j];
        if (q != NULL)
        {
            p = q -> next;
            free_nodes(p, q);
        }
    }

    closure += (num_terminals + 1);
    ffree(closure);
    clitems += (num_terminals + 1);
    ffree(clitems);

    return;
}


/*****************************************************************************/
/*                               MKLR0:                                      */
/*****************************************************************************/
/* This procedure constructs an LR(0) automaton.                             */
/*****************************************************************************/
static void mklr0(void)
{
    /*****************************************************************/
    /* STATE_TABLE is the array used to hash the states. States are  */
    /* identified by their Kernel set of items. Hash locations are   */
    /* computed for the states. As states are inserted in the table, */
    /* they are threaded together via the QUEUE component of         */
    /* STATE_ELEMENT. The variable STATE_ROOT points to the root of  */
    /* the thread, and the variable STATE_TAIL points to the tail.   */
    /*                                                               */
    /*   After constructing a state, Shift and Goto actions are      */
    /* defined on that state based on a partition of the set of items*/
    /* in that state. The partitioning is based on the symbols       */
    /* following the dot in the items. The array PARTITION is used   */
    /* for that partitioning. LIST and ROOT are used to construct    */
    /* temporary lists of symbols in a state on which Shift or Goto  */
    /* actions are defined.                                          */
    /*   NT_LIST and NT_ROOT are used to build temporary lists of    */
    /* non-terminals.                                                */
    /*****************************************************************/

    struct node *p,
                *q,
                *r,
                *new_item,
                *tail,
                *item_ptr,
                **partition,
                *closure_root,
                *closure_tail;

    struct state_element *state,
                         *new_state;

    BOOLEAN end_node;

    int goto_size,
        shift_size,
        i,
        state_no,
        next_item_no,
        item_no,
        symbol,
        rule_no,
        shift_root,
        nt_root,
        root;

    struct goto_header_type go_to;

    short *shift_list,
          *nt_list,
          *list;

    /******************************************************************/
    /* Set up a a pool of temporary space.                            */
    /******************************************************************/
    reset_temporary_space();

    list = Allocate_short_array(num_symbols + 1);
    shift_action = Allocate_short_array(num_terminals + 1);
    shift_list = Allocate_short_array(num_terminals + 1);
    nt_list = Allocate_short_array(num_non_terminals);
    nt_list -= (num_terminals + 1);
    partition = (struct node **)
                calloc(num_symbols + 1, sizeof(struct node *));
    if (partition == NULL)
        nospace(__FILE__, __LINE__);
    state_table = (struct state_element **)
                  calloc(STATE_TABLE_SIZE, sizeof(struct state_element *));
    if (state_table == NULL)
        nospace(__FILE__, __LINE__);
    shift_table = (struct state_element **)
                  calloc(SHIFT_TABLE_SIZE, sizeof(struct state_element *));
    if (shift_table == NULL)
        nospace(__FILE__, __LINE__);

/* INITIALIZATION -----------------------------------------------------------*/
    goto_size = 0;
    shift_size = 0;

    state_root = NULL;

    for (i = 0; i <= num_terminals; i++)
        shift_action[i] = OMEGA;

    nt_root = NIL;
    for ALL_NON_TERMINALS(i)
        nt_list[i] = OMEGA;

   /* PARTITION, STATE_TABLE and SHIFT_TABLE are initialized by calloc */

/* END OF INITIALIZATION ----------------------------------------------------*/

    /*****************************************************************/
    /* Kernel of the first state consists of the first items in each */
    /* rule produced by Accept non-terminal.                         */
    /*****************************************************************/
    q = NULL;
    for (end_node = ((p = clitems[accept_image]) == NULL);
         ! end_node; /* Loop over circular list */
         end_node = (p == clitems[accept_image]))
    {
        p = p -> next;

        new_item = Allocate_node();
        new_item -> value = p -> value;
        new_item -> next = q;
        q = new_item;
    }

    /*****************************************************************/
    /* Insert first state in STATE_TABLE and keep constructing states*/
    /* until we no longer can.                                       */
    /*****************************************************************/

    for (state = lr0_state_map(q); /* insert initial state */
         state != NULL; /* and process next state until no more */
         state = state -> queue)
    {
        /******************************************************************/
        /* Now we construct a list of all non-terminals that can be       */
        /* introduced in this state through closure.  The CLOSURE of each */
        /* non-terminal has been previously computed in MKFIRST.          */
        /******************************************************************/
        for (q = state -> kernel_items;
             q != NULL; /* iterate over kernel set of items */
             q = q -> next)
        {
            item_no = q -> value;
            symbol = item_table[item_no].symbol;  /* symbol after dot */
            if (symbol IS_A_NON_TERMINAL)     /* Dot symbol */
            {
                if (nt_list[symbol] == OMEGA) /* not yet seen */
                {
                    nt_list[symbol] = nt_root;
                    nt_root = symbol;

                    for (end_node = ((p = closure[symbol]) == NULL);
                         ! end_node; /* Loop over circular list */
                         end_node = (p == closure[symbol]))
                    {   /* add its closure to list */
                        p = p -> next;

                        if (nt_list[p -> value] == OMEGA)
                        {
                            nt_list[p -> value] = nt_root;
                            nt_root = p -> value;
                        }
                    }
                }
            }
        }

        /*******************************************************************/
        /*   We now construct lists of all start items that the closure    */
        /* non-terminals produce.  A map from each non-terminal to its set */
        /* start items has previously been computed in MKFIRST. (CLITEMS)  */
        /* Empty items are placed directly in the state, whereas non_empty */
        /* items are placed in a temporary list rooted at CLOSURE_ROOT.    */
        /*******************************************************************/
        closure_root = NULL; /* used to construct list of closure items */
        for (symbol = nt_root; symbol != NIL;
             nt_list[symbol] = OMEGA, symbol = nt_root)
        {
            nt_root = nt_list[symbol];

            for (end_node = ((p = clitems[symbol]) == NULL);
                 ! end_node;  /* Loop over circular list */
                 end_node = (p == clitems[symbol]))
            {
                p = p -> next;

                item_no = p -> value;
                new_item = Allocate_node();
                new_item -> value = item_no;

                if (item_table[item_no].symbol == empty) /* complete item */
                {
                    /* Add to COMPLETE_ITEMS set in state */
                    new_item -> next = state -> complete_items;
                    state -> complete_items = new_item;
                }
                else
                {   /* closure item, add to closure list */
                    if (closure_root == NULL)
                        closure_root = new_item;
                    else
                        closure_tail -> next = new_item;
                    closure_tail = new_item;
                }
            }
        }

        if  (closure_root != NULL) /* any non-complete closure items? */
        {
            /* construct list of them and kernel items */
            closure_tail -> next = state -> kernel_items;
            item_ptr = closure_root;
        }
        else  /* else just consider kernel items */
            item_ptr = state -> kernel_items;

        /*******************************************************************/
        /*   In this loop, the PARTITION map is constructed. At this point,*/
        /* ITEM_PTR points to all the non_complete items in the closure of */
        /* the state, plus all the kernel items.  We note that the kernel  */
        /* items may still contain complete-items, and if any is found, the*/
        /* COMPLETE_ITEMS list is updated.                                 */
        /*******************************************************************/
        root = NIL;
        for (; item_ptr != NULL; item_ptr = item_ptr -> next)
        {
            item_no = item_ptr -> value;
            symbol = item_table[item_no].symbol;
            if (symbol != empty)  /* incomplete item */
            {
                next_item_no = item_no + 1;
                
                if (partition[symbol] == NULL)
                {   /* PARTITION not defined on symbol */
                    list[symbol] = root;  /* add to list */
                    root = symbol;
                    if (symbol IS_A_TERMINAL) /* Update transition count */
                        shift_size++;
                    else
                        goto_size++;
                }
                for (p = partition[symbol];
                     p != NULL;
                     tail = p, p = p -> next)
                {
                    if (p -> value > next_item_no)
                        break;