resolve.c

一个非常好的检索工具

            }
        }
    }

    return configs;
}


/***********************************************************************/
/*                                NEXT_LA:                             */
/***********************************************************************/
/* This function has a similar structure as FOLLOW_SOURCES.  But,      */
/* instead of computing configurations that can be reached, it         */
/* computes lookahead symbols that can be reached.  It takes as        */
/* argument a configuration STACK, a SYMBOL on which a transition can  */
/* be made in the configuration and a set variable, LOOK_AHEAD, where  */
/* the result is to be stored.  When NEXT_LA is invoked from the       */
/* outside, LOOK_AHEAD is assumed to be initialized to the empty set.  */
/* NEXT_LA first executes the transition on SYMBOL and thereafter, all */
/* terminal symbols that can be read are added to LOOKAHEAD.           */
/***********************************************************************/
static void next_la(struct stack_element *stack,
                    int symbol, SET_PTR look_ahead)
{
    struct shift_header_type sh;
    struct goto_header_type  go_to;

    struct stack_element *q;
    struct node *item_ptr;

    int item_no,
        state_no,
        rule_no,
        lhs_symbol,
        act,
        i;

    /*******************************************************************/
    /* The only symbol that can follow the end-of-file symbol is the   */
    /* end-of-file symbol.                                             */
    /*******************************************************************/
    if (symbol == eoft_image)
    {
        SET_BIT_IN(look_ahead, 0, eoft_image);
        return;
    }

    state_no = stack -> state_number;

    /*******************************************************************/
    /* Find the transition defined on the symbol...                    */
    /*******************************************************************/
    if (symbol IS_A_NON_TERMINAL)
    {
        go_to = statset[state_no].go_to;
        for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
            ;
        act = GOTO_ACTION(go_to, i);
    }
    else
    {
        sh = shift[statset[state_no].shift_number];
        for (i = 1; SHIFT_SYMBOL(sh, i) != symbol; i++)
            ;
        act = SHIFT_ACTION(sh, i);
    }

    /*******************************************************************/
    /* If the ACTion on the symbol is a shift or a goto, then all      */
    /* terminal symbols that can be read in ACT are added to           */
    /* LOOK_AHEAD.                                                     */
    /*******************************************************************/
    if (act > 0)
    {
        SET_UNION(look_ahead, 0, read_set, act);
    }

    /*******************************************************************/
    /* We now iterate over the kernel set of items associated with the */
    /* ACTion defined on SYMBOL...                                     */
    /* Recall that the READ_SET of ACT is but the union of the FIRST   */
    /* map defined on the suffixes of the items in the kernel of ACT.  */
    /*******************************************************************/
    for (item_ptr = (act > 0 ? statset[act].kernel_items
                             : adequate_item[-act]);
         item_ptr != NULL; item_ptr = item_ptr -> next)
    {
        item_no = item_ptr -> value;

        /***************************************************************/
        /* For each item that is a final item whose left-hand side     */
        /* is neither the starting symbol nor a symbol that can        */
        /* right-most produce itself...                                */
        /***************************************************************/
        if (IS_IN_SET(first, item_table[item_no - 1].suffix_index, empty))
        {
            rule_no = item_table[item_no].rule_number;
            lhs_symbol = rules[rule_no].lhs;
            if (lhs_symbol != accept_image && ! rmpself[lhs_symbol])
            {
                /*******************************************************/
                /* If the length of the prefix of the item preceeding  */
                /* the dot is shorter that the length of the stack, we */
                /* retrace the item's path within the stack and        */
                /* invoke NEXT_LA with the prefix of the stack         */
                /* where the item was introduced through closure, the  */
                /* left-hand side of the item and LOOK_AHEAD.          */
                /*******************************************************/
                if (item_table[item_no].dot < stack -> size)
                {
                    q = stack;
                    for (i = 1; i < item_table[item_no].dot; i++)
                        q = q -> previous;
                    next_la(q, lhs_symbol, look_ahead);
                }
                else
                {
                    struct node *v,
                                *p,
                                *tail;

                    /***************************************************/
                    /* Compute the item in the root state of the stack,*/
                    /* and find the root state...                      */
                    /***************************************************/
                    item_no -= stack -> size;
                    for (q = stack; q -> size != 1; q = q -> previous)
                        ;

                    /***************************************************/
                    /* We are now back in the main automaton, find all */
                    /* sources where the item was introduced through   */
                    /* closure and add all terminal symbols in the     */
                    /* follow set of the left-hand side symbol in each */
                    /* source to LOOK_AHEAD.                           */
                    /***************************************************/
                    v = lpgaccess(q -> state_number, item_no);
                    for (p = v; p != NULL; tail = p, p = p -> next)
                    {
                        go_to = statset[p -> value].go_to;
                        for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
                            ;

                        /***********************************************/
                        /* If look-ahead after left hand side is not   */
                        /* yet computed,call LA_TRAVERSE to compute it.*/
                        /***********************************************/
                        if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
                        {
                            int stack_top = 0;
                            la_traverse(p -> value, i, &stack_top);
                        }

                        SET_UNION(look_ahead, 0,
                                  la_set, GOTO_LAPTR(go_to, i));
                    }

                    free_nodes(v, tail);
                }
            }
        }
    }

    return;
}


/***********************************************************************/
/*                              STACK_WAS_SEEN:                        */
/***********************************************************************/
/* This function takes as argument an array, STACK_SEEN, with          */
/* STATE_TABLE_SIZE elements (indexable in the range                   */
/* 0..STATE_TABLE_SIZE-1) which is the base of a hash table and a      */
/* STACK. It searches the hash table to see if it already contained    */
/* the stack in question. If yes, it returns TRUE. Otherwise, it       */
/* inserts the stack into the table and returns FALSE.                 */
/***********************************************************************/
static BOOLEAN stack_was_seen(struct stack_element **stack_seen,
                              struct stack_element *stack)
{
    unsigned long hash_address;
    struct stack_element *p,
                         *q,
                         *r;

    hash_address = stack -> size;   /* Initialize hash address */
    for (p = stack; p != NULL; p = p -> previous)
        hash_address += p -> state_number;
    hash_address %= STATE_TABLE_SIZE;

    for (p = stack_seen[hash_address]; p != NULL; p = p -> link)
    {
        if (stack -> size == p -> size)
        {
            for (q = stack, r = p;
                 q != NULL;
                 q = q -> previous, r = r -> previous)
            {
                if (q -> state_number != r -> state_number)
                    break;
            }
            if (q == NULL)
                return TRUE;
        }
    }

    stack -> link = stack_seen[hash_address];
    stack_seen[hash_address] = stack;

    return FALSE;
}


/***********************************************************************/
/*                      STATE_TO_RESOLVE_CONFLICTS:                    */
/***********************************************************************/
/* STATE_TO_RESOLVE_CONFLICTS is a function that attempts to resolve   */
/* conflicts by doing more look-ahead.  If the conflict resolution     */
/* is successful, then a new state is created and returned; otherwise, */
/* the NULL pointer is returned.                                       */
/***********************************************************************/
static struct state_element *state_to_resolve_conflicts
       (struct sources_element sources, int la_symbol, int level)
{
    struct sources_element new_sources;

    struct node **action,
                 *p,
                 *tail;

    short *symbol_list,
          *action_list,
          *rule_count,
           symbol_root,
           shift_root,
           reduce_root;

    SET_PTR look_ahead;

    struct stack_element *stack;

    struct state_element **la_shift_state,
                          *state;

    int num_shift_actions,
        num_reduce_actions,
        default_rule,
        count,
        i,
        symbol,
        act;

    new_sources = allocate_sources();

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

    symbol_list = Allocate_short_array(num_terminals + 1);
    action_list = Allocate_short_array(num_terminals + 1);
    rule_count = Allocate_short_array(num_rules + 1);

    look_ahead = (SET_PTR)
                 calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
    if (look_ahead == NULL)
        nospace(__FILE__, __LINE__);

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

    /*******************************************************************/
    /* Initialize new lookahead state. Initialize counters. Check and  */
    /* adjust HIGHEST_LEVEL reached so far, if necessary.              */
    /*******************************************************************/
    state = NULL;

    num_shift_actions = 0;
    num_reduce_actions = 0;
    shift_root = NIL;
    reduce_root = NIL;

    if (level > highest_level)
        highest_level = level;

    /*******************************************************************/
    /* One of the parameters received is a SOURCES map whose domain is */
    /* a set of actions and each of these actions is mapped into a set */
    /* of configurations that can be reached after that action is      */
    /* executed (in the state where the conflicts were detected).      */
    /* In this loop, we compute an ACTION map which maps each each     */
    /* terminal symbol into 0 or more actions in the domain of SOURCES.*/
    /*                                                                 */
    /* NOTE in a sources map, if a configuration is associated with    */
    /* more than one action then the grammar is not LALR(k) for any k. */
    /* We check for that condition below. However, this check is there */
    /* for purely cosmetic reason. It is not necessary for the         */
    /* algorithm to work correctly and its removal will speed up this  */
    /* loop somewhat (for conflict-less input).                        */
    /* The first loop below initializes the hash table used for        */
    /* lookups ...                                                     */
    /*******************************************************************/
    for (i = 0; i < STATE_TABLE_SIZE; i++)
         sources.stack_seen[i] = NULL;

    symbol_root = NIL;
    for (act = sources.root; act != NIL; act = sources.list[act])
    {
        /***************************************************************/
        /* For each action we iterate over its associated set of       */
        /* configurations and invoke NEXT_LA to compute the lookahead  */
        /* set for that configuration. These lookahead sets are in     */
        /* turn unioned together to form a lookahead set for the       */
        /* action in question.                                         */
        /***************************************************************/
        INIT_SET(look_ahead);
        for (stack = sources.configs[act];
             stack != NULL; stack = stack -> next)
        {
            if (stack_was_seen(sources.stack_seen, stack))
            {/* This is the superfluo