mkfirst.c

一个非常好的检索工具

        nospace(__FILE__, __LINE__);

    if (read_reduce_bit)
    {
        for ALL_RULES(rule_no)
        {
            int j;

            j = RHS_SIZE(rule_no);
            if (rules[rule_no].lhs != accept_image && j > 0)
            {
                struct node *p;

                item_no = first_item_of[rule_no] + j;
                p = Allocate_node();
                p -> value = item_no;
                p -> next = NULL;
                adequate_item[rule_no] = p;
            }
            else
                adequate_item[rule_no] = NULL;
        }
    }


    /***************************************************************/
    /* Construct the CLITEMS map. Each element of CLITEMS points   */
    /* to a circular linked list of items.                         */
    /***************************************************************/
    clitems = (struct node **)
              calloc(num_non_terminals, sizeof(struct node *));
    if (clitems == NULL)
        nospace(__FILE__, __LINE__);
    clitems -= (num_terminals + 1);

    for ALL_NON_TERMINALS(nt)
    {
        clitems[nt] = NULL;

        for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
             ! end_node;
             end_node = (rule_no == lhs_rule[nt]))
        {
            struct node *p;

            rule_no = next_rule[rule_no];
            p = Allocate_node();
            p -> value = first_item_of[rule_no];
            if (clitems[nt] == NULL)
                p -> next = p;
            else
            {
                p -> next = clitems[nt] -> next;
                clitems[nt] -> next = p;
            }
            clitems[nt] = p;
        }
    }

    /***************************************************************/
    /* If LALR_LEVEL > 1, we need to calculate RMPSELF, a set that */
    /* identifies the nonterminals that can right-most produce     */
    /* themselves. In order to compute RMPSELF, the map PRODUCES   */
    /* must be constructed which identifies for each nonterminal   */
    /* the set of nonterminals that it can right-most produce.     */
    /***************************************************************/
    if (lalr_level > 1)
    {
        produces = (SET_PTR)
                   calloc(num_non_terminals,
                          non_term_set_size * sizeof(BOOLEAN_CELL));
        if (produces == NULL)
            nospace(__FILE__, __LINE__);
        produces -= ((num_terminals + 1) * non_term_set_size);

        direct_produces = (struct node **)
                          calloc(num_non_terminals, sizeof(struct node *));
        if (direct_produces == NULL)
            nospace(__FILE__, __LINE__);
        direct_produces -= (num_terminals + 1);

        for ALL_NON_TERMINALS(nt)
        {
            struct node *p,
                        *q;

            for (end_node = ((p = clitems[nt]) == NULL);
                 ! end_node; end_node = (p == clitems[nt]))
            {
                p = p -> next;
                item_no = p -> value;
                symbol = item_table[item_no].symbol;
                if (symbol IS_A_NON_TERMINAL)
                {
                    i = item_table[item_no].suffix_index;
                    if (IS_IN_SET(first, i, empty) &&
                        (! IS_IN_NTSET(produces, nt,
                                       symbol - num_terminals)))
                    {
                        NTSET_BIT_IN(produces, nt,
                                     symbol - num_terminals);
                        q = Allocate_node();
                        q -> value = symbol;
                        q -> next = direct_produces[nt];
                        direct_produces[nt] = q;
                    }
                }
            }
        }

        /************************************************************/
        /* Complete the construction of the RIGHT_MOST_PRODUCES map */
        /* for non-terminals using the digraph algorithm.           */
        /************************************************************/
        for ALL_NON_TERMINALS(nt)
            index_of[nt] = OMEGA;

        top = 0;
        for ALL_NON_TERMINALS(nt)
        {
            if (index_of[nt] == OMEGA)
                compute_produces(nt);
        }

        init_rmpself(produces);

        produces += ((num_terminals + 1) * non_term_set_size);
        ffree(produces);
        direct_produces += (num_terminals + 1);
        ffree(direct_produces);
    }

    /***************************************************************/
    /* Construct the FOLLOW map if                                 */
    /*   1) an SLR table is requested                              */
    /*   2) if we have to print the FOLLOW map                     */
    /*   3) Error-maps are requested                               */
    /*   4) There are more than one starting symbol.               */
    /***************************************************************/
    if (slr_bit || follow_bit || error_maps_bit ||
        next_rule[lhs_rule[accept_image]] != lhs_rule[accept_image])
    {
        follow = (SET_PTR)
                 calloc(num_non_terminals,
                        term_set_size * sizeof(BOOLEAN_CELL));
        if (follow == NULL)
            nospace(__FILE__, __LINE__);
        follow -= ((num_terminals + 1) * term_set_size);

        SET_BIT_IN(follow, accept_image, eoft_image);

        for ALL_NON_TERMINALS(i) /* Initialize INDEX_OF to OMEGA */
            index_of[i] = OMEGA;

        index_of[accept_image] = INFINITY;  /* mark computed */
        top = 0;

        for ALL_NON_TERMINALS(nt)
        {
            if (index_of[nt] == OMEGA) /* not yet computed ? */
                compute_follow(nt);
        }

    /***************************************************************/
    /*  Initialize FIRST for suffixes that can follow each starting*/
    /* non-terminal ( except the main symbol) with the FOLLOW set */
    /* of the non-terminal in question.                            */
    /***************************************************************/
        rule_no = lhs_rule[accept_image];
        if (next_rule[rule_no] != rule_no)
        {
            rule_no = next_rule[rule_no];   /* first rule */
            top = item_table[first_item_of[rule_no]].suffix_index;
            for (i = top + 1; i <= num_first_sets; i++)
            {
                rule_no = next_rule[rule_no];
                item_no = first_item_of[rule_no];
                symbol = item_table[item_no].symbol;
                if (symbol IS_A_NON_TERMINAL)
                {
                   ASSIGN_SET(first, i, follow, symbol);
                }
            }
        }
    }

    /***************************************************************/
    /* If WARNINGS option is turned on, the unreachable symbols in */
    /* the grammar are printed.                                    */
    /***************************************************************/
    if (warnings_bit)
        print_unreachables();

    /***************************************************************/
    /* If a Cross_Reference listing is requested, it is generated  */
    /* here.                                                       */
    /***************************************************************/
    if (xref_bit)
        print_xref();

    /***************************************************************/
    /* If a listing of the FIRST map is requested, it is generated */
    /* here.                                                       */
    /***************************************************************/
    if (first_bit)
        print_nt_first();

    /****************************************************************/
    /* If a listing of the FOLLOW map is requested, it is generated */
    /* here.                                                        */
    /***************************************************************/
    if (follow_bit)
        print_follow_map();

    /***************************************************************/
    /* Free allocated arrays.                                      */
    /***************************************************************/
    nt_first += ((num_terminals + 1) * term_set_size);
    ffree(nt_first);
    nt_list += (num_terminals + 1);
    ffree(nt_list);
    ffree(first_table);
    ffree(first_element);
    nt_items += (num_terminals + 1);
    ffree(nt_items);
    ffree(next_item);
    ffree(stack);
    index_of += (num_terminals + 1);
    ffree(index_of);
    lhs_rule += (num_terminals + 1);
    ffree(lhs_rule);
    ffree(next_rule);
    ffree(first_item_of);

    return;
}


/*****************************************************************************/
/*                           NO_RULES_PRODUCED:                              */
/*****************************************************************************/
static void no_rules_produced(void)
{
    char line[PRINT_LINE_SIZE + 1],
         tok[SYMBOL_SIZE + 1];

    int nt_root,
        nt_last,
        symbol;

    /*************************************************************/
    /* Build a list of all non-terminals that do not produce any */
    /* rules.                                                    */
    /*************************************************************/
    nt_root = NIL;
    for ALL_NON_TERMINALS(symbol)
    {
        if (lhs_rule[symbol] == NIL)
        {
            if (nt_root == NIL)
                nt_root = symbol;
            else
                nt_list[nt_last] = symbol;
            nt_last = symbol;
        }
    }

    /*************************************************************/
    /* If the list of non-terminals that do not produce any rules*/
    /* is not empty, signal error and stop.                      */
    /*************************************************************/

    if (nt_root != NIL)
    {
        PR_HEADING;
        nt_list[nt_last] = NIL;
        if (nt_list[nt_root] == NIL)
        {
            PRNTERR("The following Non-terminal does not produce any rules: ");
        }
        else
        {
            PRNTERR("The following Non-terminals do not produce any rules: ");
        }
        strcpy(line, "        ");

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


/*****************************************************************************/
/*                            COMPUTE_CLOSURE:                               */
/*****************************************************************************/
/*  This function computes the closure of a non-terminal LHS_SYMBOL passed   */
/* to it as an argument using the digraph algorithm.                         */
/*  The closure of a non-terminal A is the set of all non-terminals Bi that  */
/* can directly or indirectly start a string generated by A.                 */
/* I.e., A *::= Bi X where X is an arbitrary string.                         */
/*****************************************************************************/
static void compute_closure(int lhs_symbol)
{
    int indx;
    short *nont_list;

    int symbol,
        rule_no,
        nt_root,
        i;

    struct node *p,
                *q;

    BOOLEAN end_node;

    nont_list = Allocate_short_array(num_non_terminals);
    nont_list -= (num_terminals + 1); /* Temporary direct        */
                                      /* access set for closure. */
    stack[++top] = lhs_symbol;
    indx = top;
    index_of[lhs_symbol] = indx;

    for ALL_NON_TERMINALS(i)
        nont_list[i] = OMEGA;

    nont_list[lhs_symbol] = NIL;
    nt_root = lhs_symbol;

    closure[lhs_symbol] = NULL; /* Permanent closure set. Linked list */

    for (end_node = ((rule_no = lhs_rule[lhs_symbol]) == NIL);
         ! end_node;          /* Iterate over all rules of LHS_SYMBOL */
         end_node = (rule_no == lhs_rule[lhs_symbol]))
    {
        rule_no = next_rule[rule_no];
        symbol = (RHS_SIZE(rule_no) == 0 ? empty
                                         : rhs_sym[rules[rule_no].rhs]);

        if (symbol IS_A_NON_TERMINAL)
        {
            if (nont_list[symbol] == OMEGA)
            {
                if (index_of[symbol] == OMEGA) /* if first time seen */
                    compute_closure(symbol);

                index_of[lhs_symbol] = MIN(index_of[lhs_symbol],
                                           index_of[symbol]);
                nont_list[symbol] = nt_root;
                nt_root = symbol;

                /* add closure[symbol] to closure of LHS_SYMBOL.  */