remsp.c

一个非常好的检索工具

        }
    }

    return;
}


/**********************************************************************/
/*                           SP_DEFAULT_ACTION:                       */
/**********************************************************************/
/* Sp_default_action takes as parameter a state, state_no and a rule, */
/* rule_no that may be reduce when the parser enters state_no.        */
/* Sp_default_action tries to determine the highest rule that may be  */
/* reached via a sequence of SP reductions.                           */
/**********************************************************************/
static short sp_default_action(short state_no, short rule_no)
{
    struct reduce_header_type red;
    struct goto_header_type go_to;

    int lhs_symbol,
        action,
        i;

    go_to = statset[state_no].go_to;

/**********************************************************************/
/* While the rule we have at hand is a single production, ...         */
/**********************************************************************/
    while (IS_SP_RULE(rule_no))
    {
        lhs_symbol = rules[rule_no].lhs;
        for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
            ;

        action = GOTO_ACTION(go_to, i);
        if (action < 0) /* goto-reduce action? */
        {
            action = -action;
            if (RHS_SIZE(action) != 1)
                break;

            rule_no = action;
        }
        else
        {
            int best_rule = OMEGA;

        /**************************************************************/
        /* Enter the state action and look for preferably a SP rule   */
        /* or some rule with right-hand size 1.                       */
        /**************************************************************/
            red = reduce[action];
            for (i = 1; i <= red.size; i++)
            {
                action = REDUCE_RULE_NO(red, i);
                if (IS_SP_RULE(action))
                {
                    best_rule = action;
                    break;
                }
                if (RHS_SIZE(action) == 1)
                    best_rule = action;
            }
            if (best_rule == OMEGA)
                break;

            rule_no = best_rule;
        }
    }

    return rule_no;
}

/**********************************************************************/
/*                              SP_NT_ACTION:                         */
/**********************************************************************/
/* This routine takes as parameter a state, state_no, a nonterminal,  */
/* lhs_symbol (that is the right-hand side of a SP or a rule with     */
/* right-hand size 1, but not identified as a SP) on which there is   */
/* a transition in state_no and a lookahead symbol la_symbol that may */
/* be processed after taking the transition. It returns the reduce    */
/* action that follows the transition if an action on la_symbol is    */
/* found, otherwise it returns the most suitable default action.      */
/**********************************************************************/
static short sp_nt_action(short state_no, short lhs_symbol, short la_symbol)
{
    struct reduce_header_type red;
    struct goto_header_type go_to;

    int action,
        rule_no,
        i;

    go_to = statset[state_no].go_to;
    for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
        ;

    action = GOTO_ACTION(go_to, i);
    if (action < 0)
        action = -action;
    else
    {
        red = reduce[action];
        action = OMEGA;
        for (i = 1; i <= red.size; i++)
        {
            rule_no = REDUCE_RULE_NO(red, i);
            if (REDUCE_SYMBOL(red, i) == la_symbol)
            {
                action = rule_no;
                break;
            }
            else if (action == OMEGA && IS_SP_RULE(rule_no))
                action = rule_no;
        }
    }

    return action;
}


/**********************************************************************/
/*                       GREATEST_COMMON_ANCESTOR:                    */
/**********************************************************************/
/* Let BASE_RULE be a rule  A -> X.  The item [A -> .X] is in STATE1  */
/* and STATE2.  After shifting on X (in STATE1 and STATE2), if the    */
/* lookahead is LA_SYMBOL then BASE_RULE is reduced. In STATE1, a     */
/* sequence of single-production reductions is executed ending with   */
/* a reduction of RULE1. In STATE2, a sequence of single-productions  */
/* is also executed ending with RULE2.                                */
/* The goal of this function is to find the greatest ancestor of      */
/* BASE_RULE that is also a descendant of both RULE1 and RULE2.       */
/**********************************************************************/
static short greatest_common_ancestor(short base_rule, short la_symbol,
                                      short state1, short rule1,
                                      short state2, short rule2)
{
    int lhs_symbol,
        act1,
        act2,
        rule_no;

    act1 = base_rule;
    act2 = base_rule;
    while (act1 == act2)
    {
        rule_no = act1;
        if (act1 == rule1 || act2 == rule2)
            break;

        lhs_symbol = rules[rule_no].lhs;

        act1 = sp_nt_action(state1, lhs_symbol, la_symbol);
        act2 = sp_nt_action(state2, lhs_symbol, la_symbol);
    }

    return rule_no;
}


/**********************************************************************/
/*                       COMPUTE_UPDATE_ACTION:                       */
/**********************************************************************/
/* In SOURCE_STATE there is a transition on SYMBOL into STATE_NO.     */
/* SYMBOL is the right-hand side of a SP rule and the global map      */
/* sp_action[SYMBOL] yields a set of update reduce actions that may   */
/* follow the transition on SYMBOL into STATE_NO.                     */
/**********************************************************************/
static void compute_update_actions(short source_state,
                                   short state_no, short symbol)
{
    int i,
        rule_no;

    struct reduce_header_type red;
    struct update_action_element *p;

    red = reduce[state_no];

    for (i = 1; i <= red.size; i++)
    {
        if (IS_SP_RULE(REDUCE_RULE_NO(red, i)))
        {
            rule_no = sp_action[symbol][REDUCE_SYMBOL(red, i)];
            if (rule_no == OMEGA)
                rule_no = sp_default_action(source_state,
                                            REDUCE_RULE_NO(red, i));

        /**************************************************************/
        /* Lookup the update map to see if a previous update was made */
        /* in STATE_NO on SYMBOL...                                   */
        /**************************************************************/
            for (p = update_action[state_no]; p != NULL; p = p -> next)
            {
                if (p -> symbol == REDUCE_SYMBOL(red, i))
                    break;
            }

        /**************************************************************/
        /* If no previous update action was defined on STATE_NO and   */
        /* SYMBOL, simply add it. Otherwise, chose as the greatest    */
        /* common ancestor of the initial reduce action and the two   */
        /* contending updates as the update action.                   */
        /**************************************************************/
            if (p == NULL)
            {
                p = (struct update_action_element *)
                    talloc(sizeof(struct update_action_element));
                if (p == (struct update_action_element *) NULL)
                    nospace(__FILE__, __LINE__);
                p -> next = update_action[state_no];
                update_action[state_no] = p;

                p -> symbol = REDUCE_SYMBOL(red, i);
                p -> action = rule_no;
                p -> state  = source_state;
            }
            else if ((rule_no != p -> action) &&
                     (p -> action != REDUCE_RULE_NO(red, i)))
            {
                p -> action = greatest_common_ancestor(REDUCE_RULE_NO(red, i),
                                                       REDUCE_SYMBOL(red, i),
                                                       source_state, rule_no,
                                                       p -> state,
                                                       p -> action);
            }
        }
    }

    return;
}


/**********************************************************************/
/*                             SP_STATE_MAP:                          */
/**********************************************************************/
/* Sp_state_map is invoked to create a new state using the reduce map */
/* sp_symbol[SYMBOL]. The new state will be entered via a transition  */
/* on SYMBOL which is the right-hand side of the SP rule of which     */
/* ITEM_NO is the final item.                                         */
/*                                                                    */
/* RULE_HEAD is the root of a list of rules in the global vector      */
/* next_rule.  This list of rules identifies the range of the reduce  */
/* map sp_symbol[SYMBOL]. The value SP_RULE_COUNT is the number of    */
/* rules in the list. The value SP_ACTION_COUNT is the number of      */
/* actions in the map sp_symbol[SYMBOL].                              */
/**********************************************************************/
static short sp_state_map(int rule_head, short item_no,
                          short sp_rule_count,
                          short sp_action_count, short symbol)
{
    struct sp_state_element *state;
    struct node             *p;

    int rule_no,
        i;

    BOOLEAN no_overwrite;

    unsigned long hash_address;

    /******************************************************************/
    /* These new SP states are defined by their reduce maps. Hash the */
    /* reduce map based on the set of rules in its range - simply add */
    /* them up and reduce modulo STATE_TABLE_SIZE.                    */
    /******************************************************************/
    hash_address = 0;
    for (rule_no = rule_head;
         rule_no != NIL; rule_no = next_rule[rule_no])
        hash_address += rule_no;

    hash_address %= STATE_TABLE_SIZE;

    /******************************************************************/
    /* Search the hash table for a compatible state. Two states S1    */
    /* and S2 are compatible if                                       */
    /*     1) the set of rules in their reduce map is identical.      */
    /*     2) for each terminal symbol t, either                      */
    /*            reduce[S1][t] == reduce[S2][t] or                   */
    /*            reduce[S1][t] == OMEGA         or                   */
    /*            reduce[S2][t] == OMEGA                              */
    /*                                                                */
    /******************************************************************/
    for (state = sp_table[hash_address];
         state != NULL; state = state -> link)
    {
        if (state -> rule_count == sp_rule_count) /* same # of rules? */
        {
            for (p = state -> rule_root; p != NULL; p = p -> next)
            {
                if (next_rule[p -> value] == OMEGA)   /* not in list? */
                    break;
            }

    /******************************************************************/
    /* If the set of rules are identical, we proceed to compare the   */
    /* actions for compatibility. The idea is to make sure that all   */
    /* actions in the hash table do not clash in the actions in the   */
    /* map sp_action[SYMBOL].                                         */
    /******************************************************************/
            if (p == NULL) /* all the rules match? */
            {
                struct action_element *actionp,
                                      *action_tail;

                for (actionp = state -> action_root;
                     actionp != NULL; actionp = actionp -> next)
                {
                    if (sp_action[symbol][actionp -> symbol] != OMEGA &&
                        sp_action[symbol][actionp -> symbol] !=
                                                     actionp -> action)
                         break;
                }

        /**************************************************************/