mkfirst.c

一个非常好的检索工具

/* $Id: mkfirst.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
/*
 This software is subject to the terms of the IBM Jikes Compiler
 License Agreement available at the following URL:
 http://www.ibm.com/research/jikes.
 Copyright (C) 1983, 1999, International Business Machines Corporation
 and others.  All Rights Reserved.
 You must accept the terms of that agreement to use this software.
*/
static char hostfile[] = __FILE__;

#include <string.h>
#include "common.h"
#include "header.h"

#define LEN (PRINT_LINE_SIZE - 4)
#define NEXT_RULE_SIZE (num_rules + 1)
#define LAST_RHS_INDEX(rule_no) rules[rule_no + 1].rhs - 1

#define INIT_FIRST(nt) \
        { \
            register int k; \
            for (k = 0; k < term_set_size; k++)\
                 first[nt * term_set_size + k] = 0;\
        }

static BOOLEAN is_terminal_rhs(short *rhs_start,
                               BOOLEAN *produces_terminals, int rule_no);
static BOOLEAN is_nullable_rhs(short *rhs_start, int rule_no);
static void compute_first(int nt);
static void print_unreachables(void);
static void print_xref(void);
static void print_nt_first(void);
static void print_follow_map(void);
static short first_map(int root, int tail);
static void s_first(int root, int tail, int set);
static void compute_follow(int nt);
static void quick_sym(short array[], int l, int h);
static void check_non_terminals(void);
static void no_rules_produced(void);
static void nullables_computation(void);
static void compute_closure(int lhs_symbol);
static void compute_produces(int symbol);

static struct f_element_type
{
    short suffix_root,
          suffix_tail,
          link;
} *first_element;

static struct node **direct_produces;
static SET_PTR produces;

/****************************************************************************/
/* TOP, STACK, and INDEX_OF are used for the linear graph algorithm in      */
/* constructing the FIRST, FOLLOW and CLOSURE maps.                         */
/*                                                                          */
/* LHS_RULE and NEXT_RULE are used in constructing a map from non-terminals */
/* to the set of rules produced by the non-terminals.                       */
/*                                                                          */
/* FIRSTis an array used as a hash table to construct                       */
/* the mapping from sequence of symbols to their FIRST terminal             */
/* set.  A sequence is hashed into a location depending on the              */
/* first symbol in that sequence.                                           */
/*                                                                          */
/* FIRST_ITEM_OF is a map from each rule into the first item                */
/* that it generates.                                                       */
/*                                                                          */
/* The following pointers are used to construct a mapping from each symbol  */
/* in the grammar into the set of items denoted by that symbol. I.e.,       */
/*                                                                          */
/*     f(t) := { [A -> x .t y] | A -> x t y is a rule in the grammar }      */
/*                                                                          */
/* Since these sets are simply partitions of the set of items, they are kept*/
/* all in a sequential list in the array NEXT_ITEM.  The roots of the lists */
/* are placed in the arrats T_ITEMS and NT_ITEMS.                           */
/****************************************************************************/
static short *stack,
             *index_of,

             *lhs_rule,
             *next_rule,

             *first_table,
             *first_item_of,

             *next_item,
             *nt_items,
             *nt_list;

static int top;

/*****************************************************************************/
/*                               MKFIRST:                                    */
/*****************************************************************************/
/*    MKFIRST constructs the FIRST and FOLLOW maps, the CLOSURE map,         */
/* ADEQUATE_ITEM and ITEM_TABLE maps and all other basic maps.               */
/*****************************************************************************/
void mkfirst(void)
{
    int symbol,
        nt,
        item_no,
        first_of_empty,
        rule_no,
        i;

    BOOLEAN end_node;

    term_set_size = num_terminals / SIZEOF_BC
                  + (num_terminals % SIZEOF_BC ? 1 : 0);
    non_term_set_size = num_non_terminals / SIZEOF_BC
                      + (num_non_terminals % SIZEOF_BC ? 1 : 0);

    /* allocate various arrays */

    lhs_rule = Allocate_short_array(num_non_terminals);
    lhs_rule -= (num_terminals + 1);

    next_rule = Allocate_short_array(NEXT_RULE_SIZE);
    first_item_of = Allocate_short_array(NEXT_RULE_SIZE);
    stack = Allocate_short_array(num_non_terminals + 1);

    index_of = Allocate_short_array(num_non_terminals);
    index_of -= (num_terminals + 1);

    /*********************************************************************/
    /* NT_FIRST is used to construct a mapping from non-terminals to the */
    /* set of terminals taht may appear first in a string derived from   */
    /* the non-terminal.                                                 */
    /*********************************************************************/
    nt_first = (SET_PTR)
               calloc(num_non_terminals,
                      term_set_size * sizeof(BOOLEAN_CELL));
    if (nt_first == NULL)
        nospace(__FILE__, __LINE__);

    nt_first -= ((num_terminals + 1) * term_set_size);

    next_item = Allocate_short_array(num_items + 1);

    nt_items = Allocate_short_array(num_non_terminals);
    nt_items -= (num_terminals + 1);

    nt_list = Allocate_short_array(num_non_terminals);
    nt_list -= (num_terminals + 1);

    first_element = (struct f_element_type *)
                    calloc(num_items + 1, sizeof(struct f_element_type));
    if (first_element == NULL)
        nospace(__FILE__, __LINE__);

    item_table = (struct itemtab *)
                 calloc(num_items + 1, sizeof(struct itemtab));
    if (item_table == NULL)
        nospace(__FILE__, __LINE__);

    for ALL_NON_TERMINALS(i) /* Initialize LHS_RULE to NIL */
        lhs_rule[i] = NIL;

    /**************************************************************/
    /* In this loop, we construct the LHS_RULE map which maps     */
    /* each non-terminal symbol into the set of rules it produces */
    /**************************************************************/
    for ALL_RULES(rule_no)
    {
        symbol = rules[rule_no].lhs;
        if (lhs_rule[symbol] == NIL)
            next_rule[rule_no] = rule_no;
        else
        {
            next_rule[rule_no] = next_rule[lhs_rule[symbol]];
            next_rule[lhs_rule[symbol]]  = rule_no;
        }
        lhs_rule[symbol] = rule_no;
    }

    /*************************************************************/
    /* Check if there are any non-terminals that do not produce  */
    /* any rules.                                                */
    /*************************************************************/

    no_rules_produced();

    /*************************************************************/
    /* Construct the CLOSURE map of non-terminals.               */
    /*************************************************************/
    closure = (struct node **)
              calloc(num_non_terminals, sizeof(struct node *));
    if (closure == NULL)
        nospace(__FILE__, __LINE__);
    closure -= (num_terminals + 1);

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

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

    /*************************************************************/
    /* Construct the NULL_NT map for non-terminals.              */
    /* A non-terminal B is said to be nullable if either:        */
    /*    B -> %empty  or  B -> B1 B2 B3 ... Bk  where Bi is     */
    /*                         nullable for 1 <= i <= k          */
    /*************************************************************/
    null_nt = Allocate_boolean_array(num_non_terminals);
    null_nt -= (num_terminals + 1);

    nullables_computation();

    /*************************************************************/
    /* Construct the FIRST map for non-terminals and also a list */
    /* of non-terminals whose first set is empty.                */
    /*************************************************************/
    for ALL_NON_TERMINALS(i) /* Initialize INDEX_OF to OMEGA */
        index_of[i] = OMEGA;
    top = 0;
    for ALL_NON_TERMINALS(nt)
    {
        if (index_of[nt] == OMEGA)
            compute_first(nt);
    }

    /*************************************************************/
    /*  Since every input source will be followed by the EOFT    */
    /*  symbol, FIRST[accept_image] cannot contain empty but     */
    /*  instead must contain the EOFT symbol.                    */
    /*************************************************************/
    if (null_nt[accept_image])
    {
        null_nt[accept_image] = FALSE;
        RESET_BIT_IN(nt_first, accept_image, empty);
        SET_BIT_IN(nt_first, accept_image, eoft_image);
    }

    /***************************************************************/
    /* Check whether there are any non-terminals that do not       */
    /* generate any terminal strings. If so, signal error and stop.*/
    /***************************************************************/

    check_non_terminals();

    /***************************************************************/
    /* Construct the ITEM_TABLE, FIRST_ITEM_OF, and NT_ITEMS maps. */
    /***************************************************************/

    first_table = Allocate_short_array(num_symbols + 1);

    for ALL_SYMBOLS(i) /* Initialize FIRST_TABLE to NIL */
        first_table[i] = NIL;

    top = 1;
    first_of_empty = top;
    first_element[first_of_empty].suffix_root = 1;
    first_element[first_of_empty].suffix_tail = 0;

    for ALL_NON_TERMINALS(i) /* Initialize NT_ITEMS to NIL */
        nt_items[i] = NIL;

    item_no = 0;
    item_table[item_no].rule_number = 0;
    item_table[item_no].symbol = empty;
    item_table[item_no].dot = 0;
    item_table[item_no].suffix_index = NIL;

    for ALL_RULES(rule_no)
    {
        int j,
            k;

        first_item_of[rule_no] = item_no + 1;
        j = 0;
        k = LAST_RHS_INDEX(rule_no);
        for ENTIRE_RHS(i, rule_no)
        {
            item_no++;
            symbol = rhs_sym[i];
            item_table[item_no].rule_number = rule_no;
            item_table[item_no].symbol = symbol;
            item_table[item_no].dot = j;

            if (lalr_level > 1 ||
                symbol IS_A_NON_TERMINAL ||
                symbol == error_image)
            {
                if (i == k)
                    item_table[item_no].suffix_index = first_of_empty;
                else
                    item_table[item_no].suffix_index = first_map(i + 1, k);
            }
            else
                item_table[item_no].suffix_index = NIL;

            if (symbol IS_A_NON_TERMINAL)
            {
                next_item[item_no] = nt_items[symbol];
                nt_items[symbol] = item_no;
            }
            j++;
        }

        item_table[++item_no].rule_number = rule_no;
        item_table[item_no].symbol = empty;
        item_table[item_no].dot = j;
        item_table[item_no].suffix_index = NIL;
    }


    /***************************************************************/
    /* We now compute the first set for all suffixes that were     */
    /* inserted in the FIRST_TABLE map. There are TOP such suffixes*/
    /* Extra space is also allocated to compute the first set for  */
    /* suffixes whose left-hand side is the ACCEPT non-terminal.   */
    /* The first set for these suffixes are the sets needed to     */
    /* construct the FOLLOW map and compute look-ahead sets.  They */
    /* are placed in the FIRST table in the range 1..NUM_FIRST_SETS*/
    /* The first element in the FIRST table contains the first sets*/
    /* for the empty sequence.                                     */
    /***************************************************************/
    num_first_sets = top;

    for (end_node = ((rule_no = lhs_rule[accept_image]) == NIL);
         ! end_node;
         end_node = (rule_no == lhs_rule[accept_image]))
    {
        rule_no = next_rule[rule_no];
        num_first_sets++;
    }

    first = (SET_PTR)
            calloc(num_first_sets + 1, term_set_size * sizeof(BOOLEAN_CELL));
    if (first == NULL)
        nospace(__FILE__, __LINE__);
    for (i = 1; i <= top; i++)
    {
        s_first(first_element[i].suffix_root,
                first_element[i].suffix_tail, i);
    }

    rule_no = lhs_rule[accept_image];
    for (i = top + 1; i <= num_first_sets; i++)
    {
        rule_no = next_rule[rule_no];
        item_no = first_item_of[rule_no];
        item_table[item_no].suffix_index = i;
        INIT_FIRST(i);
        SET_BIT_IN(first, i, eoft_image);
    }

    /***************************************************************/
    /* If the READ/REDUCE option is on, we precalculate the kernel */
    /* of the final states which simply consists of the last item  */
    /* in  the corresponding rule.  Rules with the ACCEPT          */
    /* non-terminal as their left-hand side are not considered so  */
    /* as to let the Accpet action remain as a Reduce action       */
    /* instead of a Goto/Reduce action.                            */
    /***************************************************************/
    adequate_item = (struct node **)
                    calloc(num_rules + 1, sizeof(struct node *));
    if (adequate_item == NULL)