produce.c

一个非常好的检索工具

    int item_no,
        rule_no,
        symbol;

    symbol_seen[source] = TRUE;

    if (IS_IN_NTSET(right_produces, target, source - num_terminals) &&
        IS_IN_NTSET(right_produces, lhs_symbol, source - num_terminals))
        return(FALSE);

    for (item_no = item_of[source];
         item_no != NIL; item_no = next_item[item_no])
    {
        if (item_table[item_no].dot != 0)
            return(TRUE);

        rule_no = item_table[item_no].rule_number;
        symbol = rules[rule_no].lhs;
        if (! symbol_seen[symbol])        /* not yet processed */
        {
            if (scope_check(lhs_symbol, target, symbol))
                return(TRUE);
        }
    }

    return(FALSE);
}


/*********************************************************************/
/*                       INSERT_PREFIX:                              */
/*********************************************************************/
/* This procedure takes as argument an item and inserts the string   */
/* prefix of the item preceeding the "dot" into the scope table, if  */
/* that string is not already there.  In any case, the index  number */
/* associated with the prefix in question is returned.               */
/* NOTE that since both prefixes and suffixes are entered in the     */
/* table, the prefix of a given item, ITEM_NO, is encoded as         */
/* -ITEM_NO, whereas the suffix of that item is encoded as +ITEM_NO. */
/*********************************************************************/
static insert_prefix(int item_no)
{
    int i,
        j,
        rule_no;

    unsigned long hash_address = 0;

    rule_no = item_table[item_no].rule_number;
    for (i = rules[rule_no].rhs;    /* symbols before dot */
         i < rules[rule_no].rhs + item_table[item_no].dot; i++)
        hash_address += rhs_sym[i];

    i = hash_address % SCOPE_SIZE;

    for (j = scope_table[i]; j != NIL; j = scope_element[j].link)
    {
        if (is_prefix_equal(scope_element[j].item, item_no))
            return(scope_element[j].index);
    }
    scope_top++;
    scope_element[scope_top].item = -item_no;
    scope_element[scope_top].index = scope_rhs_size + 1;
    scope_element[scope_top].link = scope_table[i];
    scope_table[i] = scope_top;

    scope_rhs_size += (item_table[item_no].dot + 1);

    return(scope_element[scope_top].index);
}


/******************************************************************/
/*                      IS_PREFIX_EQUAL:                          */
/******************************************************************/
/* This boolean function takes two items as arguments and checks  */
/* whether or not they have the same prefix.                      */
/******************************************************************/
static BOOLEAN is_prefix_equal(int item_no, int item_no2)
{
    int item_no1,
        start,
        dot,
        i,
        j;

    if (item_no > 0)    /* a suffix */
        return(FALSE);

    item_no1 = -item_no;
    if (item_table[item_no1].dot != item_table[item_no2].dot)
        return(FALSE);

    j = rules[item_table[item_no1].rule_number].rhs;
    start = rules[item_table[item_no2].rule_number].rhs;
    dot = start + item_table[item_no2].dot - 1;
    for (i = start; i <= dot; i++)    /* symbols before dot */
    {
        if (rhs_sym[i] != rhs_sym[j])
            return(FALSE);
        j++;
    }

    return(TRUE);
}


/*********************************************************************/
/*                            INSERT_SUFFIX:                         */
/*********************************************************************/
/* This procedure is analoguous to INSERT_PREFIX.  It takes as       */
/* argument an item, and inserts the suffix string following the dot */
/* in the item into the scope table, if it is not already there.     */
/* In any case, it returns the index associated with the suffix.     */
/* When inserting a suffix into the table, all nullable nonterminals */
/* in the suffix are disregarded.                                    */
/*********************************************************************/
static insert_suffix(int item_no)
{
    int i,
        j,
        rule_no,
        num_elements = 0;

    unsigned long hash_address = 0;

    rule_no = item_table[item_no].rule_number;
    for (i = rules[rule_no].rhs + item_table[item_no].dot;
         i < rules[rule_no + 1].rhs; /* symbols after dot */
         i++)
    {
        if (rhs_sym[i] IS_A_NON_TERMINAL)
        {
            if (! null_nt[rhs_sym[i]])
            {
                hash_address += rhs_sym[i];
                num_elements++;
            }
        }
        else if (rhs_sym[i] != error_image)
        {
            hash_address += rhs_sym[i];
            num_elements++;
        }
    }

    i = hash_address % SCOPE_SIZE;

    for (j = scope_table[i]; j != NIL; j = scope_element[j].link)
    {
        if (is_suffix_equal(scope_element[j].item, item_no))
            return(scope_element[j].index);
    }
    scope_top++;
    scope_element[scope_top].item = item_no;
    scope_element[scope_top].index = scope_rhs_size + 1;
    scope_element[scope_top].link = scope_table[i];
    scope_table[i] = scope_top;

    scope_rhs_size += (num_elements + 1);

    return(scope_element[scope_top].index);
}


/******************************************************************/
/*                        IS_SUFFIX_EQUAL:                        */
/******************************************************************/
/* This boolean function takes two items as arguments and checks  */
/* whether or not they have the same suffix.                      */
/******************************************************************/
static BOOLEAN is_suffix_equal(int item_no1, int item_no2)
{
    int rule_no,
        dot1,
        dot2,
        i,
        j;

    if (item_no1 < 0)      /* a prefix */
        return(FALSE);

    rule_no = item_table[item_no1].rule_number;
    i = rules[rule_no].rhs + item_table[item_no1].dot;
    dot1 = rules[rule_no + 1].rhs - 1;

    rule_no = item_table[item_no2].rule_number;
    j = rules[rule_no].rhs + item_table[item_no2].dot;
    dot2 = rules[rule_no + 1].rhs - 1;

    while (i <= dot1 && j <= dot2) /* non-nullable syms before dot */
    {
        if (rhs_sym[i] IS_A_NON_TERMINAL)
        {
            if (null_nt[rhs_sym[i]])
            {
                i++;
                continue;
            }
        }
        else if (rhs_sym[i] == error_image)
        {
            i++;
            continue;
        }

        if (rhs_sym[j] IS_A_NON_TERMINAL)
        {
            if (null_nt[rhs_sym[j]])
            {
                j++;
                continue;
            }
        }
        else if (rhs_sym[j] == error_image)
        {
            j++;
            continue;
        }

        if (rhs_sym[i] != rhs_sym[j])
            return(FALSE);

        j++;
        i++;
    }

    for (; i <= dot1; i++)
    {
        if (rhs_sym[i] IS_A_NON_TERMINAL)
        {
            if (! null_nt[rhs_sym[i]])
                return(FALSE);
        }
        else if (rhs_sym[i] != error_image)
            return(FALSE);
    }

    for (; j <= dot2; j++)
    {
        if (rhs_sym[j] IS_A_NON_TERMINAL)
        {
            if (! null_nt[rhs_sym[j]])
                return(FALSE);
        }
        else if (rhs_sym[j] != error_image)
            return(FALSE);
    }

    return(TRUE);
}


/******************************************************************/
/*                         PRINT_SCOPES:                          */
/******************************************************************/
/* This procedure is similar to the global procedure PTITEM.      */
/******************************************************************/
static void print_scopes(void)
{
    int len,
        offset,
        i,
        k,
        symbol;

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

    PR_HEADING;
    fprintf(syslis, "\nScopes:\n");
    output_line_no += 2;

    for (k=1; k <= num_scopes; k++)
    {
        symbol = scope[k].lhs_symbol;
        restore_symbol(tok, RETRIEVE_STRING(symbol));
        len = PRINT_LINE_SIZE - 5;
        print_large_token(line, tok, "", len);
        strcat(line, " ::= ");
        i = (PRINT_LINE_SIZE / 2) - 1;
        offset = MIN(strlen(line) - 1, i);
        len = PRINT_LINE_SIZE - (offset + 4);

        /* locate end of list */
        for (i = scope[k].prefix; scope_right_side[i] != 0; i++)
            ;

        for (i = i - 1; i >= scope[k].prefix; i--) /* symbols before dot */
        {
            symbol = scope_right_side[i];
            restore_symbol(tok, RETRIEVE_STRING(symbol));
            if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 4)
            {
                fprintf(syslis, "\n%s", line);
                ENDPAGE_CHECK;
                fill_in(tmp, offset, ' ');
                print_large_token(line, tok, tmp, len);
            }
            else
                strcat(line, tok);
            strcat(line, BLANK);
        }

/*********************************************************************/
/* We now add a dot "." to the output line, and print the remaining  */
/* symbols in the right hand side.                                   */
/*********************************************************************/
        strcat(line, " .");
        len = PRINT_LINE_SIZE - (offset + 1);

        for (i = scope[k].suffix;  scope_right_side[i] != 0; i++)
        {
            symbol = scope_right_side[i];
            restore_symbol(tok, RETRIEVE_STRING(symbol));
            if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 1)
            {
                fprintf(syslis, "\n%s", line);
                ENDPAGE_CHECK;
                fill_in(tmp, offset, ' ');
                print_large_token(line, tok, tmp, len);
            }
            else
                strcat(line, tok);
            strcat(line, BLANK);
        }
        fprintf(syslis, "\n%s", line);
        ENDPAGE_CHECK;
    }

    return;
}


/*********************************************************************/
/*                           GET_SHIFT_SYMBOL:                       */
/*********************************************************************/
/* This procedure takes as parameter a nonterminal, LHS_SYMBOL, and  */
/* determines whether or not there is a terminal symbol t such that  */
/* LHS_SYMBOL can rightmost produce a string tX.  If so, t is        */
/* returned, otherwise EMPTY is returned.                            */
/*********************************************************************/
static get_shift_symbol(int lhs_symbol)
{
    int item_no,
        rule_no,
        symbol;

    BOOLEAN end_node;

    struct node *p;

    if (! symbol_seen[lhs_symbol])
    {
        symbol_seen[lhs_symbol] = TRUE;

        for (end_node = ((p = clitems[lhs_symbol]) == NULL);
             ! end_node; end_node = (p == clitems[lhs_symbol]))
        {
            p = p -> next;
            item_no = p -> value;
            rule_no = item_table[item_no].rule_number;
            if (RHS_SIZE(rule_no) > 0)
            {
                symbol = rhs_sym[rules[rule_no].rhs];
                if (symbol IS_A_TERMINAL)
                    return(symbol);
                else
                {
                    symbol = get_shift_symbol(symbol);
                    if (symbol != empty)
                        return(symbol);
                }
            }
        }
    }

    return(empty);
}