ptables.c

一个非常好的检索工具

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

struct action_element
{
    struct action_element *next;
    short count,
          action;
};

/****************************************************************************/
/*                            PROCESS_SHIFT_ACTIONS:                        */
/****************************************************************************/
/* The array ACTION_COUNT is used to construct a map from each terminal     */
/* into the set (list) of actions defined on that terminal. A count of the  */
/* number of occurences of each action in the automaton is kept.            */
/* This procedure is invoked with a specific shift map which it processes   */
/* and updates the ACTION_COUNT map accordingly.                            */
/****************************************************************************/
static void process_shift_actions(struct action_element **action_count,
                                  int shift_no)
{
    struct shift_header_type sh;
    struct action_element *q;

    int symbol,
        act,
        i;

    sh = shift[shift_no];
    for (i = 1; i <= sh.size; i++)
    {
        symbol = SHIFT_SYMBOL(sh, i);
        act = SHIFT_ACTION(sh, i);
        for (q = action_count[symbol]; q != NULL; q = q -> next)
        {
            if (q -> action == act)
                break;
        }

        if (q == NULL) /* new action not yet seen */
        {
            q = (struct action_element *)
                talloc(sizeof(struct action_element));
            if (q == NULL)
                nospace(__FILE__, __LINE__);

            q -> action = act;
            q -> count = 1;
            q -> next = action_count[symbol];
            action_count[symbol] = q;
        }
        else (q -> count)++;
    }

    return;
}


/****************************************************************************/
/*                            COMPUTE_SHIFT_DEFAULT:                        */
/****************************************************************************/
/* This procedure updates the vector SHIFTDF, indexable by the terminals in */
/* the grammar. Its task is to assign to each element of SHIFTDF, the action*/
/* most frequently defined on the symbol in question.                       */
/****************************************************************************/
static void compute_shift_default(void)
{
    struct action_element **action_count,
                           *q;

    int state_no,
        symbol,
        default_action,
        max_count,
        shift_count = 0,
        shift_reduce_count = 0;

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

    shiftdf = Allocate_short_array(num_terminals + 1);

    action_count = (struct action_element **)
                   calloc(num_terminals + 1,
                          sizeof(struct action_element *));
    if (action_count == NULL)
        nospace(__FILE__, __LINE__);

    /*******************************************************************/
    /* For each state, invoke PROCESS_SHIFT_ACTIONS to process the     */
    /* shift map associated with that state.                           */
    /*******************************************************************/
    for ALL_STATES(state_no)
    {
        process_shift_actions(action_count,
                              statset[state_no].shift_number);
    }

    for ALL_LA_STATES(state_no)
    {
        process_shift_actions(action_count,
                              lastats[state_no].shift_number);
    }

    /*********************************************************************/
    /* We now iterate over the ACTION_COUNT mapping, and for each        */
    /* terminal t, initialize SHIFTDF[t] to the action that is most      */
    /* frequently defined on t.                                          */
    /*********************************************************************/
    for ALL_TERMINALS(symbol)
    {
        max_count = 0;
        default_action = 0;

        for (q = action_count[symbol]; q != NULL; q = q -> next)
        {
            if (q -> count > max_count)
            {
                max_count = q -> count;
                default_action = q -> action;
            }
        }

        shiftdf[symbol] = default_action;
        if (default_action > 0)  /* A state number ? */
            shift_count += max_count;
        else
            shift_reduce_count += max_count;
    }

    sprintf(msg_line,
            "Number of Shift entries saved by default: %d",
            shift_count);
    PRNT(msg_line);

    sprintf(msg_line,
            "Number of Shift/Reduce entries saved by default: %d",
            shift_reduce_count);
    PRNT(msg_line);

    num_shifts -= shift_count;
    num_shift_reduces -= shift_reduce_count;
    num_entries = num_entries - shift_count - shift_reduce_count;

    ffree(action_count);

    return;
}


/*****************************************************************************/
/*                             COMPUTE_GOTO_DEFAULT:                         */
/*****************************************************************************/
/*   COMPUTE_GOTO_DEFAULT constructs the vector GOTODEF, which is indexed by */
/* the non-terminals in the grammar. Its task is to assign to each element   */
/* of the array the Action which is most frequently defined on the symbol in */
/* question, and remove all such actions from the state automaton.           */
/*****************************************************************************/
static void compute_goto_default(void)
{
    struct goto_header_type go_to;

    struct action_element **action_count,
                           *q;

    int state_no,
        symbol,
        default_action,
        act,
        i,
        k,
        max_count,
        goto_count = 0,
        goto_reduce_count = 0;

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

    gotodef = Allocate_short_array(num_non_terminals);
    gotodef -= (num_terminals + 1);

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

    /*******************************************************************/
    /* The array ACTION_COUNT is used to construct a map from each     */
    /* non-terminal into the set (list) of actions defined on that     */
    /* non-terminal. A count of how many occurences of each action     */
    /* is also kept.                                                   */
    /* This loop is analoguous to the loop in PROCESS_SHIFT_ACTIONS.   */
    /*******************************************************************/
    for ALL_STATES(state_no)
    {
        go_to = statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
        {
            symbol = GOTO_SYMBOL(go_to, i);
            act = GOTO_ACTION(go_to, i);
            for (q = action_count[symbol]; q != NULL; q = q -> next)
            {
                if (q -> action == act)
                    break;
            }

            if (q == NULL) /* new action not yet seen */
            {
                q = (struct action_element *)
                    talloc(sizeof(struct action_element));
                if (q == NULL)
                    nospace(__FILE__, __LINE__);

                q -> action = act;
                q -> count = 1;
                q -> next = action_count[symbol];
                action_count[symbol] = q;
            }
            else (q -> count)++;
        }
    }

    /*******************************************************************/
    /* We now iterate over the mapping created above and for each      */
    /* non-terminal A, initialize GOTODEF(A) to the action that is     */
    /* most frequently defined on A.                                   */
    /*******************************************************************/
    for ALL_NON_TERMINALS(symbol)
    {
        max_count = 0;