resolve.c

一个非常好的检索工具

    {
        struct sr_conflict_element *p,
                                   *tail;

        for (p = sr_conflict_root; p != NULL; tail = p, p = p -> next)
        {
            symbol = p -> symbol;
            rule_no = item_table[p -> item].rule_number;

            restore_symbol(temp, RETRIEVE_STRING(symbol));
            printf("*** Shift/reduce conflict on \"%s\" with rule %d\n",
                   temp, rule_no);
            fprintf(syslis,
                    "\n*** Shift/reduce conflict on \"%s\" with rule %d\n",
                    temp, rule_no);

            if (trace_opt != NOTRACE)
            {
                if (! slr_bit)
                    print_relevant_lalr_items(state_no, p -> item, symbol);
                else
                    print_relevant_slr_items(p -> item, symbol);
                print_item(p -> item);
            }
        }

        free_conflict_elements(sr_conflict_root, tail);
    }

    /*******************************************************************/
    /* Process reduce-reduce conflicts.                                */
    /*******************************************************************/
    if (rr_conflict_root != NULL)
    {
        struct rr_conflict_element *p,
                                   *tail;

        for (p = rr_conflict_root; p != NULL; tail = p, p = p -> next)
        {
            symbol = p -> symbol;
            n = item_table[p -> item1].rule_number;
            rule_no = item_table[p -> item2].rule_number;

            restore_symbol(temp, RETRIEVE_STRING(symbol));
            printf("*** Reduce/reduce conflict "
                   "on \"%s\" between rule %d and %d\n",
                   temp, n, rule_no);
            fprintf(syslis,
                    "\n*** Reduce/reduce conflict "
                    "on \"%s\" between rule %d and %d\n",
                    temp, n, rule_no);
            output_line_no +=2;
            if (trace_opt != NOTRACE)
            {
                if (! slr_bit)
                    print_relevant_lalr_items(state_no, p -> item1, symbol);
                else
                    print_relevant_slr_items(p -> item1, symbol);
                print_item(p -> item1);
                fill_in(msg_line, PRINT_LINE_SIZE - 3, '-');
                fprintf(syslis,"\n%s",msg_line);
                ENDPAGE_CHECK;
                if (! slr_bit)
                    print_relevant_lalr_items(state_no, p -> item2, symbol);
                else
                    print_relevant_slr_items(p -> item2, symbol);
                print_item(p -> item2);
            }
        }

        free_conflict_elements(rr_conflict_root, tail);
    }

    return;
}


/***********************************************************************/
/*                           ADD_CONFLICT_SYMBOL:                      */
/***********************************************************************/
/* Add SYMBOL to the set of symbols CONFLICT_SYMBOLS[STATE_NO].        */
/***********************************************************************/
static void add_conflict_symbol(int state_no, int symbol)
{
    struct node *p;

    p = Allocate_node();
    p -> value = symbol;
    if (conflict_symbols[state_no] == NULL)
        p -> next = p;
    else
    {
        p -> next = conflict_symbols[state_no] -> next;
        conflict_symbols[state_no] -> next = p;
    }
    conflict_symbols[state_no] = p;

    return;
}


/***********************************************************************/
/*                             FOLLOW_SOURCES:                         */
/***********************************************************************/
/* This function takes as argument a configuration STACK, a SYMBOL on  */
/* which a transition can be made in the configuration and a terminal  */
/* lookahead symbol, LA_SYMBOL. It executes the transition on SYMBOL   */
/* and simulates all paths taken in the automaton after that transition*/
/* until new state(s) are reached where a transition is possible on    */
/* the lookahead symbol. It then returns the new set of configurations */
/* found on which a transition on LA_SYMBOL is possible.               */
/***********************************************************************/
static struct stack_element *follow_sources(struct stack_element *stack,
                                            int symbol, int la_symbol)
{
    struct shift_header_type sh;
    struct goto_header_type  go_to;

    struct stack_element *configs,
                         *q;
    struct node *item_ptr;

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

    configs = NULL; /* Initialize the output set of configurations */

    /*******************************************************************/
    /* If the starting configuration consists of a single state and    */
    /* the initial [state, symbol] pair has already been visited,      */
    /* return the null set. Otherwise, mark the pair visited and ...   */
    /*******************************************************************/
    state_no = stack -> state_number;
    if (stack -> size == 1)
    {
        if (was_visited(state_no, symbol) ||
            (state_no == 1 && symbol == accept_image))
            return configs;

        mark_visited(state_no, symbol);
    }

    /*******************************************************************/
    /* Find the transition defined on the symbol...                    */
    /* If the SYMBOL is a nonterminal and we can determine that the    */
    /* lookahead symbol (LA_SYMBOL) cannot possibly follow the         */
    /* nonterminal in question in this context, we simply abandon the  */
    /* search and return the NULL set.                                 */
    /*******************************************************************/
    if (symbol IS_A_NON_TERMINAL)
    {
        go_to = statset[state_no].go_to;
        for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
            ;
        if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
        {
            int stack_top = 0;
            la_traverse(state_no, i, &stack_top);
        }

        if (! IS_IN_SET(la_set, GOTO_LAPTR(go_to, i), la_symbol))
            return configs;

        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, ...           */
    /*******************************************************************/
    if (act > 0)
    {
        /***************************************************************/
        /* We check to see if the new state contains an action on the  */
        /* lookahead symbol. If that's the case then we create a new   */
        /* configuration by appending ACT to the starting configuration*/
        /* and add this newly formed configuration to the set(list) of */
        /* configurations...                                           */
        /***************************************************************/
        sh = shift[statset[act].shift_number];
        for (i = 1; i <= sh.size; i++)
        {
            if (SHIFT_SYMBOL(sh, i) == la_symbol)
                break;
        }
        if (i <= sh.size) /* there is a transition on la_symbol in act */
        {
            q = allocate_stack_element();
            q -> state_number = act;
            q -> size = stack -> size + 1;
            q -> previous = stack;
            q -> next = NULL;

            configs = q;
        }

        /***************************************************************/
        /* If the new state cannot get into a cycle of null            */
        /* transitions, we check to see if it contains any transition  */
        /* on a nullable nonterminal. For each such transition, we     */
        /* append the new state to the stack and recursively invoke    */
        /* FOLLOW_SOURCES to check if a transition on LA_SYMBOL cannot */
        /* follow such a null transition.                              */
        /***************************************************************/
        if (! cyclic[act])
        {
            go_to = statset[act].go_to;
            for (i = 1; i <= go_to.size; i++)
            {
                symbol = GOTO_SYMBOL(go_to, i);
                if (null_nt[symbol])
                {
                    struct stack_element *new_configs;

                    q = allocate_stack_element();
                    q -> state_number = act;
                    q -> size = stack -> size + 1;
                    q -> previous = stack;
                    q -> next = NULL;

                    new_configs = follow_sources(q, symbol, la_symbol);
                    if (new_configs == NULL)
                        free_stack_elements(q, q);
                    else
                    {
                        add_dangling_stack_element(q);
                        configs = union_config_sets(configs, new_configs);
                    }
                }
            }
        }
    }

    /*******************************************************************/
    /* We now iterate over the kernel set of items associated with the */
    /* ACTion defined on SYMBOL...                                     */
    /*******************************************************************/
    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 (item_table[item_no].symbol == 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 FOLLOW_SOURCES with the prefix of the stack  */
                /* where the item was introduced through closure, the  */
                /* left-hand side of the item and the lookahead symbol.*/
                /*******************************************************/
                if (item_table[item_no].dot < stack -> size)
                {
                    q = stack;
                    for (i = 1; i < item_table[item_no].dot; i++)
                        q = q -> previous;

                    q = follow_sources(q, lhs_symbol, la_symbol);
                    configs = union_config_sets(configs, q);
                }
                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 start a new configuration and invoke    */
                    /* FOLLOW_SOURCES with the appropriate arguments to*/
                    /* calculate the set of configurations associated  */
                    /* with these sources.                             */
                    /***************************************************/
                    v = lpgaccess(q -> state_number, item_no);
                    for (p = v; p != NULL; tail = p, p = p -> next)
                    {
                        struct stack_element *new_configs;

                        q = allocate_stack_element();
                        q -> state_number = p -> value;
                        q -> size = 1;
                        q -> previous = NULL;
                        q -> next = NULL;

                        new_configs = follow_sources(q, lhs_symbol, la_symbol);
                        if (new_configs == NULL)
                            free_stack_elements(q, q);
                        else
                        {
                            add_dangling_stack_element(q);
                            configs = union_config_sets(configs, new_configs);
                        }
                    }

                    free_nodes(v, tail);
                }