Back to index

python3.2  3.2.2
Classes | Defines | Typedefs | Functions | Variables
pgen.c File Reference
#include "Python.h"
#include "pgenheaders.h"
#include "token.h"
#include "node.h"
#include "grammar.h"
#include "metagrammar.h"
#include "pgen.h"

Go to the source code of this file.

Classes

struct  _nfaarc
struct  _nfastate
struct  _nfa
struct  _nfagrammar
struct  _ss_arc
struct  _ss_state
struct  _ss_dfa

Defines

#define REQN(i, count)   /* empty */

Typedefs

typedef struct _nfaarc nfaarc
typedef struct _nfastate nfastate
typedef struct _nfa nfa
typedef struct _nfagrammar nfagrammar
typedef struct _ss_arc ss_arc
typedef struct _ss_state ss_state
typedef struct _ss_dfa ss_dfa

Functions

static void compile_rhs (labellist *ll, nfa *nf, node *n, int *pa, int *pb)
static void compile_alt (labellist *ll, nfa *nf, node *n, int *pa, int *pb)
static void compile_item (labellist *ll, nfa *nf, node *n, int *pa, int *pb)
static void compile_atom (labellist *ll, nfa *nf, node *n, int *pa, int *pb)
static int addnfastate (nfa *nf)
static void addnfaarc (nfa *nf, int from, int to, int lbl)
static nfanewnfa (char *name)
static void compile_rule (nfagrammar *gr, node *n)
static nfagrammarnewnfagrammar (void)
static nfaaddnfa (nfagrammar *gr, char *name)
static nfagrammarmetacompile (node *n)
static void dumpstate (labellist *ll, nfa *nf, int istate)
static void dumpnfa (labellist *ll, nfa *nf)
static void addclosure (bitset ss, nfa *nf, int istate)
static void printssdfa (int xx_nstates, ss_state *xx_state, int nbits, labellist *ll, char *msg)
static void simplify (int xx_nstates, ss_state *xx_state)
static void convert (dfa *d, int xx_nstates, ss_state *xx_state)
static void makedfa (nfagrammar *gr, nfa *nf, dfa *d)
static int samestate (ss_state *s1, ss_state *s2)
static void renamestates (int xx_nstates, ss_state *xx_state, int from, int to)
static grammarmaketables (nfagrammar *gr)
grammarpgen (node *n)
grammarPy_pgen (node *n)

Variables

int Py_DebugFlag
int Py_IgnoreEnvironmentFlag

Class Documentation

struct _nfaarc

Definition at line 19 of file pgen.c.

Class Members
int ar_arrow
int ar_label
struct _nfastate

Definition at line 24 of file pgen.c.

Collaboration diagram for _nfastate:
Class Members
nfaarc * st_arc
int st_narcs
struct _nfa

Definition at line 29 of file pgen.c.

Collaboration diagram for _nfa:
Class Members
int nf_finish
char * nf_name
int nf_nstates
int nf_start
nfastate * nf_state
int nf_type
struct _nfagrammar

Definition at line 95 of file pgen.c.

Collaboration diagram for _nfagrammar:
Class Members
labellist gr_ll
nfa ** gr_nfa
int gr_nnfas
struct _ss_arc

Definition at line 358 of file pgen.c.

Class Members
int sa_arrow
bitset sa_bitset
int sa_label
struct _ss_state

Definition at line 364 of file pgen.c.

Collaboration diagram for _ss_state:
Class Members
struct _ss_arc * ss_arc
int ss_deleted
int ss_finish
int ss_narcs
int ss_rename
bitset ss_ss
struct _ss_dfa

Definition at line 373 of file pgen.c.

Collaboration diagram for _ss_dfa:
Class Members
int sd_nstates
ss_state * sd_state

Define Documentation

#define REQN (   i,
  count 
)    /* empty */

Definition at line 146 of file pgen.c.


Typedef Documentation

typedef struct _nfa nfa
typedef struct _nfaarc nfaarc
typedef struct _nfagrammar nfagrammar
typedef struct _nfastate nfastate
typedef struct _ss_arc ss_arc
typedef struct _ss_dfa ss_dfa
typedef struct _ss_state ss_state

Function Documentation

static void addclosure ( bitset  ss,
nfa nf,
int  istate 
) [static]

Definition at line 343 of file pgen.c.

{
    if (addbit(ss, istate)) {
        nfastate *st = &nf->nf_state[istate];
        nfaarc *ar = st->st_arc;
        int i;

        for (i = st->st_narcs; --i >= 0; ) {
            if (ar->ar_label == EMPTY)
                addclosure(ss, nf, ar->ar_arrow);
            ar++;
        }
    }
}

Here is the caller graph for this function:

static nfa* addnfa ( nfagrammar gr,
char *  name 
) [static]

Definition at line 121 of file pgen.c.

{
    nfa *nf;

    nf = newnfa(name);
    gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
                                  sizeof(nfa*) * (gr->gr_nnfas + 1));
    if (gr->gr_nfa == NULL)
        Py_FatalError("out of mem");
    gr->gr_nfa[gr->gr_nnfas++] = nf;
    addlabel(&gr->gr_ll, NAME, nf->nf_name);
    return nf;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void addnfaarc ( nfa nf,
int  from,
int  to,
int  lbl 
) [static]

Definition at line 63 of file pgen.c.

{
    nfastate *st;
    nfaarc *ar;

    st = &nf->nf_state[from];
    st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,
                                  sizeof(nfaarc) * (st->st_narcs + 1));
    if (st->st_arc == NULL)
        Py_FatalError("out of mem");
    ar = &st->st_arc[st->st_narcs++];
    ar->ar_label = lbl;
    ar->ar_arrow = to;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int addnfastate ( nfa nf) [static]

Definition at line 48 of file pgen.c.

{
    nfastate *st;

    nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,
                                sizeof(nfastate) * (nf->nf_nstates + 1));
    if (nf->nf_state == NULL)
        Py_FatalError("out of mem");
    st = &nf->nf_state[nf->nf_nstates++];
    st->st_narcs = 0;
    st->st_arc = NULL;
    return st - nf->nf_state;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void compile_alt ( labellist ll,
nfa nf,
node n,
int pa,
int pb 
) [static]

Definition at line 221 of file pgen.c.

{
    int i;
    int a, b;

    REQ(n, ALT);
    i = n->n_nchildren;
    REQN(i, 1);
    n = n->n_child;
    REQ(n, ITEM);
    compile_item(ll, nf, n, pa, pb);
    --i;
    n++;
    for (; --i >= 0; n++) {
        REQ(n, ITEM);
        compile_item(ll, nf, n, &a, &b);
        addnfaarc(nf, *pb, a, EMPTY);
        *pb = b;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void compile_atom ( labellist ll,
nfa nf,
node n,
int pa,
int pb 
) [static]

Definition at line 280 of file pgen.c.

{
    int i;

    REQ(n, ATOM);
    i = n->n_nchildren;
    REQN(i, 1);
    n = n->n_child;
    if (n->n_type == LPAR) {
        REQN(i, 3);
        n++;
        REQ(n, RHS);
        compile_rhs(ll, nf, n, pa, pb);
        n++;
        REQ(n, RPAR);
    }
    else if (n->n_type == NAME || n->n_type == STRING) {
        *pa = addnfastate(nf);
        *pb = addnfastate(nf);
        addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
    }
    else
        REQ(n, NAME);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void compile_item ( labellist ll,
nfa nf,
node n,
int pa,
int pb 
) [static]

Definition at line 243 of file pgen.c.

{
    int i;
    int a, b;

    REQ(n, ITEM);
    i = n->n_nchildren;
    REQN(i, 1);
    n = n->n_child;
    if (n->n_type == LSQB) {
        REQN(i, 3);
        n++;
        REQ(n, RHS);
        *pa = addnfastate(nf);
        *pb = addnfastate(nf);
        addnfaarc(nf, *pa, *pb, EMPTY);
        compile_rhs(ll, nf, n, &a, &b);
        addnfaarc(nf, *pa, a, EMPTY);
        addnfaarc(nf, b, *pb, EMPTY);
        REQN(i, 1);
        n++;
        REQ(n, RSQB);
    }
    else {
        compile_atom(ll, nf, n, pa, pb);
        if (--i <= 0)
            return;
        n++;
        addnfaarc(nf, *pb, *pa, EMPTY);
        if (n->n_type == STAR)
            *pb = *pa;
        else
            REQ(n, PLUS);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void compile_rhs ( labellist ll,
nfa nf,
node n,
int pa,
int pb 
) [static]

Definition at line 188 of file pgen.c.

{
    int i;
    int a, b;

    REQ(n, RHS);
    i = n->n_nchildren;
    REQN(i, 1);
    n = n->n_child;
    REQ(n, ALT);
    compile_alt(ll, nf, n, pa, pb);
    if (--i <= 0)
        return;
    n++;
    a = *pa;
    b = *pb;
    *pa = addnfastate(nf);
    *pb = addnfastate(nf);
    addnfaarc(nf, *pa, a, EMPTY);
    addnfaarc(nf, b, *pb, EMPTY);
    for (; --i >= 0; n++) {
        REQ(n, VBAR);
        REQN(i, 1);
        --i;
        n++;
        REQ(n, ALT);
        compile_alt(ll, nf, n, &a, &b);
        addnfaarc(nf, *pa, a, EMPTY);
        addnfaarc(nf, b, *pb, EMPTY);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void compile_rule ( nfagrammar gr,
node n 
) [static]

Definition at line 169 of file pgen.c.

{
    nfa *nf;

    REQ(n, RULE);
    REQN(n->n_nchildren, 4);
    n = n->n_child;
    REQ(n, NAME);
    nf = addnfa(gr, n->n_str);
    n++;
    REQ(n, COLON);
    n++;
    REQ(n, RHS);
    compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
    n++;
    REQ(n, NEWLINE);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void convert ( dfa d,
int  xx_nstates,
ss_state xx_state 
) [static]

Definition at line 599 of file pgen.c.

{
    int i, j;
    ss_state *yy;
    ss_arc *zz;

    for (i = 0; i < xx_nstates; i++) {
        yy = &xx_state[i];
        if (yy->ss_deleted)
            continue;
        yy->ss_rename = addstate(d);
    }

    for (i = 0; i < xx_nstates; i++) {
        yy = &xx_state[i];
        if (yy->ss_deleted)
            continue;
        for (j = 0; j < yy->ss_narcs; j++) {
            zz = &yy->ss_arc[j];
            addarc(d, yy->ss_rename,
                xx_state[zz->sa_arrow].ss_rename,
                zz->sa_label);
        }
        if (yy->ss_finish)
            addarc(d, yy->ss_rename, yy->ss_rename, 0);
    }

    d->d_initial = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void dumpnfa ( labellist ll,
nfa nf 
) [static]

Definition at line 329 of file pgen.c.

{
    int i;

    printf("NFA '%s' has %d states; start %d, finish %d\n",
        nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
    for (i = 0; i < nf->nf_nstates; i++)
        dumpstate(ll, nf, i);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void dumpstate ( labellist ll,
nfa nf,
int  istate 
) [static]

Definition at line 306 of file pgen.c.

{
    nfastate *st;
    int i;
    nfaarc *ar;

    printf("%c%2d%c",
        istate == nf->nf_start ? '*' : ' ',
        istate,
        istate == nf->nf_finish ? '.' : ' ');
    st = &nf->nf_state[istate];
    ar = st->st_arc;
    for (i = 0; i < st->st_narcs; i++) {
        if (i > 0)
            printf("\n    ");
        printf("-> %2d  %s", ar->ar_arrow,
            PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
        ar++;
    }
    printf("\n");
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void makedfa ( nfagrammar gr,
nfa nf,
dfa d 
) [static]

Definition at line 385 of file pgen.c.

{
    int nbits = nf->nf_nstates;
    bitset ss;
    int xx_nstates;
    ss_state *xx_state, *yy;
    ss_arc *zz;
    int istate, jstate, iarc, jarc, ibit;
    nfastate *st;
    nfaarc *ar;

    ss = newbitset(nbits);
    addclosure(ss, nf, nf->nf_start);
    xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
    if (xx_state == NULL)
        Py_FatalError("no mem for xx_state in makedfa");
    xx_nstates = 1;
    yy = &xx_state[0];
    yy->ss_ss = ss;
    yy->ss_narcs = 0;
    yy->ss_arc = NULL;
    yy->ss_deleted = 0;
    yy->ss_finish = testbit(ss, nf->nf_finish);
    if (yy->ss_finish)
        printf("Error: nonterminal '%s' may produce empty.\n",
            nf->nf_name);

    /* This algorithm is from a book written before
       the invention of structured programming... */

    /* For each unmarked state... */
    for (istate = 0; istate < xx_nstates; ++istate) {
        size_t size;
        yy = &xx_state[istate];
        ss = yy->ss_ss;
        /* For all its states... */
        for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
            if (!testbit(ss, ibit))
                continue;
            st = &nf->nf_state[ibit];
            /* For all non-empty arcs from this state... */
            for (iarc = 0; iarc < st->st_narcs; iarc++) {
                ar = &st->st_arc[iarc];
                if (ar->ar_label == EMPTY)
                    continue;
                /* Look up in list of arcs from this state */
                for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
                    zz = &yy->ss_arc[jarc];
                    if (ar->ar_label == zz->sa_label)
                        goto found;
                }
                /* Add new arc for this state */
                size = sizeof(ss_arc) * (yy->ss_narcs + 1);
                yy->ss_arc = (ss_arc *)PyObject_REALLOC(
                                            yy->ss_arc, size);
                if (yy->ss_arc == NULL)
                    Py_FatalError("out of mem");
                zz = &yy->ss_arc[yy->ss_narcs++];
                zz->sa_label = ar->ar_label;
                zz->sa_bitset = newbitset(nbits);
                zz->sa_arrow = -1;
             found:             ;
                /* Add destination */
                addclosure(zz->sa_bitset, nf, ar->ar_arrow);
            }
        }
        /* Now look up all the arrow states */
        for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
            zz = &xx_state[istate].ss_arc[jarc];
            for (jstate = 0; jstate < xx_nstates; jstate++) {
                if (samebitset(zz->sa_bitset,
                    xx_state[jstate].ss_ss, nbits)) {
                    zz->sa_arrow = jstate;
                    goto done;
                }
            }
            size = sizeof(ss_state) * (xx_nstates + 1);
            xx_state = (ss_state *)PyObject_REALLOC(xx_state,
                                                        size);
            if (xx_state == NULL)
                Py_FatalError("out of mem");
            zz->sa_arrow = xx_nstates;
            yy = &xx_state[xx_nstates++];
            yy->ss_ss = zz->sa_bitset;
            yy->ss_narcs = 0;
            yy->ss_arc = NULL;
            yy->ss_deleted = 0;
            yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
         done:          ;
        }
    }

    if (Py_DebugFlag)
        printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
                                        "before minimizing");

    simplify(xx_nstates, xx_state);

    if (Py_DebugFlag)
        printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
                                        "after minimizing");

    convert(d, xx_nstates, xx_state);

    /* XXX cleanup */
    PyObject_FREE(xx_state);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static grammar* maketables ( nfagrammar gr) [static]

Definition at line 633 of file pgen.c.

{
    int i;
    nfa *nf;
    dfa *d;
    grammar *g;

    if (gr->gr_nnfas == 0)
        return NULL;
    g = newgrammar(gr->gr_nfa[0]->nf_type);
                    /* XXX first rule must be start rule */
    g->g_ll = gr->gr_ll;

    for (i = 0; i < gr->gr_nnfas; i++) {
        nf = gr->gr_nfa[i];
        if (Py_DebugFlag) {
            printf("Dump of NFA for '%s' ...\n", nf->nf_name);
            dumpnfa(&gr->gr_ll, nf);
            printf("Making DFA for '%s' ...\n", nf->nf_name);
        }
        d = adddfa(g, nf->nf_type, nf->nf_name);
        makedfa(gr, gr->gr_nfa[i], d);
    }

    return g;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static nfagrammar* metacompile ( node n) [static]

Definition at line 150 of file pgen.c.

{
    nfagrammar *gr;
    int i;

    if (Py_DebugFlag)
        printf("Compiling (meta-) parse tree into NFA grammar\n");
    gr = newnfagrammar();
    REQ(n, MSTART);
    i = n->n_nchildren - 1; /* Last child is ENDMARKER */
    n = n->n_child;
    for (; --i >= 0; n++) {
        if (n->n_type != NEWLINE)
            compile_rule(gr, n);
    }
    return gr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static nfa* newnfa ( char *  name) [static]

Definition at line 79 of file pgen.c.

{
    nfa *nf;
    static int type = NT_OFFSET; /* All types will be disjunct */

    nf = (nfa *)PyObject_MALLOC(sizeof(nfa));
    if (nf == NULL)
        Py_FatalError("no mem for new nfa");
    nf->nf_type = type++;
    nf->nf_name = name; /* XXX strdup(name) ??? */
    nf->nf_nstates = 0;
    nf->nf_state = NULL;
    nf->nf_start = nf->nf_finish = -1;
    return nf;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static nfagrammar* newnfagrammar ( void  ) [static]

Definition at line 105 of file pgen.c.

{
    nfagrammar *gr;

    gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));
    if (gr == NULL)
        Py_FatalError("no mem for new nfa grammar");
    gr->gr_nnfas = 0;
    gr->gr_nfa = NULL;
    gr->gr_ll.ll_nlabels = 0;
    gr->gr_ll.ll_label = NULL;
    addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
    return gr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

grammar* pgen ( node n)

Definition at line 661 of file pgen.c.

{
    nfagrammar *gr;
    grammar *g;

    gr = metacompile(n);
    g = maketables(gr);
    translatelabels(g);
    addfirstsets(g);
    PyObject_FREE(gr);
    return g;
}

Here is the call graph for this function:

static void printssdfa ( int  xx_nstates,
ss_state xx_state,
int  nbits,
labellist ll,
char *  msg 
) [static]

Definition at line 494 of file pgen.c.

{
    int i, ibit, iarc;
    ss_state *yy;
    ss_arc *zz;

    printf("Subset DFA %s\n", msg);
    for (i = 0; i < xx_nstates; i++) {
        yy = &xx_state[i];
        if (yy->ss_deleted)
            continue;
        printf(" Subset %d", i);
        if (yy->ss_finish)
            printf(" (finish)");
        printf(" { ");
        for (ibit = 0; ibit < nbits; ibit++) {
            if (testbit(yy->ss_ss, ibit))
                printf("%d ", ibit);
        }
        printf("}\n");
        for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
            zz = &yy->ss_arc[iarc];
            printf("  Arc to state %d, label %s\n",
                zz->sa_arrow,
                PyGrammar_LabelRepr(
                    &ll->ll_label[zz->sa_label]));
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

grammar* Py_pgen ( node n)

Definition at line 675 of file pgen.c.

{
  return pgen(n);
}
static void renamestates ( int  xx_nstates,
ss_state xx_state,
int  from,
int  to 
) [static]

Definition at line 551 of file pgen.c.

{
    int i, j;

    if (Py_DebugFlag)
        printf("Rename state %d to %d.\n", from, to);
    for (i = 0; i < xx_nstates; i++) {
        if (xx_state[i].ss_deleted)
            continue;
        for (j = 0; j < xx_state[i].ss_narcs; j++) {
            if (xx_state[i].ss_arc[j].sa_arrow == from)
                xx_state[i].ss_arc[j].sa_arrow = to;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int samestate ( ss_state s1,
ss_state s2 
) [static]

Definition at line 536 of file pgen.c.

{
    int i;

    if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
        return 0;
    for (i = 0; i < s1->ss_narcs; i++) {
        if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
            s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
            return 0;
    }
    return 1;
}

Here is the caller graph for this function:

static void simplify ( int  xx_nstates,
ss_state xx_state 
) [static]

Definition at line 568 of file pgen.c.

{
    int changes;
    int i, j;

    do {
        changes = 0;
        for (i = 1; i < xx_nstates; i++) {
            if (xx_state[i].ss_deleted)
                continue;
            for (j = 0; j < i; j++) {
                if (xx_state[j].ss_deleted)
                    continue;
                if (samestate(&xx_state[i], &xx_state[j])) {
                    xx_state[i].ss_deleted++;
                    renamestates(xx_nstates, xx_state,
                                 i, j);
                    changes++;
                    break;
                }
            }
        }
    } while (changes);
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Definition at line 25 of file pgenmain.c.

Definition at line 27 of file pgenmain.c.