remsp.c

一个非常好的检索工具

/* $Id: remsp.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"

#define IS_SP_RHS(symbol)   (sp_rules[symbol] != NIL)
#define IS_SP_RULE(rule_no) (rule_list[rule_no] != OMEGA)

static int max_sp_state;

static struct action_element
{
    struct action_element *next;
    short symbol,
          action;
} **new_action;
static struct action_element *action_element_pool = NULL;

static struct update_action_element
{
    struct update_action_element *next;
    short symbol,
          action,
          state;
} **update_action;

static struct sp_state_element
{
    struct sp_state_element *next,
                            *link;
    struct action_element   *action_root;
    struct node             *rule_root,
                            *complete_items;
    short                    state_number,
                             rule_count,
                             action_count;
} **sp_table;
static struct sp_state_element *sp_state_root;

static short *sp_rules,
             *stack,
             *index_of,
             *next_rule,
             *rule_list,

             **sp_action;

static BOOLEAN *is_conflict_symbol;

static SET_PTR look_ahead;

static int top,
           symbol_root,
           rule_root;

/**********************************************************************/
/*                        ALLOCATE_ACTION_ELEMENT:                    */
/**********************************************************************/
/* This function first tries to recycle an action_element node from a */
/* free list. If the list is empty a new node is allocated from       */
/* temporary storage.                                                 */
/**********************************************************************/
static struct action_element* allocate_action_element(void)
{
    struct action_element *p;

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

    return p;
}


/**********************************************************************/
/*                          FREE_ACTION_ELEMENTS:                     */
/**********************************************************************/
/* This routine returns a list of action_element structures to the    */
/* free list.                                                         */
/**********************************************************************/
static void free_action_elements(struct action_element *head,
                                 struct action_element *tail)
{
    tail -> next = action_element_pool;
    action_element_pool = head;

    return;
}


/**********************************************************************/
/*                             COMPUTE_SP_MAP:                        */
/**********************************************************************/
/* Compute_sp_map is an instantiation of the digraph algorithm. It    */
/* is invoked repeatedly by remove_single_productions to:             */
/*                                                                    */
/*   1) Partially order the right-hand side of all the single         */
/*      productions (SP) into a list [A1, A2, A3, ..., An]            */
/*      such that if Ai -> Aj then i < j.                             */
/*                                                                    */
/*   2) As a side effect, it uses the ordering above to order all     */
/*      the SP rules.                                                 */
/*                                                                    */
/**********************************************************************/
static void compute_sp_map(int symbol)
{
    int indx;
    int i,
        lhs_symbol,
        rule_no;

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

/**********************************************************************/
/* In this instantiation of the digraph algorithm, two symbols (A, B) */
/* are related if  A -> B  is a SP and A is the right-hand side of    */
/* some other SP rule.                                                */
/**********************************************************************/
    for (rule_no = sp_rules[symbol];
         rule_no != NIL; rule_no = next_rule[rule_no])
    {
        lhs_symbol = rules[rule_no].lhs;
        if (IS_SP_RHS(lhs_symbol))
        {
            if (index_of[lhs_symbol] == OMEGA)
                compute_sp_map(lhs_symbol);

            index_of[symbol] = MIN(index_of[symbol],
                                   index_of[lhs_symbol]);
        }
    }

/**********************************************************************/
/* If the index of symbol is the same index it started with then      */
/* symbol if the root of a SCC...                                     */
/**********************************************************************/
    if (index_of[symbol] == indx)
    {
        /**************************************************************/
        /* If symbol is on top of the stack then it is the only       */
        /* symbol in its SCC (thus it is not part of a cycle).        */
        /* Note that since remove_single_productions is only invoked  */
        /* when the input grammar is conflict-free, the graph of      */
        /* the single productions will never contain any cycle.       */
        /* Thus, this test will always succeed and all single         */
        /* productions associated with the symbol being processed     */
        /* are added to the list of SP rules here...                  */
        /**************************************************************/
        if (stack[top] == symbol)
        {
            for (rule_no = sp_rules[symbol];
                 rule_no != NIL; rule_no = next_rule[rule_no])
            {
                if (rule_root == NIL)
                    rule_list[rule_no] = rule_no;
                else
                {
                    rule_list[rule_no] = rule_list[rule_root];
                    rule_list[rule_root] = rule_no;
                }
                rule_root = rule_no;
            }
        }

        /**************************************************************/
        /* As all SCC contains exactly one symbol (as explained above)*/
        /* this loop will always execute exactly once.                */
        /**************************************************************/
        do
        {
            i = stack[top--];
            index_of[i] = INFINITY;
        } while(i != symbol);
    }

    return;
}


/**********************************************************************/
/*                         COMPUTE_SP_ACTION:                         */
/**********************************************************************/
/* When the parser enters STATE_NO and it is processing SYMBOL, its   */
/* next move is ACTION. Given these 3 parameters, compute_sp_action   */
/* computes the set of reduce actions that may be executed after      */
/* SYMBOL is shifted in STATE_NO.                                     */
/*                                                                    */
/* NOTE that this algorithm works only for the LALR(1) case. When the */
/* transition on SYMBOL is a lookahead-shift, indicating that the     */
/* parser requires extra lookahead on a particular symbol, the set of */
/* reduce actions for that symbol is calculated as the empty set.     */
/**********************************************************************/
static void compute_sp_action(short state_no, short symbol, short action)
{
    struct goto_header_type go_to;

    struct node *item_ptr;
    int item_no,
        rule_no,
        lhs_symbol,
        i,
        k;

    BOOLEAN end_node;

    struct node *p;

    go_to = statset[state_no].go_to;

    if (sp_action[symbol] == NULL)
        sp_action[symbol] = Allocate_short_array(num_terminals + 1);

    for ALL_TERMINALS(i) /* initialize sp_action to the empty map */
        sp_action[symbol][i] = OMEGA;

/**********************************************************************/
/* Note that before this routine is invoked, the global vector        */
/* index_of identifies the index of each symbol in the goto map of    */
/* state_no.                                                          */
/**********************************************************************/
    if (is_conflict_symbol[symbol])             /* do nothing */
        ;
    else if (action > 0) /* transition action (shift or goto) */
    {
        for (item_ptr = statset[action].complete_items;
             item_ptr != NULL; item_ptr = item_ptr -> next)
        {
            item_no = item_ptr -> value;
            rule_no = item_table[item_no].rule_number;
            lhs_symbol = rules[rule_no].lhs;
            if (RHS_SIZE(rule_no) == 1 && lhs_symbol != accept_image)
            {
                if (slr_bit)
                {
                    ASSIGN_SET(look_ahead, 0, follow, lhs_symbol);
                }
                else
                {
                    i = index_of[lhs_symbol];
                    k = GOTO_LAPTR(go_to, i);
                    if (la_index[k] == OMEGA)
                    {
                        int stack_top = 0;
                        la_traverse(state_no, i, &stack_top);
                    }
                    ASSIGN_SET(look_ahead, 0, la_set, k);
                }
                RESET_BIT(look_ahead, empty); /* empty not valid look-ahead */

                for ALL_TERMINALS(i)
                {
                    if (IS_ELEMENT(look_ahead, i))
                        sp_action[symbol][i] = rule_no;
                }
            }
        }

        /**************************************************************/
        /* Remove all lookahead symbols on which conflicts were       */
        /* detected from consideration.                               */
        /**************************************************************/
        for (end_node = ((p = conflict_symbols[action]) == NULL);
             ! end_node; end_node = (p == conflict_symbols[action]))
        {
            p = p -> next;
            sp_action[symbol][p -> value] = OMEGA;
        }
    }
    else /* read-reduce action */
    {
        rule_no = -action;
        if (RHS_SIZE(rule_no) == 1)
        {
            lhs_symbol = rules[rule_no].lhs;

            if (slr_bit)
            {
                ASSIGN_SET(look_ahead, 0, follow, lhs_symbol);
            }
            else
            {
                i = index_of[lhs_symbol];
                k = GOTO_LAPTR(go_to, i);
                if (la_index[k] == OMEGA)
                {
                    int stack_top = 0;
                    la_traverse(state_no, i, &stack_top);
                }
                ASSIGN_SET(look_ahead, 0, la_set, k);
            }
            RESET_BIT(look_ahead, empty); /* empty not valid look-ahead */

            for ALL_TERMINALS(i)
            {
                if (IS_ELEMENT(look_ahead, i))
                    sp_action[symbol][i] = rule_no;
            }