resolve.c

一个非常好的检索工具

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

/***********************************************************************/
/* VISITED is a structure used to mark state-symbol pairs that have    */
/* been visited in the process of computing follow-sources for a       */
/* given action in conflict.                                           */
/* The field MAP is an array indexable by the states 1..NUM_STATES;    */
/* each element of which points to a set (list) of symbols. Thus, for  */
/* a given state S, and for all symbol X in the list MAP[S], [S,X]     */
/* has been visited. For efficiency, the fields LIST and ROOT are used */
/* to store the set (list) of indexed elements of MAP that are not     */
/* NULL.                                                               */
/* See routines MARK_VISITED, WAS_VISITED, CLEAR_VISITED,              */
/*              INIT_LALRK_PROCESS, EXIT_PROCESS                       */
/***********************************************************************/
static struct visited_element
{
    struct node **map;
    short        *list,
                  root;
} visited;

/***********************************************************************/
/* Given a set of actions that are in conflict on a given symbol, the  */
/* structure SOURCES_ELEMENT is used to store a mapping from each      */
/* such action into a set of configurations that can be reached        */
/* following execution of the action in question up to the point where */
/* the automaton is about to shift the conflict symbol.                */
/* The field CONFIGS is an array indexable by actions which are        */
/* encoded as follows:                                                 */
/*    1. shift-reduce  [-NUM_RULES..-1]                                */
/*    2. reduce        [0..NUM_RULES]                                  */
/*    3. shift         [NUM_RULES+1..NUM_STATES+1].                    */
/* Each element of CONFIGS points to a set (sorted list) of            */
/* configurations.  For efficiency, the fields LIST and ROOT are used  */
/* to store the set (list) of indexed elements of CONFIGS that are not */
/* NULL.                                                               */
/* See routines ALLOCATE_SOURCES, FREE_SOURCES, CLEAR_SOURCES,         */
/*              ADD_CONFIGS, UNION_CONFIG_SETS.                        */
/* See STATE_TO_RESOLVE_CONFLICTS for an explanation of STACK_SEEN.    */
/*                                                                     */
/* A configuration is a stack of states that represents a certain path */
/* in the automaton. The stack is implemented as a list of             */
/* STACK_ELEMENT nodes linked through the field PREVIOUS.              */
/* A set/list of configurations is linked through the field NEXT.      */
/* When attempting to resolve conflicts we try to make sure that the   */
/* set of configurations associated with each action is unique. This   */
/* is achieved by throwing these configurations into a set and making  */
/* sure that there are no duplicates. The field LINK is used for that  */
/* purpose (see routine STACK_WAS_SEEN). The field STATE_NUMBER is     */
/* obviously used to store the number of a state in the automaton. The */
/* field SIZE holds index of the node within the stack. Thus, for the  */
/* first element of the stack this field represents the number of      */
/* elements in the stack; for the last element, this field holds the   */
/* value 1.                                                            */
/* See routines ALLOCATE_STACK_ELEMENT, FREE_STACK_ELEMENT,            */
/*              ADD_DANGLING_STACK, FREE_DANGLING_STACK.               */
/***********************************************************************/
static struct sources_element
{
    struct stack_element **configs,
                         **stack_seen;
    short                 *list,
                           root;
} sources;

struct stack_element
{
    struct stack_element *previous,
                         *next,
                         *link;
    short                 state_number,
                          size;
};
static struct stack_element *stack_pool = NULL,
                            *dangling_stacks = NULL;

/***********************************************************************/
/* The structure STATE_ELEMENT is used to construct lookahead states.  */
/* LA_STATE_ROOT point to a list of lookahead states using the LINK    */
/* field. The field NEXT_SHIFT is used to hash the new shift maps      */
/* associated with lookahead states. The field IN_STATE identifies the */
/* state that shifted into the lookahead state in question. The field  */
/* SYMBOL identifies the symbol on shift the transition was made into  */
/* the lookahead state in question.  The remaining fields are          */
/* self-explanatory.                                                   */
/***********************************************************************/
struct state_element
{
    struct state_element      *link,
                              *next_shift;
    struct reduce_header_type  reduce;
    struct shift_header_type   shift;
    short                      in_state,
                               symbol,
                               state_number,
                               shift_number;
};
static struct state_element *la_state_root = NULL;

/***********************************************************************/
/* The structures SR_CONFLICT_ELEMENT and RR_CONFLICT_ELEMENT are used */
/* th store conflict information. CONFLICT_ELEMENT_POOL is used to     */
/* keep track of a pool conflict element structures (SR or RR) that    */
/* are available for allocation.                                       */
/* See routines ALLOCATE_CONFLICT_ELEMENT and FREE_CONFLICT_ELEMENTS.  */
/***********************************************************************/
struct sr_conflict_element
{
    struct sr_conflict_element *next;
    short                       state_number,
                                item,
                                symbol;
};
static struct sr_conflict_element *sr_conflict_root;

struct rr_conflict_element
{
    struct rr_conflict_element *next;
    short                       symbol,
                                item1,
                                item2;
};
static struct rr_conflict_element *rr_conflict_root;
static void *conflict_element_pool = NULL;

/***********************************************************************/
/* NT_ITEMS and ITEM_LIST are used to construct a mapping from each    */
/* nonterminal into the set of items of which the nonterminal in       */
/* question is the dot symbol. See CONFLICTS_INITIALIZATION.           */
/***********************************************************************/
static short *nt_items  = NULL,
             *item_list = NULL;

/***********************************************************************/
/* LALR_VISITED is used to keep track of (state, nonterminal) pairs    */
/* that are visited in tracing the path of a lalr conflict.SLR_VISITED */
/* is similarly used to keep track of nonterminal symbols that are     */
/* visited in tracing the path of an slr conflict. SYMBOL_SEEN is used */
/* to keep track of nonterminal symbols that are visited in tracing a  */
/* path to the start state (root).                                     */
/*                                                                     */
/* CYCLIC is a boolean vector used to identify states that can enter   */
/* a cycle of transitions on nullable nonterminals.                    */
/* As the computation of CYCLIC requires a modified version of the     */
/* digraph algorithm, the variables STACK, INDEX_OF and TOP are used   */
/* for that algorithm.                                                 */
/*                                                                     */
/* RMPSELF is a boolean vector that indicates whether or not a given   */
/* non-terminal can right-most produce itself. It is only constructed  */
/* when LALR_LEVEL > 1.                                                */
/***********************************************************************/
static BOOLEAN *lalr_visited,
               *slr_visited,
               *symbol_seen,
               *cyclic,
               *rmpself;

static short *stack,
             *index_of,
              top;

static struct state_element **shift_table;

/*******************************************************************/
/*                     ALLOCATE_CONFLICT_ELEMENT:                  */
/*******************************************************************/
/* This function allocates a conflict_element (sr or rr) structure */
/* & returns a pointer to it. If there are nodes in the free pool, */
/* one of them is returned. Otherwise, a new node is allocated     */
/* from the temporary storage pool.                                */
/*******************************************************************/
static void *allocate_conflict_element(void)
{
    void *p;

    p = conflict_element_pool;
    if (p != NULL)
        conflict_element_pool = ((struct sr_conflict_element *) p) -> next;
    else
    {
        p = (void *) talloc(MAX(sizeof(struct sr_conflict_element),
                            sizeof(struct rr_conflict_element)));
        if (p == NULL)
            nospace(__FILE__, __LINE__);
    }

    return p;
}


/**********************************************************************/
/*                         FREE_CONFLICT_ELEMENTS:                    */
/**********************************************************************/
/* This routine returns a list of conflict_element (sr/rr)structures  */
/* to the free pool.                                                  */
/**********************************************************************/
static void free_conflict_elements(void *head, void *tail)
{
    ((struct sr_conflict_element *) tail) -> next =
             (struct sr_conflict_element *) conflict_element_pool;
    conflict_element_pool = head;

    return;
}


/*******************************************************************/
/*                      ALLOCATE_STACK_ELEMENT:                    */
/*******************************************************************/
/* This function allocates a stack_element structure and returns a */
/* pointer to it. If there are nodes in the free pool, one of them */
/* is returned. Otherwise, a new node is allocated from the        */
/* temporary storage pool.                                         */
/*******************************************************************/
static struct stack_element *allocate_stack_element(void)
{
    struct stack_element *p;

    p = stack_pool;
    if (p != NULL)
        stack_pool = p -> next;
    else
    {
        p = (struct stack_element *)
            talloc(sizeof(struct stack_element));
        if (p == NULL)
            nospace(__FILE__, __LINE__);
    }

    return p;
}


/**********************************************************************/
/*                           FREE_STACK_ELEMENTS:                     */
/**********************************************************************/
/* This routine returns a list of stack_element structures to the     */
/* free pool.                                                         */
/**********************************************************************/
static void free_stack_elements(struct stack_element *head,
                                struct stack_element *tail)
{
    tail -> next = stack_pool;
    stack_pool = head;

    return;
}


/***************************************************************************/
/*                        ADD_DANGLING_STACK_ELEMENT:                      */
/***************************************************************************/
/* When an allocated stack_element structure is not directly associated    */
/* with an action, it is added to a circular list of dangling stack_element*/
/* nodes so that its space can be reclaimed.                               */
/***************************************************************************/
static void add_dangling_stack_element(struct stack_element *s)
{
    if (dangling_stacks == NULL)
        s -> next = s;
    else
    {
        s -> next = dangling_stacks -> next;
        dangling_stacks -> next = s;
    }
    dangling_stacks = s;

    return;
}


/***************************************************************************/
/*                       FREE_DANGLING_STACK_ELEMENTS:                     */
/***************************************************************************/
/* This function is invoked to free up all dangling stack_element nodes    */
/* and reset the dangling stack list.                                      */
/* Recall that the dangling stack list is circular.                        */
/***************************************************************************/
static void free_dangling_stack_elements(void)
{
    struct stack_element *tail;

    if (dangling_stacks != NULL)
    {
        tail = dangling_stacks;
        free_stack_elements(dangling_stacks -> next, tail);

        dangling_stacks = NULL;
    }

    return;
}


/***************************************************************************/
/*                              ALLOCATE_SOURCES:                          */
/***************************************************************************/
/* This function allocates and initializes a SOURCE_ELEMENT map.           */
/* See definition of SOURCE_ELEMENT above.                                 */
/***************************************************************************/
static struct sources_element allocate_sources(void)
{
    struct sources_element sources;

    sources.configs = (struct stack_element **)
                      calloc(num_rules + num_rules + num_states + 1,
                             sizeof(struct stack_element *));
    if (sources.configs == NULL)
        nospace(__FILE__, __LINE__);
    sources.configs += num_rules;

    sources.stack_seen = (struct stack_element **)