mkstates.c

一个非常好的检索工具

                }

                r = Allocate_node();
                r -> value = next_item_no;
                r -> next = p;

                if (p == partition[symbol]) /* Insert at beginning */
                    partition[symbol] = r;
                else
                    tail -> next = r;
            }
            else /* Update complete item set with item from kernel */
            {
                 p = Allocate_node();
                 p -> value = item_no;
                 p -> next = state -> complete_items;
                 state -> complete_items = p;
            }
        }
        if (closure_root != NULL)
            free_nodes(closure_root, closure_tail);

        /*******************************************************************/
        /* We now iterate over the set of partitions and update the state  */
        /* automaton and the transition maps: SHIFT and GOTO. Each         */
        /* partition represents the kernel of a state.                     */
        /*******************************************************************/
        if (goto_size > 0)
        {
            go_to = Allocate_goto_map(goto_size);
            state -> lr0_goto = go_to;
        }
        else
            state -> lr0_goto = no_gotos_ptr;

        shift_root = NIL;
        for (symbol = root;
             symbol != NIL; /* symbols on which transition is defined */
             symbol = list[symbol])
        {
            short action = OMEGA;

            /*****************************************************************/
            /* If the partition contains only one item, and it is adequate   */
            /* (i.e. the dot immediately follows the last symbol), and       */
            /* READ-REDUCE is requested, a new state is not created, and the */
            /* action is marked as a Shift-reduce or a Goto-reduce. Otherwise*/
            /* if a state with that kernel set does not yet exist, we create */
            /* it.                                                           */
            /*****************************************************************/
            q = partition[symbol]; /* kernel of a new state */
            if (read_reduce_bit && q -> next == NULL)
            {
                item_no = q -> value;
                if (item_table[item_no].symbol == empty)
                {
                    rule_no = item_table[item_no].rule_number;
                    if (rules[rule_no].lhs != accept_image)
                    {
                        action = -rule_no;
                        free_nodes(q, q);
                    }
                }
            }

            if (action == OMEGA) /* Not a Read-Reduce action */
            {
                new_state = lr0_state_map(q);
                action = new_state -> state_number;
            }

            /****************************************************************/
            /* At this stage, the partition list has been freed (for an old */
            /* state or an ADEQUATE item), or used (for a new state).  The  */
            /* PARTITION field involved should be reset.                    */
            /****************************************************************/
            partition[symbol] = NULL;           /* To be reused */

            /*****************************************************************/
            /* At this point, ACTION contains the value of the state to Shift*/
            /* to, or rule to Read-Reduce on. If the symbol involved is a    */
            /* terminal, we update the Shift map; else, it is a non-terminal */
            /* and we update the Goto map.                                   */
            /* Shift maps are constructed temporarily in SHIFT_ACTION.       */
            /* Later, they are inserted into a map of unique Shift maps, and */
            /* shared by states that contain identical shifts.               */
            /* Since the lookahead set computation is based on the GOTO maps,*/
            /* all these maps and their element maps should be kept as       */
            /* separate entities.                                            */
            /*****************************************************************/
            if (symbol IS_A_TERMINAL) /* terminal? add to SHIFT map */
            {
                shift_action[symbol] = action;
                shift_list[symbol] = shift_root;
                shift_root = symbol;
                if (action > 0)
                    num_shifts++;
                else
                    num_shift_reduces++;
            }

            /*****************************************************************/
            /* NOTE that for Goto's we update the field LA_PTR of GOTO. This */
            /* field will be used later in the routine MKRDCTS to point to a */
            /* look-ahead set.                                               */
            /*****************************************************************/
            else
            {
                GOTO_SYMBOL(go_to, goto_size) = symbol; /* symbol field */
                GOTO_ACTION(go_to, goto_size) = action; /* state field  */
                GOTO_LAPTR(go_to,  goto_size) = OMEGA;  /* la_ptr field */
                goto_size--;
                if (action > 0)
                    num_gotos++;
                else
                    num_goto_reduces++;
            }
        }

        /*******************************************************************/
        /* We are now going to update the set of Shift-maps. Ths idea is   */
        /* to do a look-up in a hash table based on SHIFT_TABLE to see if  */
        /* the Shift map associated with the current state has already been*/
        /* computed. If it has, we simply update the SHIFT_NUMBER and the  */
        /* SHIFT field of the current state. Otherwise, we allocate and    */
        /* construct a SHIFT_ELEMENT map, update the current state, and    */
        /* add it to the set of Shift maps in the hash table.              */
        /*   Note that the SHIFT_NUMBER field in the STATE_ELEMENTs could  */
        /* have been factored out and associated instead with the          */
        /* SHIFT_ELEMENTs. That would have saved some space, but only in   */
        /* the short run. This field was purposely stored in the           */
        /* STATE_ELEMENTs, because once the states have been constructed,  */
        /* they are not kept, whereas the SHIFT_ELEMENTs are kept.         */
        /*    One could have also threaded through the states that contain */
        /* original shift maps so as to avoid duplicate assignments in     */
        /* creating the SHIFT map later. However, this would have          */
        /* increased the storage requirement, and would probably have saved*/
        /* (at most) a totally insignificant amount of time.               */
        /*******************************************************************/
update_shift_maps:
        {
            unsigned long hash_address;

            struct shift_header_type sh;

            struct state_element *p;

            hash_address = shift_size;
            for (symbol = shift_root;
                 symbol != NIL; symbol = shift_list[symbol])
            {
                hash_address += ABS(shift_action[symbol]);
            }
            hash_address %= SHIFT_TABLE_SIZE;

            for (p = shift_table[hash_address];
                 p != NULL; /* Search has table for shift map */
                 p = p -> next_shift)
            {
                sh = p -> lr0_shift;
                if (sh.size == shift_size)
                {
                    for (i = 1; i <= shift_size; i++) /* Compare shift maps */
                    {
                        if (SHIFT_ACTION(sh, i) !=
                            shift_action[SHIFT_SYMBOL(sh, i)])
                            break;
                    }

                    if (i > shift_size)  /* Are they equal ? */
                    {
                        state -> lr0_shift    = sh;
                        state -> shift_number = p -> shift_number;
                        for (symbol = shift_root;
                             symbol != NIL; symbol = shift_list[symbol])
                        { /* Clear SHIFT_ACTION */
                            shift_action[symbol] = OMEGA;
                        }
                        shift_size = 0;   /* Reset for next round */
                        goto leave_update_shift_maps;
                    }
                }
            }

            if (shift_size > 0)
            {
                sh = Allocate_shift_map(shift_size);
                num_shift_maps++;
                state -> shift_number = num_shift_maps;
            }
            else
            {
                state -> shift_number = 0;
                sh = no_shifts_ptr;
            }

            state -> lr0_shift = sh;
            state -> next_shift = shift_table[hash_address];
            shift_table[hash_address] = state;

            for (symbol = shift_root;
                 symbol != NIL; symbol = shift_list[symbol])
            {
                SHIFT_SYMBOL(sh, shift_size) = symbol;
                SHIFT_ACTION(sh, shift_size) = shift_action[symbol];
                shift_action[symbol] = OMEGA;
                shift_size--;
            }
        } /*end update_shift_maps */

leave_update_shift_maps:;
    }

    /*********************************************************************/
    /* Construct STATSET, a "compact" and final representation of        */
    /* State table, and SHIFT which is a set of all shift maps needed.   */
    /* NOTE that assignments to elements of SHIFT may occur more than    */
    /* once, but that's ok. It is probably faster to  do that than to    */
    /* set up an elaborate scheme to avoid the multiple assignment which */
    /* may in fact cost more.  Look at it this way: it is only a pointer */
    /* assignment, namely a Load and a Store.                            */
    /* Release all NODEs used by  the maps CLITEMS and CLOSURE.          */
    /*********************************************************************/
    {
        struct state_element *p;

    /*********************************************************************/
    /* If the grammar is LALR(k), k > 1, more states may be added and    */
    /* the size of the shift map increased.                              */
    /*********************************************************************/
        shift = (struct shift_header_type *)
                calloc(num_states + 1, sizeof(struct shift_header_type));
        if (shift == NULL)
            nospace(__FILE__, __LINE__);
        shift[0] = no_shifts_ptr;        /* MUST be initialized for LALR(k) */
        statset = (struct statset_type *)
                  calloc(num_states + 1, sizeof(struct statset_type));
        if (statset == NULL)
            nospace(__FILE__, __LINE__);

        for (p = state_root; p != NULL; p = p -> queue)
        {
            state_no = p -> state_number;
            statset[state_no].kernel_items = p -> kernel_items;
            statset[state_no].complete_items = p -> complete_items;
            shift[p -> shift_number] = p -> lr0_shift;
            statset[state_no].shift_number = p -> shift_number;
            statset[state_no].go_to = p -> lr0_goto;
        }
    }

    ffree(list);
    ffree(shift_action);
    ffree(shift_list);
    nt_list += (num_terminals + 1);
    ffree(nt_list);
    ffree(partition);
    ffree(state_table);
    ffree(shift_table);

    return;
}


/*****************************************************************************/
/*                            LR0_STATE_MAP:                                 */
/*****************************************************************************/
/* LR0_STATE_MAP takes as an argument a pointer to a kernel set of items. If */
/* no state based on that kernel set already exists, then a new one is       */
/* created and added to STATE_TABLE. In any case, a pointer to the STATE of  */
/* the KERNEL is returned.                                                   */
/*****************************************************************************/
static struct state_element *lr0_state_map(struct node *kernel)
{
    unsigned long hash_address = 0;
    struct node *p;
    struct state_element *state_ptr,
                         *ptr;

    /*********************************************/
    /*       Compute the hash address.           */
    /*********************************************/
    for (p = kernel; p != NULL; p = p -> next)
    {
        hash_address += p -> value;
    }
    hash_address %= STATE_TABLE_SIZE;

    /*************************************************************************/
    /* Check whether a state is already defined by the KERNEL set.           */
    /*************************************************************************/
    for (state_ptr = state_table[hash_address];
         state_ptr != NULL; state_ptr = state_ptr -> link)
    {
        struct node *q,
                    *r;

        for (p = state_ptr -> kernel_items, q = kernel;
             p != NULL && q != NULL;
             p = p -> next, r = q, q = q -> next)
        {
            if (p -> value != q -> value)
                break;
        }

        if (p == q)  /* Both P and Q are NULL? */
        {
            free_nodes(kernel, r);
            return(state_ptr);
        }
    }


    /*******************************************************************/
    /* Add a new state based on the KERNEL set.                        */
    /*******************************************************************/
    ptr = (struct state_element *) talloc(sizeof(struct state_element));
    if (ptr == (struct state_element *) NULL)
        nospace(__FILE__, __LINE__);

    num_states++;
    SHORT_CHECK(num_states);
    ptr -> queue = NULL;
    ptr -> kernel_items = kernel;
    ptr -> complete_items = NULL;
    ptr -> state_number = num_states;
    ptr -> link = state_table[hash_address];
    state_table[hash_address] = ptr;
    if (state_root == NULL)
        state_root = ptr;
    else
        state_tail -> queue = ptr;

    state_tail = ptr;

    return(ptr);
}