closure.c File Reference

#include "defs.h"

Include dependency graph for closure.c:

Go to the source code of this file.

Functions
	set_EFF ()
	Populates EFF, the matrix of Epsilon-Free Firsts. More...
	set_first_derives ()
	Populates first_derives, the matrix of closure productions. More...
	closure (short *nucleus, int n)
	finalize_closure ()

Variables
short *	itemset
short *	itemsetend
unsigned *	ruleset
	Bitset of closure items for the current state. More...
static unsigned *	first_derives
	Matrix of closure productions. More...
static unsigned *	EFF
	Matrix of Epsilon-Free Firsts. More...

Function Documentation

closure	(	short *	nucleus,
		int	n
	)

Definition at line 155 of file closure.c.

References BITS_PER_WORD, first_derives, ISVAR, itemset, itemsetend, nrules, ritem, rrhs, ruleset, and WORDSIZE.

Referenced by generate_states().

{
    register int ruleno;
    register unsigned word;
    register unsigned i;
    register short *csp;
    register unsigned *dsp;
    register unsigned *rsp;
    register int rulesetsize;

    short *csend;
    unsigned *rsend;
    int symbol;
    int itemno;

    rulesetsize = WORDSIZE(nrules);
    rsp = ruleset;
    rsend = ruleset + rulesetsize;
    for (rsp = ruleset; rsp < rsend; rsp++)
        *rsp = 0;

    csend = nucleus + n;
    for (csp = nucleus; csp < csend; ++csp)
    {
        symbol = ritem[*csp];
        if (ISVAR(symbol))
        {
            dsp = first_derives + symbol * rulesetsize;
            rsp = ruleset;
            while (rsp < rsend)
                *rsp++ |= *dsp++;
        }
    }

    ruleno = 0;
    itemsetend = itemset;
    csp = nucleus;
    for (rsp = ruleset; rsp < rsend; ++rsp)
    {
        word = *rsp;
        if (word)
        {
            for (i = 0; i < BITS_PER_WORD; ++i)
            {
                if (word & (1 << i))
                {
                    itemno = rrhs[ruleno+i];
                    while (csp < csend && *csp < itemno)
                        *itemsetend++ = *csp++;
                    *itemsetend++ = itemno;
                    while (csp < csend && *csp == itemno)
                        ++csp;
                }
            }
        }
        ruleno += BITS_PER_WORD;
    }

    while (csp < csend)
        *itemsetend++ = *csp++;

#ifdef DEBUG
    print_closure(n);
#endif
}

Here is the caller graph for this function:

finalize_closure

(

)

Definition at line 225 of file closure.c.

References first_derives, FREE, itemset, nrules, ntokens, ruleset, and WORDSIZE.

Referenced by generate_states().

{
    FREE(itemset);
    FREE(ruleset);
    FREE(first_derives + ntokens * WORDSIZE(nrules));
}

Here is the caller graph for this function:

set_EFF

(

)

Populates EFF, the matrix of Epsilon-Free Firsts.

Let \( V \) be the set of all variables (non-terminals) and \( \mathcal{P} \) the set of all productions.

For each non-terminal \( V_i \), scans all of its productions. If they start with a non-terminal \( V_j \), sets \( \mathrm{EFF}_{i,j} \), thus computing the direct epsilon-free firsts of \( V_i \). It then calls a function that computes the reflexive and transitive closure of such relation.

Definition at line 52 of file closure.c.

References derives, EFF, ISVAR, NEW2, nsyms, nvars, reflexive_transitive_closure(), ritem, rrhs, SETBIT, start_symbol, and WORDSIZE.

Referenced by set_first_derives().

{
    register unsigned *row;
    register int symbol;
    register short *sp;
    register int rowsize;
    register int i;
    register int rule;

    rowsize = WORDSIZE(nvars);
    EFF = NEW2(nvars * rowsize, unsigned);

    row = EFF;
    for (i = start_symbol; i < nsyms; i++)
    {
        sp = derives[i];
        for (rule = *sp; rule > 0; rule = *++sp)
        {
            symbol = ritem[rrhs[rule]];
            if (ISVAR(symbol))
            {
                symbol -= start_symbol;
                SETBIT(row, symbol);
            }
        }
        row += rowsize;
    }

    reflexive_transitive_closure(EFF, nvars);

#ifdef DEBUG
    print_EFF();
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

set_first_derives

(

)

Populates first_derives, the matrix of closure productions.

Let \( V \) be the set of all variables (non-terminals) and \( \mathcal{P} \) the set of all productions.

Using the information saved in EFF, computes the closure productions of each non-terminal. That is, it sets \( \mathrm{first\_derives}_{i,j} \) if and only if the left-hand side of \( \mathcal{P}_j \) is a \( V_k \) such that \( \mathrm{EFF}_{i,k} \) is set.

In other words, it calculates the same information as set_EFF(), expanding the list of non-terminals to the list of their productions.

Definition at line 100 of file closure.c.

References BITS_PER_WORD, derives, EFF, first_derives, FREE, NEW2, nrules, nsyms, ntokens, nvars, set_EFF(), SETBIT, start_symbol, and WORDSIZE.

Referenced by generate_states().

{
    register unsigned *rrow;
    register unsigned *vrow;
    register int j;
    register unsigned k;
    register unsigned cword;
    register short *rp;

    int rule;
    int i;
    int rulesetsize;
    int varsetsize;

    rulesetsize = WORDSIZE(nrules);
    varsetsize = WORDSIZE(nvars);
    first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;

    set_EFF();

    rrow = first_derives + ntokens * rulesetsize;
    for (i = start_symbol; i < nsyms; i++)
    {
        vrow = EFF + ((i - ntokens) * varsetsize);
        k = BITS_PER_WORD;
        for (j = start_symbol; j < nsyms; k++, j++)
        {
            if (k >= BITS_PER_WORD)
            {
                cword = *vrow++;
                k = 0;
            }

            if (cword & (1 << k))
            {
                rp = derives[j];
                while ((rule = *rp++) >= 0)
                {
                    SETBIT(rrow, rule);
                }
            }
        }

        vrow += varsetsize;
        rrow += rulesetsize;
    }

#ifdef DEBUG
    print_first_derives();
#endif

    FREE(EFF);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

unsigned* EFF

static

Matrix of Epsilon-Free Firsts.

Let \( V \) be the set of all variables (non-terminals) and \( \mathcal{P} \) the set of all productions.

This is a matrix of \( \left| V \right| \times \left| V \right| \) bits, where entry \( \mathrm{EFF}_{i,j} \) is set if and only if the closure of an item of kind \( A \rightarrow \alpha . V_i \beta \) should include the productions of \( V_j \) (i.e. the closure items of the form \( V_j \rightarrow . \alpha \)).

It can be seen as a relation \( V \rightarrow 2^V \).

Definition at line 40 of file closure.c.

Referenced by set_EFF(), and set_first_derives().

unsigned* first_derives

static

Matrix of closure productions.

Let \( V \) be the set of all variables (non-terminals) and \( \mathcal{P} \) the set of all productions.

This is a matrix of \( \left| V \right| \times \left| \mathcal{P} \right| \) bits, where entry \( \mathrm{first\_derives}_{i,j} \) is set if and only if the closure of an item of kind \( A \rightarrow \alpha . V_i \beta \) should include the production \( \mathcal{P}_j \) (with the dot on the far left).

It can be seen as a relation \( V \rightarrow 2^{\mathcal{P}} \).

Definition at line 27 of file closure.c.

Referenced by closure(), finalize_closure(), and set_first_derives().

short* itemset

Definition at line 3 of file closure.c.

Referenced by closure(), finalize_closure(), generate_states(), new_itemsets(), and save_reductions().

short* itemsetend

Definition at line 4 of file closure.c.

Referenced by closure(), new_itemsets(), and save_reductions().

unsigned* ruleset

Bitset of closure items for the current state.

The n-th bit is set if and only if the n-th rule is part of the closure of the currently analyzed state. This variable is allocated in generate_states(), overwritten by each iteration of closure() and deleted in finalize_closure().

Definition at line 13 of file closure.c.

Referenced by closure(), finalize_closure(), and generate_states().