mkfirst.c

一个非常好的检索工具

    {
        if (! produces_terminals[nt])
        {
            if (nt_root == NIL)
                nt_root = nt;
            else
                nt_list[nt_last] = nt;
            nt_last = nt;
        }
    }

    /*************************************************************/
    /* If there are non-terminal symbols that do not generate    */
    /* terminal strings, print them out and stop the program.    */
    /*************************************************************/
    if (nt_root != NIL)
    {
        nt_list[nt_last] = NIL;  /* mark end of list */
        PR_HEADING;
        strcpy(line, "*** ERROR: The following Non-terminal");
        if (nt_list[nt_root] == NIL)
            strcat(line, " does not generate any terminal strings: ");
        else
        {
            strcat(line, "s do not generate any terminal strings: ");
            PRNT(line);
            strcpy(line, "        "); /* 8 spaces */
        }

        for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
        {
            restore_symbol(tok, RETRIEVE_STRING(symbol));
            if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE-1)
            {
                PRNT(line);
                print_large_token(line, tok, "    ", LEN);
            }
            else
                strcat(line, tok);
            strcat(line, BLANK);
        }
        PRNT(line);
        exit(12);
    }
    produces_terminals += (num_terminals + 1);
    ffree(produces_terminals);
    ffree(rhs_start);
}


/*****************************************************************************/
/*                          IS_TERMINAL_RHS:                                 */
/*****************************************************************************/
/*   This procedure tries to advance the RHS_START pointer.  If the current  */
/* symbol identified by the RHS_START element is a bad non-terminal it       */
/* returns FALSE.  Otherwise, the whole right-hand side is traversed, and it */
/* returns the value TRUE.                                                   */
/*****************************************************************************/
static BOOLEAN is_terminal_rhs(short *rhs_start,
                               BOOLEAN *produces_terminals, 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_NON_TERMINAL)
        {
            if (! produces_terminals[symbol])
                return(FALSE);
        }
    }

    return(TRUE);
}


/*****************************************************************************/
/*                             FIRST_MAP:                                    */
/*****************************************************************************/
/*  FIRST_MAP takes as arguments two pointers, ROOT and TAIL, to a sequence  */
/* of symbols in RHS which it inserts in FIRST_TABLE.  The vector FIRST_TABLE*/
/* is used as the base for a hashed table where collisions are resolved by   */
/* links.  Elements added to this hash table are allocated from the vector   */
/* FIRST_ELEMENT, with the variable TOP always indicating the position of the*/
/* last element in FIRST_ELEMENT that was allocated.                         */
/* NOTE: The suffix indentified by ROOT and TAIL is presumed not to be empty.*/
/*       That is, ROOT <= TAIL !!!                                           */
/*****************************************************************************/
static short first_map(int root, int tail)
{
    int i,
        j,
        k;

    for (i = first_table[rhs_sym[root]]; i != NIL; i = first_element[i].link)
    {
        for (j = root + 1,
             k = first_element[i].suffix_root + 1;
             (j <= tail && k <= first_element[i].suffix_tail);
             j++, k++)
        {
            if (rhs_sym[j] != rhs_sym[k])
                break;
        }
        if (j > tail && k > first_element[i].suffix_tail)
            return((short) i);
    }
    top++;
    first_element[top].suffix_root = root;
    first_element[top].suffix_tail = tail;
    first_element[top].link = first_table[rhs_sym[root]];
    first_table[rhs_sym[root]] = top;

    return(top);
}


/*****************************************************************************/
/*                              S_FIRST:                                     */
/*****************************************************************************/
/* S_FIRST takes as argument, two pointers: ROOT and TAIL to a sequence of   */
/* symbols in the vector RHS, and INDEX which is the index of a first set.   */
/* It computes the set of all terminals that can appear as the first symbol  */
/* in the sequence and places the result in the FIRST set indexable by INDEX.*/
/*****************************************************************************/
static void s_first(int root, int tail, int index)
{
    int i,
        symbol;

    symbol = (root > tail ? empty : rhs_sym[root]);

    if (symbol IS_A_TERMINAL)
    {
        INIT_FIRST(index);
        SET_BIT_IN(first, index, symbol); /* add it to set */
    }
    else
    {
        ASSIGN_SET(first, index, nt_first, symbol);
    }

    for (i = root + 1; i <= tail && IS_IN_SET(first, index, empty); i++)
    {
        symbol = rhs_sym[i];
        RESET_BIT_IN(first, index, empty);    /* remove EMPTY */
        if (symbol IS_A_TERMINAL)
        {
            SET_BIT_IN(first, index, symbol);  /* add it to set */
        }
        else
        {
            SET_UNION(first, index, nt_first, symbol);
        }
    }

    return;
}


/******************************************************************/
/*                     COMPUTE_PRODUCES:                          */
/******************************************************************/
/* For a given symbol, complete the computation of                */
/* PRODUCES[symbol].                                              */
/******************************************************************/
static void compute_produces(int symbol)
{
    int indx;

    int new_symbol;

    struct node *p,
                *q;

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

    for (p = direct_produces[symbol]; p != NULL; q = p, p = p -> next)
    {
        new_symbol = p -> value;
        if (index_of[new_symbol] == OMEGA)  /* first time seen? */
            compute_produces(new_symbol);
        index_of[symbol] = MIN(index_of[symbol], index_of[new_symbol]);
        NTSET_UNION(produces, symbol, produces, new_symbol);
    }
    if (direct_produces[symbol] != NULL)
        free_nodes(direct_produces[symbol], q);

    if (index_of[symbol] == indx)  /*symbol is SCC root */
    {
        for (new_symbol = stack[top];
             new_symbol != symbol; new_symbol = stack[--top])
        {
            ASSIGN_NTSET(produces, new_symbol, produces, symbol);
            index_of[new_symbol] = INFINITY;
        }

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

    return;
}


/*****************************************************************************/
/*                          COMPUTE_FOLLOW:                                  */
/*****************************************************************************/
/* COMPUTE_FOLLOW computes FOLLOW[nt] for some non-terminal NT using the     */
/* digraph algorithm.  FOLLOW[NT] is the set of all terminals Ti that        */
/* may immediately follow a string X generated by NT. I.e., if NT *::= X     */
/* then X Ti is a valid substring of a class of strings that may be          */
/* recognized by the language.                                               */
/*****************************************************************************/
static void compute_follow(int nt)
{
    int indx;

    int rule_no,
        lhs_symbol,
        item_no;

    SET_PTR temp_set;

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

    /**************************************************************/
    /* FOLLOW[NT] was initialized to 0 for all non-terminals.     */
    /**************************************************************/

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

    for (item_no = nt_items[nt]; item_no != NIL; item_no = next_item[item_no])
    { /* iterate over all items of NT */
        ASSIGN_SET(temp_set, 0, first, item_table[item_no].suffix_index);
        if (IS_ELEMENT(temp_set, empty))
        {
            RESET_BIT(temp_set, empty);
            rule_no = item_table[item_no].rule_number;
            lhs_symbol = rules[rule_no].lhs;
            if (index_of[lhs_symbol] == OMEGA)
                compute_follow(lhs_symbol);
            SET_UNION( follow, nt, follow, lhs_symbol);
            index_of[nt] = MIN( index_of[nt], index_of[lhs_symbol]);
        }
        SET_UNION(follow, nt, temp_set, 0);
    }

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


/*****************************************************************************/
/*                           PRINT_UNREACHABLES:                             */
/*****************************************************************************/
static void print_unreachables(void)
{
    short *symbol_list;

    int nt,
        t_root,
        nt_root,
        rule_no,
        symbol,
        i;

    BOOLEAN end_node;

    char line[PRINT_LINE_SIZE + 1],
         tok[SYMBOL_SIZE + 1];

    /***************************************************************/
    /* SYMBOL_LIST is used for two purposes:                       */
    /*  1) to mark symbols that are reachable from the Accepting   */
    /*        non-terminal.                                        */
    /*  2) to construct lists of symbols that are not reachable.   */
    /***************************************************************/

    symbol_list = Allocate_short_array(num_symbols + 1);
    for ALL_SYMBOLS(i)
        symbol_list[i] = OMEGA;
    symbol_list[eoft_image] = NIL;
    symbol_list[empty] = NIL;
    if (error_maps_bit)
        symbol_list[error_image] = NIL;

    /*********************************************************************/
    /* Initialize a list consisting only of the Accept non-terminal.     */
    /* This list is a work pile of non-terminals to process as follows:  */
    /* Each non-terminal in the front of the list is removed in turn and */
    /* 1) All terminal symbols in one of its right-hand sides are        */
    /*     marked reachable.                                             */
    /* 2) All non-terminals in one of its right-hand sides are placed    */
    /*     in the the work pile of it had not been processed previously  */
    /*********************************************************************/
    nt_root = accept_image;
    symbol_list[nt_root] = NIL;

    for (nt = nt_root; nt != NIL; nt = nt_root)
    {
        nt_root = symbol_list[nt];

        for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
             ! end_node;
             end_node = (rule_no == lhs_rule[nt]))
        {
            rule_no = next_rule[rule_no];
            for ENTIRE_RHS(i, rule_no)
            {
                symbol = rhs_sym[i];
                if (symbol IS_A_TERMINAL)
                    symbol_list[symbol] = NIL;
                else if (symbol_list[symbol] == OMEGA)
                {
                    symbol_list[symbol] = nt_root;
                    nt_root = symbol;
                }
            }
        }
    }

    /***************************************************************/
    /* We now iterate (backwards to keep things in order) over the */
    /* terminal symbols, and place each unreachable terminal in a  */
    /* list. If the list is not empty, we signal that these symbols*/
    /* are unused.                                                 */
    /***************************************************************/
    t_root = NIL;
    for ALL_TERMINALS_BACKWARDS(symbol)
    {
        if (symbol_list[symbol] == OMEGA)
        {
            symbol_list[symbol] = t_root;
            t_root = symbol;
        }
    }

    if (t_root != NIL)
    {
        PR_HEADING;
        if (symbol_list[t_root] != NIL)
        {
            PRNT("*** The following Terminals are useless: ");