mkfirst.c

一个非常好的检索工具

            fprintf(syslis, "\n\n");
            strcpy(line, "        "); /* 8 spaces */
        }
        else
            strcpy(line, "*** The following Terminal is useless: ");

        for (symbol = t_root; symbol != NIL; symbol = symbol_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);
             }
             strcat(line, BLANK);
        }
        PRNT(line);
    }


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

    if (nt_root != NIL)
    {
        PR_HEADING;
        if (symbol_list[nt_root] != NIL)
        {
            PRNT("*** The following Non-Terminals are useless: ");
            fprintf(syslis, "\n\n");
            strcpy(line, "        "); /* 8 spaces */
        }
        else
            strcpy(line, "*** The following Non-Terminal is useless: ");

        for (symbol = nt_root; symbol != NIL; symbol = symbol_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);
    }

    ffree(symbol_list);

    return;
}


/*****************************************************************************/
/*                               PRINT_XREF:                                 */
/*****************************************************************************/
/* PRINT_XREF prints out the Cross-reference map. We build a map from each   */
/* terminal into the set of items whose Dot-symbol (symbol immediately       */
/* following the dot ) is the terminal in question.  Note that we iterate    */
/* backwards over the rules to keep the rules associated with the items      */
/* sorted, since they are inserted in STACK fashion in the lists:  Last-in,  */
/* First out.                                                                */
/*****************************************************************************/
static void print_xref(void)
{
    short *sort_sym,
          *t_items;

    int i,
        offset,
        rule_no,
        item_no,
        symbol;

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

    /*********************************************************************/
    /* SORT_SYM is used to sort the symbols for cross_reference listing. */
    /*********************************************************************/
    sort_sym = Allocate_short_array(num_symbols + 1);
    t_items = Allocate_short_array(num_terminals + 1);

    for ALL_TERMINALS(i)
        t_items[i] = NIL;

    for ALL_RULES_BACKWARDS(rule_no)
    {
        item_no = first_item_of[rule_no];
        for ENTIRE_RHS(i, rule_no)
        {
            symbol = rhs_sym[i];
            if (symbol IS_A_TERMINAL)
            {
                next_item[item_no] = t_items[symbol];
                t_items[symbol] = item_no;
            }
            item_no++;
        }
    }
    for ALL_SYMBOLS(i)
        sort_sym[i] = i;
    quick_sym(sort_sym, 1, num_symbols);

    PR_HEADING;
    fprintf(syslis, "\n\nCross-reference table:\n");
    output_line_no += 3;
    for ALL_SYMBOLS(i)
    {
        symbol = sort_sym[i];
        if (symbol != accept_image && symbol != eoft_image
                                   && symbol != empty)
        {
            fprintf(syslis, "\n");
            ENDPAGE_CHECK;
            restore_symbol(tok, RETRIEVE_STRING(symbol));
            print_large_token(line, tok, "", PRINT_LINE_SIZE-7);
            strcat(line, "  ==>> ");
            offset = strlen(line) - 1;
            if (symbol IS_A_NON_TERMINAL)
            {
                BOOLEAN end_node;

                for (end_node = ((rule_no = lhs_rule[symbol]) == NIL);
                     ! end_node;
                     end_node = (rule_no == lhs_rule[symbol]))
                {
                    rule_no = next_rule[rule_no];
                    sprintf(tok, "%d", rule_no);
                    if (strlen(tok) + strlen(line) > PRINT_LINE_SIZE)
                    {
                        int j;

                        fprintf(syslis, "\n%s", line);
                        ENDPAGE_CHECK;
                        strcpy(line, BLANK);
                        for (j = 1; j <= offset; j++)
                             strcat(line, BLANK);
                    }
                    strcat(line, tok);
                    strcat(line, BLANK);
                }
                fprintf(syslis, "\n%s", line);
                ENDPAGE_CHECK;
                item_no = nt_items[symbol];
            }
            else
            {
                for (item_no = t_items[symbol];
                     item_no != NIL; item_no = next_item[item_no])
                {
                    rule_no = item_table[item_no].rule_number;
                    sprintf(tok, "%d", rule_no);
                    if (strlen(tok) + strlen(line) > PRINT_LINE_SIZE)
                    {
                        int j;

                        fprintf(syslis, "\n%s", line);
                        ENDPAGE_CHECK;
                        strcpy(line, BLANK);
                        for (j = 1; j <= offset; j++)
                             strcat(line, BLANK);
                    }
                    strcat(line, tok);
                    strcat(line, BLANK);
                }
                fprintf(syslis, "\n%s",line);
                ENDPAGE_CHECK;
            }
        }
    }
    fprintf(syslis, "\n\n");
    output_line_no +=2;
    ffree(t_items);
    ffree(sort_sym);

    return;
}


/*****************************************************************************/
/*                              QUICK_SYM:                                   */
/*****************************************************************************/
/* QUICK_SYM takes as arguments an array of pointers whose elements point to */
/* nodes and two integer arguments: L, H. L and H indicate respectively the  */
/* lower and upper bound of a section in the array.                          */
/*****************************************************************************/
static void quick_sym(short array[], int l, int h)
{
    /**************************************************************/
    /* Since no more than 2**15-1 symbols are allowed, the stack  */
    /* not grow past 14.                                          */
    /**************************************************************/

    int   lostack[14],
          histack[14],
          lower,
          upper,
          top,
          i,
          j;

    short temp,
          pivot;

    top = 1;
    lostack[top] = l;
    histack[top] = h;

    while(top != 0)
    {
        lower = lostack[top];
        upper = histack[top--];

        while(upper > lower)
        {
            /********************************************************/
            /* Split the array section indicated by LOWER and UPPER */
            /* using ARRAY[LOWER] as the pivot.                     */
            /********************************************************/
            i = lower;
            pivot = array[lower];
            for (j = lower + 1; j <= upper; j++)
            {
                if (strcmp(RETRIEVE_STRING(array[j]),
                           RETRIEVE_STRING(pivot)) < 0)
                {
                    temp = array[++i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }

            array[lower] = array[i];
            array[i] = pivot;

            top++;
            if ((i - lower) < (upper - i))
            {
                lostack[top] = i + 1;
                histack[top] = upper;
                upper = i - 1;
            }
            else
            {
                histack[top] = i - 1;
                lostack[top] = lower;
                lower = i + 1;
            }
        }
    }

    return;
}


/*****************************************************************************/
/*                             PRINT_NT_FIRST:                               */
/*****************************************************************************/
/* PRINT_NT_FIRST prints the first set for each non-terminal.                */
/*****************************************************************************/
static void print_nt_first(void)
{
    int nt,
        t;

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

    PR_HEADING;
    fprintf(syslis, "\nFirst map for non-terminals:\n\n");
    output_line_no += 3;

    for ALL_NON_TERMINALS(nt)
    {
        restore_symbol(tok, RETRIEVE_STRING(nt));
        print_large_token(line, tok, "", PRINT_LINE_SIZE - 7);
        strcat(line, "  ==>> ");
        for ALL_TERMINALS(t)
        {
            if (IS_IN_SET(nt_first, nt, t))
            {
                restore_symbol(tok, RETRIEVE_STRING(t));
                if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 1)
                {
                    fprintf(syslis, "\n%s", line);
                    ENDPAGE_CHECK;
                    print_large_token(line, tok, "    ", LEN);
                }
                else
                    strcat(line, tok);
                strcat(line, BLANK);
            }
        }
        fprintf(syslis, "\n%s\n", line);
        output_line_no++;
        ENDPAGE_CHECK;
    }

    return;
}


/*****************************************************************************/
/*                           PRINT_FOLLOW_MAP:                               */
/*****************************************************************************/
/* PRINT_FOLLOW_MAP prints the follow map.                                   */
/*****************************************************************************/
static void print_follow_map(void)
{
    int nt,
        t;

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

    PR_HEADING;
    fprintf(syslis, "\nFollow Map:\n\n");
    output_line_no += 3;

    for ALL_NON_TERMINALS(nt)
    {
        restore_symbol(tok, RETRIEVE_STRING(nt));
        print_large_token(line, tok, "", PRINT_LINE_SIZE-7);
        strcat(line, "  ==>> ");
        for ALL_TERMINALS(t)
        {
            if (IS_IN_SET(follow, nt, t))
            {
                restore_symbol(tok, RETRIEVE_STRING(t));
                if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE-2)
                {
                    fprintf(syslis, "\n%s", line);
                    ENDPAGE_CHECK;
                    print_large_token(line, tok, "    ", LEN);
                }
                else
                    strcat(line, tok);
                strcat(line, BLANK);
            }
        }
        fprintf(syslis, "\n%s\n", line);
        output_line_no++;