mkfirst.c

一个非常好的检索工具

                for (end_node = ((q = closure[symbol]) == NULL);
                     ! end_node;
                     end_node = (q == closure[symbol]))
                {
                    q = q -> next;
                    if (nont_list[q -> value] == OMEGA)
                    {
                        nont_list[q -> value] = nt_root;
                        nt_root = q -> value;
                    }
                }
            }
        }
    }

    for (; nt_root != lhs_symbol; nt_root = nont_list[nt_root])
    {
        p = Allocate_node();
        p -> value = nt_root;
        if (closure[lhs_symbol] == NULL)
            p -> next = p;
        else
        {
            p -> next = closure[lhs_symbol] -> next;
            closure[lhs_symbol] -> next = p;
        }
        closure[lhs_symbol] = p;
    }

    if (index_of[lhs_symbol] == indx)
    {
        for (symbol = stack[top]; symbol != lhs_symbol; symbol = stack[--top])
        {
            q = closure[symbol];
            if (q != NULL)
            {
                p = q -> next;
                free_nodes(p, q); /* free nodes used by CLOSURE[SYMBOL] */
                closure[symbol] = NULL;
            }

            p = Allocate_node();
            p -> value = lhs_symbol;
            p -> next = p;
            closure[symbol] = p;

            for (end_node = ((q = closure[lhs_symbol]) == NULL);
                 ! end_node;
                 end_node = (q == closure[lhs_symbol]))
            {
                q = q -> next;
                if (q -> value != symbol)
                {
                    p = Allocate_node();
                    p -> value = q -> value;
                    p -> next = closure[symbol] -> next;
                    closure[symbol] -> next = p;
                    closure[symbol] = p;
                }
            }

            index_of[symbol] = INFINITY;
        }

        index_of[lhs_symbol] = INFINITY;
        top--;
    }

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

    return;
}


/*****************************************************************************/
/*                           NULLABLES_COMPUTATION:                          */
/*****************************************************************************/
/*   This procedure computes the set of non-terminal symbols that can        */
/* generate the empty string.  Such non-terminals are said to be nullable.   */
/*                                                                           */
/* A non-terminal "A" can generate empty if the grammar in question contains */
/* a rule:                                                                   */
/*          A ::= B1 B2 ... Bn     n >= 0,  1 <= i <= n                      */
/* and Bi, for all i, is a nullable non-terminal.                            */
/*****************************************************************************/
static void nullables_computation(void)
{
    short *rhs_start;

    int rule_no,
        nt;

    BOOLEAN changed = TRUE,
            end_node;

    rhs_start = Allocate_short_array(NEXT_RULE_SIZE);

    /******************************************************************/
    /* First, mark all non-terminals as non-nullable.  Then initialize*/
    /* RHS_START. RHS_START is a mapping from each rule in the grammar*/
    /* into the next symbol in its right-hand side that has not yet   */
    /* proven to be nullable.                                         */
    /******************************************************************/
    for ALL_NON_TERMINALS(nt)
        null_nt[nt] = FALSE;

    for ALL_RULES(rule_no)
        rhs_start[rule_no] = rules[rule_no].rhs;

    /******************************************************************/
    /* We now iterate over the rules and try to advance the RHS_START */
    /* pointer thru each right-hand side as far as we can.  If one or */
    /* more non-terminals are found to be nullable, they are marked   */
    /* as such and the process is repeated.                           */
    /*                                                                */
    /* If we go through all the rules and no new non-terminal is found*/
    /* to be nullable then we stop and return.                        */
    /*                                                                */
    /* Note that for each iteration, only rules associated with       */
    /* non-terminals that are non-nullable are considered.  Further,  */
    /* as soon as a non-terminal is found to be nullable, the         */
    /* remaining rules associated with it are not considered.  I.e.,  */
    /* we quit the inner loop.                                        */
    /******************************************************************/
    while(changed)
    {
        changed = FALSE;

        for ALL_NON_TERMINALS(nt)
        {
            for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
                 ! null_nt[nt] && ! end_node;
                 end_node = (rule_no == lhs_rule[nt]))
            {
                rule_no = next_rule[rule_no];
                if (is_nullable_rhs(rhs_start,rule_no))
                {
                    changed = TRUE;
                    null_nt[nt] = TRUE;
                }
            }
        }
    }

    ffree(rhs_start);

    return;
}


/*****************************************************************************/
/*                            IS_NULLABLE_RHS:                               */
/*****************************************************************************/
/*   This procedure tries to advance the RHS_START pointer.  If the current  */
/* symbol identified by the RHS_START element is a terminal it returns FALSE */
/* to indicate that it cannot go any further.  If it encounters a  non-null- */
/* lable non-terminal, it also returns FALSE. Otherwise, the whole right-hand*/
/* side is consumed, and it returns the value TRUE.                          */
/*****************************************************************************/
static BOOLEAN is_nullable_rhs(short *rhs_start, int rule_no)
{
    int symbol;

    for(rhs_start[rule_no] = rhs_start[rule_no];
        rhs_start[rule_no] <= rules[rule_no + 1].rhs - 1;
        rhs_start[rule_no]++)
    {
        symbol = rhs_sym[rhs_start[rule_no]];
        if (symbol IS_A_TERMINAL)
            return(FALSE);
        else if (! null_nt[symbol]) /* symbol is a non-terminal */
            return(FALSE);
    }

    return(TRUE);
}


/*****************************************************************************/
/*                             COMPUTE_FIRST:                                */
/*****************************************************************************/
/* This subroutine computes FIRST(NT) for some non-terminal NT using the     */
/* digraph algorithm.                                                        */
/* FIRST(NT) is the set of all terminals Ti that may start a string generated*/
/* by NT. That is, NT *::= Ti X where X is an arbitrary string.              */
/*****************************************************************************/
static void compute_first(int nt)
{
    int indx;

    BOOLEAN end_node,
            blocked;

    int i,
        symbol,
        rule_no;

    SET_PTR temp_set;

    temp_set = (SET_PTR)
               calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
    if (temp_set == NULL)
        nospace(__FILE__, __LINE__);

    stack[++top] = nt;
    indx = top;
    index_of[nt] = indx;

    /**************************************************************/
    /* Iterate over all rules generated by non-terminal NT...     */
    /* In this application of the transitive closure algorithm,   */
    /*                                                            */
    /*  G(A) := { t | A ::= t X for a terminal t and a string X } */
    /*                                                            */
    /* The relation R is defined as follows:                      */
    /*                                                            */
    /*    R(A, B) iff A ::= B1 B2 ... Bk B X                      */
    /*                                                            */
    /* where Bi is nullable for 1 <= i <= k                       */
    /**************************************************************/

    for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
         ! end_node;    /* Iterate over all rules produced by NT */
         end_node = (rule_no == lhs_rule[nt]))
    {
        rule_no = next_rule[rule_no];
        blocked = FALSE;

        for ENTIRE_RHS(i, rule_no)
        {
            symbol = rhs_sym[i];
            if (symbol IS_A_NON_TERMINAL)
            {
                if (index_of[symbol] == OMEGA)
                    compute_first(symbol);
                index_of[nt] = MIN( index_of[nt], index_of[symbol]);

                ASSIGN_SET(temp_set, 0, nt_first, symbol);
                RESET_BIT(temp_set, empty);
                SET_UNION(nt_first, nt, temp_set, 0);
                blocked = NOT(null_nt[symbol]);
            }
            else
            {
                SET_BIT_IN(nt_first, nt, symbol);
                blocked = TRUE;
            }

            if (blocked)
                break;
        }

        if (! blocked)
        {
            SET_BIT_IN(nt_first, nt, empty);
        }
    }

    if (index_of[nt] == indx)
    {
        for (symbol = stack[top]; symbol != nt; symbol = stack[--top])
        {
            ASSIGN_SET(nt_first, symbol, nt_first, nt);
            index_of[symbol] = INFINITY;
        }
        index_of[nt] = INFINITY;
        top--;
    }
    ffree(temp_set);
    return;
}


/*****************************************************************************/
/*                            CHECK_NON_TERMINALS:                           */
/*****************************************************************************/
/* This procedure checks whether or not any non-terminal symbols can fail to */
/* generate a string of terminals.                                           */
/*                                                                           */
/* A non-terminal "A" can generate a terminal string if the grammar in       */
/* question contains a rule of the form:                                     */
/*                                                                           */
/*         A ::= X1 X2 ... Xn           n >= 0,  1 <= i <= n                 */
/*                                                                           */
/* and Xi, for all i, is a terminal or a non-terminal that can generate a    */
/* string of terminals.                                                      */
/* This routine is structurally identical to COMPUTE_NULLABLES.              */
/*****************************************************************************/
static void check_non_terminals(void)
{
    char line[PRINT_LINE_SIZE + 1],
         tok[SYMBOL_SIZE + 1];

    short *rhs_start;

    int rule_no,
        nt_root,
        nt_last,
        symbol,
        nt;

    BOOLEAN changed = TRUE,
            end_node,
            *produces_terminals;

    rhs_start = Allocate_short_array(NEXT_RULE_SIZE);
    produces_terminals = Allocate_boolean_array(num_non_terminals);
    produces_terminals -= (num_terminals + 1);

    /******************************************************************/
    /* First, mark all non-terminals as not producing terminals. Then */
    /* initialize RHS_START. RHS_START is a mapping from each rule in */
    /* the grammar into the next symbol in its right-hand side that   */
    /* has not yet proven to be a symbol that generates terminals.    */
    /******************************************************************/
    for ALL_NON_TERMINALS(nt)
        produces_terminals[nt] = FALSE;

    produces_terminals[accept_image] = TRUE;

    for ALL_RULES(rule_no)
        rhs_start[rule_no] = rules[rule_no].rhs;

    /******************************************************************/
    /* We now iterate over the rules and try to advance the RHS_START */
    /* pointer to each right-hand side as far as we can.  If one or   */
    /* more non-terminals are found to be "all right", they are       */
    /* marked as such and the process is repeated.                    */
    /*                                                                */
    /* If we go through all the rules and no new non-terminal is      */
    /* found to be "all right" then we stop and return.               */
    /*                                                                */
    /* Note that on each iteration, only rules associated with        */
    /* non-terminals that are not "all right" are considered. Further,*/
    /* as soon as a non-terminal is found to be "all right", the      */
    /* remaining rules associated with it are not considered. I.e.,   */
    /* we quit the inner loop.                                        */
    /******************************************************************/
    while(changed)
    {
        changed = FALSE;

        for ALL_NON_TERMINALS(nt)
        {
            for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
                 (! produces_terminals[nt]) && (! end_node);
                 end_node = (rule_no == lhs_rule[nt]))
            {
                rule_no = next_rule[rule_no];
                if (is_terminal_rhs(rhs_start, produces_terminals, rule_no))
                {
                    changed = TRUE;
                    produces_terminals[nt] = TRUE;
                }
            }
        }
    }

    /*************************************************************/
    /* Construct a list of all non-terminals that do not generate*/
    /* terminal strings.                                         */
    /*************************************************************/
    nt_root = NIL;
    for ALL_NON_TERMINALS(nt)