resolve.c

一个非常好的检索工具

                         calloc(STATE_TABLE_SIZE,
                                sizeof(struct stack_element *));
    if (sources.stack_seen == NULL)
        nospace(__FILE__, __LINE__);

    sources.list =
        Allocate_short_array(num_rules + num_rules + num_states + 1);
    sources.list += num_rules;

    sources.root = NIL;

    return sources;
}


/***************************************************************************/
/*                               CLEAR_SOURCES:                            */
/***************************************************************************/
/* This function takes as argument a SOURCES_ELEMENT structure which it    */
/* resets to the empty map.                                                */
/* See definition of SOURCE_ELEMENT above.                                 */
/***************************************************************************/
static struct sources_element clear_sources(struct sources_element sources)
{
    struct stack_element *p,
                         *tail;
    int act,
        i;

    for (act = sources.root; act != NIL; act = sources.list[act])
    {
        for (p = sources.configs[act]; p != NULL; tail = p, p = p -> next)
            ;
        free_stack_elements(sources.configs[act], tail);
        sources.configs[act] = NULL;
    }

    sources.root = NIL;

    return sources;
}


/***************************************************************************/
/*                               FREE_SOURCES:                             */
/***************************************************************************/
/* This function takes as argument a SOURCES_ELEMENT structure. First, it  */
/* clears it to reclaim all space that was used by STACK_ELEMENTs and then */
/* it frees the array space used as a base to construct the map.           */
/***************************************************************************/
static void free_sources(struct sources_element sources)
{
    sources = clear_sources(sources);

    sources.configs -= num_rules;
    ffree(sources.configs);

    ffree(sources.stack_seen);

    sources.list -= num_rules;
    ffree(sources.list);

    return;
}


/***************************************************************************/
/*                             UNION_CONFIG_SETS:                          */
/***************************************************************************/
/* This function takes as argument two pointers to sorted lists of stacks. */
/* It merges the lists in the proper order and returns the resulting list. */
/***************************************************************************/
static struct stack_element *union_config_sets(struct stack_element *root1,
                                               struct stack_element *root2)
{
    struct stack_element *p1,
                         *p2,
                         *root,
                         *tail;

    root = NULL;

    /*******************************************************************/
    /* This loop iterates over both lists until one (or both) has been */
    /* completely processed. Each time around the loop, a stack is     */
    /* removed from one of the lists and possibly added to the new     */
    /* list. The new list is initially kept as a circular list to      */
    /* preserve the sorted ordering in which elements are added to it. */
    /*******************************************************************/
    while (root1 != NULL && root2 != NULL)
    {
        /***************************************************************/
        /* Compare the two stacks in front of the lists for equality.  */
        /* We exit this loop when we encounter the end of one (or both)*/
        /* of the stacks or two elements in them that are not the same.*/
        /***************************************************************/
        for (p1 = root1, p2 = root2;
             p1 != NULL && p2 != NULL;
             p1 = p1 -> previous, p2 = p2 -> previous)
        {
            if (p1 -> state_number != p2 -> state_number)
                break;
        }

        /***************************************************************/
        /* We now have 3 cases to consider:                            */
        /*    1. The two stacks are equal? Discard one!                */
        /*    2. List 1 stack is prefix of list 2 stack (p1 == NULL)?  */
        /*       or list 1 stack is less than list 2 stack?            */
        /*       Remove list 1 stack and add it to new list.           */
        /*    3. List 2 stack is either a prefix of list 1 stack, or   */
        /*       it is smaller!                                        */
        /*       Remove list 2 stack and add it to new list.           */
        /***************************************************************/
        if (p1 == p2) /* are both p1 and p2 NULL? */
        {
            p2 = root2;
            root2 = root2 -> next;
            add_dangling_stack_element(p2);
        }
        else if ((p1 == NULL) ||
                ((p2 != NULL) && (p1 -> state_number < p2 -> state_number)))
        {
            p1 = root1;
            root1 = root1 -> next;

            if (root == NULL)
                p1 -> next = p1;
            else
            {
                p1 -> next = root -> next;
                root -> next = p1;
            }
            root = p1;
        }
        else
        {
            p2 = root2;
            root2 = root2 -> next;

            if (root == NULL)
                p2 -> next = p2;
            else
            {
                p2 -> next = root -> next;
                root -> next = p2;
            }
            root = p2;
        }
    }

    /*******************************************************************/
    /* At this stage, at least one (or both) list has been expended    */
    /* (or was empty to start with).                                   */
    /* If the new list is not empty, turn it into a linear list and    */
    /* append the unexpended list to it, if any.                       */
    /* Otherwise, set the new list to the nonempty list if any!        */
    /*******************************************************************/
    if (root != NULL)
    {
        tail = root;
        root = root -> next;
        tail -> next = (root1 == NULL ? root2 : root1);
    }
    else root = (root1 == NULL ? root2 : root1);

    return root;
}


/***************************************************************************/
/*                                ADD_CONFIGS:                             */
/***************************************************************************/
/* This function takes as argument a SOURCES_ELEMENT map, an ACTION and a  */
/* set (sorted list) of configurations. It adds the set of configurations  */
/* to the previous set of configurations associated with the ACTION in the */
/* SOURCES_ELEMENT map.                                                    */
/***************************************************************************/
static struct sources_element add_configs(struct sources_element sources,
                                          int action,
                                          struct stack_element *config_root)
{
    if (config_root == NULL) /* The new set is empty? Do nothing */
        return sources;

    if (sources.configs[action] == NULL) /* The previous was empty? */
    {
        sources.list[action] = sources.root;
        sources.root = action;
    }

    sources.configs[action] = union_config_sets(sources.configs[action],
                                                config_root);

    return sources;
}



/***************************************************************************/
/*                               CLEAR_VISITED:                            */
/***************************************************************************/
/* This function clears out all external space used by the VISITED set and */
/* resets VISITED to the empty set.                                        */
/***************************************************************************/
static void clear_visited(void)
{
    struct node *p,
                *tail;
    int state_no;

    for (state_no = visited.root;
         state_no != NIL; state_no = visited.list[state_no])
    {
        for (p = visited.map[state_no]; p != NULL; tail = p, p = p -> next)
            ;
        free_nodes(visited.map[state_no], tail);
        visited.map[state_no] = NULL;
    }

    visited.root = NIL;

    return;
}

/***************************************************************************/
/*                                WAS_VISITED:                             */
/***************************************************************************/
/* This boolean function checks whether or not a given pair [state, symbol]*/
/* was already inserted in the VISITED set.                                */
/***************************************************************************/
static BOOLEAN was_visited(int state_no, int symbol)
{
    struct node *p;

    for (p = visited.map[state_no]; p != NULL; p = p -> next)
    {
        if (p -> value == symbol)
            break;
    }

    return (p != NULL);
}


/***************************************************************************/
/*                               MARK_VISITED:                             */
/***************************************************************************/
/* This function inserts a given pair [state, symbol] into the VISITED set.*/
/***************************************************************************/
static void mark_visited(int state_no, int symbol)
{
    struct node *p;

    if (visited.map[state_no] == NULL) /* 1st time we see state_no? */
    {
        visited.list[state_no] = visited.root;
        visited.root = state_no;
    }

    p = Allocate_node();
    p -> value = symbol;
    p -> next = visited.map[state_no];
    visited.map[state_no] = p;

    return;
}


/***********************************************************************/
/*                             COMPUTE_CYCLIC:                         */
/***********************************************************************/
/* This procedure is a modified instantiation of the digraph algorithm */
/* to compute the CYCLIC set of states.                                */
/***********************************************************************/
static void compute_cyclic(short state_no)
{
    int indx;
    struct goto_header_type go_to;
    int symbol,
        act,
        i;

    stack[++top] = state_no;
    indx = top;
    cyclic[state_no] = FALSE;
    index_of[state_no] = indx;

    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);
        if (act > 0 && null_nt[symbol])
        {   /* We have a transition on a nullable nonterminal? */
            if (index_of[act] == OMEGA)
                compute_cyclic(act);
            else if (index_of[act] != INFINITY)
                cyclic[state_no] = TRUE;
            cyclic[state_no] = cyclic[state_no] || cyclic[act];

            index_of[state_no] = MIN(index_of[state_no], index_of[act]);
        }
    }

    if (index_of[state_no] == indx)
    {
        do
        {
            act = stack[top--];
            index_of[act] = INFINITY;
        } while(act != state_no);
    }

    return;
}


/***********************************************************************/
/*                           TRACE_ROOT:                               */
/***********************************************************************/
/*    In tracing an error, we will be moving backward in the state     */
/* automaton looking for items with the conflict symbol as look-ahead. */
/* In the case of SLR, we may have to analoguously look at an          */
/* arbitrary set of items involved.  In moving around these graphs, it */
/* is possible to encounter a cycle, in which case, we simply want to  */