resolve.c

一个非常好的检索工具

/* back out of the cycle and try another path. We therefore need to    */
/* keep track of which nodes have already been visited.  For LALR      */
/* conflicts, we use the LA_PTR field of the GOTO_ELEMENTs as an index */
/* to a BOOLEAN array LALR_VISITED.  For SLR conflicts, a boolean      */
/* array, SLR_VISITED, indexable by non-terminals, is used.  For       */
/* trace-backs to the root item, the boolean array SYMBOL_SEEN, also   */
/* also indexable by non-terminals, is used.                           */
/***********************************************************************/
static BOOLEAN trace_root(int lhs_symbol)
{
    int item;

    if (lhs_symbol == accept_image)
        return(TRUE);

    if (symbol_seen[lhs_symbol])
        return(FALSE);

    symbol_seen[lhs_symbol] = TRUE;
    for (item = nt_items[lhs_symbol]; item != NIL; item = item_list[item])
    {
        if (trace_root(rules[item_table[item].rule_number].lhs))
        {
            print_item(item);
            return(TRUE);
        }
    }

    return(FALSE);
}


/***********************************************************************/
/*                             PRINT_ROOT_PATH:                        */
/***********************************************************************/
/* The procedure below is invoked to retrace a path from the initial   */
/* item to a given item (ITEM_NO) passed to it as argument.            */
/***********************************************************************/
static void print_root_path(int item_no)
{
    symbol_seen = Allocate_boolean_array(num_non_terminals);
    symbol_seen -= (num_terminals + 1);

    if (trace_root(rules[item_table[item_no].rule_number].lhs))
    {
        fprintf(syslis, "\n"); /* Leave one blank line after root trace. */
        ENDPAGE_CHECK;
    }

    symbol_seen += (num_terminals + 1);
    ffree(symbol_seen);

    return;
}


/***********************************************************************/
/*                          LALR_PATH_RETRACED:                        */
/***********************************************************************/
/* This procedure takes as argument, a state number, STATE_NO, an      */
/* index into the goto map of state_no, GOTO_INDX, which identifies a  */
/* starting point for a search for the CONFLICT_SYMBOL. It attempts to */
/* find a path in the automaton (from the starting point) that leads   */
/* to a state where the conflict symbol can be read. If a path is      */
/* found, all items along the path are printed and SUCCESS is returned.*/
/*  Otherwise, FAILURE is returned.                                    */
/***********************************************************************/
static BOOLEAN lalr_path_retraced(int state_no,
                                  int goto_indx,
                                  int conflict_symbol)
{
    int symbol,
        item,
        state,
        i;

    struct goto_header_type go_to;

    struct node *p,
                *q,
                *tail,
                *w;

    BOOLEAN found;

    go_to = statset[state_no].go_to;
    lalr_visited[GOTO_LAPTR(go_to, goto_indx)] = TRUE;

    found = FALSE;

    state = GOTO_ACTION(go_to, goto_indx);
    for (p = (state > 0 ? statset[state].kernel_items
                        : adequate_item[-state]);
         (p != NULL) && (! found); p = p -> next)
    {
        item = p -> value - 1;
        if IS_IN_SET(first, item_table[item].suffix_index, conflict_symbol)
        {   /* Conflict_symbol can be read in state? */
            if (trace_opt == TRACE_FULL)
                print_root_path(item);
            found = TRUE;
        }
        else if IS_IN_SET(first, item_table[item].suffix_index, empty)
        {
            symbol = rules[item_table[item].rule_number].lhs;
            w = lpgaccess(state_no, item);
            for (q = w; q != NULL; tail = q, q = q -> next)
            {
                go_to = statset[q -> value].go_to;
                for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
                    ;

                if (! lalr_visited[GOTO_LAPTR(go_to, i)])
                {
                    if (lalr_path_retraced(q -> value, i, conflict_symbol))
                    {
                        found = TRUE;
                        break;
                    }
                }
            }

            for (; q != NULL; tail = q, q = q -> next)
                ;
            free_nodes(w, tail);
        }
    }

    if (found)
        print_item(item);

    return(found);
}


/***********************************************************************/
/*                      PRINT_RELEVANT_LALR_ITEMS:                     */
/***********************************************************************/
/*   In this procedure, we attempt to retrace an LALR conflict path    */
/* (there may be more than one) of CONFLICT_SYMBOL in the state        */
/* automaton that led to ITEM_NO in state STATE_NO.                    */
/***********************************************************************/
static void print_relevant_lalr_items(int state_no,
                                      int item_no,
                                      int conflict_symbol)
{
    int lhs_symbol,
        i;

    struct node *p,
                *tail,
                *v;

    lhs_symbol = rules[item_table[item_no].rule_number].lhs;
    if (lhs_symbol == accept_image)
        return;

    lalr_visited = Allocate_boolean_array(la_top + 1);

    v = lpgaccess(state_no, item_no);
    for (p = v; p != NULL; tail = p, p = p -> next)
    {
        struct goto_header_type go_to;

        go_to = statset[p -> value].go_to;
        for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
            ;

        if (lalr_path_retraced(p -> value, i, conflict_symbol))
            break;
    }

    for (; p != NULL; tail = p, p = p -> next)
        ;

    free_nodes(v, tail);

    ffree(lalr_visited);

    return;
}


/***********************************************************************/
/*                              SLR_TRACE:                             */
/***********************************************************************/
/* The procedure below is invoked to retrace a path that may have      */
/* introduced the CONFLICT_SYMBOL in the FOLLOW set of the nonterminal */
/* that produces ITEM_NO.  Note that such a path must exist.           */
/***********************************************************************/
static BOOLEAN slr_trace(int lhs_symbol, int conflict_symbol)
{
    int item;

    if (slr_visited[lhs_symbol])
        return(FALSE);

    slr_visited[lhs_symbol] = TRUE;

    for (item = nt_items[lhs_symbol]; item != NIL; item = item_list[item])
    {
        if IS_IN_SET(first, item_table[item].suffix_index, conflict_symbol)
        {
            if (trace_opt == TRACE_FULL)
                print_root_path(item);
            break;
        }
        if IS_IN_SET(first, item_table[item].suffix_index, empty)
        {
            if (slr_trace(rules[item_table[item].rule_number].lhs,
                          conflict_symbol))
                break;
        }
    }

    if (item != NIL)
    {
        print_item(item);
        return(TRUE);
    }
    else
        return(FALSE);
}


/***********************************************************************/
/*                           PRINT_RELEVANT_SLR_ITEMS:                 */
/***********************************************************************/
/* This procedure is invoked to print an SLR path of items that leads  */
/* to the conflict symbol.                                             */
/***********************************************************************/
static void print_relevant_slr_items(int item_no, int conflict_symbol)
{
    slr_visited = Allocate_boolean_array(num_non_terminals);
    slr_visited -= (num_terminals + 1);

    if (slr_trace(rules[item_table[item_no].rule_number].lhs,
                   conflict_symbol))
        ;
    slr_visited += (num_terminals + 1);
    ffree(slr_visited);

    return;
}


/***********************************************************************/
/*                       CONFLICTS_INITIALIZATION:                     */
/***********************************************************************/
/* This routine is invoked when a grammar contains conflicts, and the  */
/* first conflict is detected.                                         */
/***********************************************************************/
static void conflicts_initialization(void)
{
    int i;

    /*******************************************************************/
    /* NT_ITEMS and ITEM_LIST are used in reporting SLR conflicts, and */
    /* in recreating paths from the Start item. See the routines       */
    /* PRINT_RELEVANT_SLR_ITEMS and PRINT_ROOT_PATH.                   */
    /*******************************************************************/
    nt_items = Allocate_short_array(num_non_terminals);
    nt_items -= (num_terminals + 1);
    item_list = Allocate_short_array(num_items + 1);

    i = (PRINT_LINE_SIZE - 11) / 2 - 1;
    PR_HEADING;
    fill_in(msg_line, i, '-');
    fprintf(syslis, "\n%s CONFLICTS %s\n", msg_line, msg_line);
    output_line_no += 2;

/***********************************************************************/
/*   SLR conflicts may be caused by a symbol in the FOLLOW set of a    */
/* left hand side, which is not actually in the LALR look-ahead set in */
/* that context.  Therefore, there may not exist a path in the state   */
/* automaton from the state where the conflict was detected to another */
/* state where it was introduced.  In such a case, we try to retrace a */
/* path that contributed the conflict-symbol to the FOLLOW set via a   */
/* sequence of productions.                                            */
/*                                                                     */
/* To assist in this task, we build below a map from each non-terminal */
/* A to the set of items of which A is the dot SYMBOL. I.e., all items */
/* of the form [x .A y] where x and y are arbitrary strings, and A is  */
/* a non-terminal. This map is also used in retracing a path from the  */
/* Start item to any other item.                                       */
/***********************************************************************/
    for ALL_NON_TERMINALS(i)
        nt_items[i] = NIL;

    for ALL_ITEMS(i)
    {
        if (item_table[i].symbol IS_A_NON_TERMINAL)
        {
            item_list[i] = nt_items[item_table[i].symbol];
            nt_items[item_table[i].symbol] =  i;
        }
    }

    return;
}


/***********************************************************************/
/*                            PROCESS_CONFLICTS:                       */
/***********************************************************************/
/*   If conflicts are detected, tehy are placed in two lists headed by */
/* SR_CONFLICT_ROOT and RR_CONFLICT_ROOT.  We scan these lists, and    */
/* report the conflicts.                                               */
/***********************************************************************/
static void process_conflicts(int state_no)
{
    int symbol,
        rule_no,
        n;

    char temp[SYMBOL_SIZE + 1];

    if (nt_items == NULL)
        conflicts_initialization();

    print_state(state_no); /* Print state containing conflicts */

    /*******************************************************************/
    /* Process shift-reduce conflicts.                                 */
    /*******************************************************************/
    if (sr_conflict_root != NULL)