/* Parser generator */

/* For a description, see the comments at end of this file */

#include "Python.h"
#include "pgenheaders.h"
#include "token.h"
#include "node.h"
#include "grammar.h"
#include "metagrammar.h"
#include "pgen.h"

extern int Py_DebugFlag;
extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */


/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */

typedef struct _nfaarc {
       int     ar_label;
       int     ar_arrow;
} nfaarc;

typedef struct _nfastate {
       int     st_narcs;
       nfaarc  *st_arc;
} nfastate;

typedef struct _nfa {
       int             nf_type;
       char            *nf_name;
       int             nf_nstates;
       nfastate        *nf_state;
       int             nf_start, nf_finish;
} nfa;

/* Forward */
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)
{
       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;
}

static void
addnfaarc(nfa *nf, int from, int to, int lbl)
{
       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;
}

static nfa *
newnfa(char *name)
{
       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;
}

typedef struct _nfagrammar {
       int             gr_nnfas;
       nfa             **gr_nfa;
       labellist       gr_ll;
} nfagrammar;

/* Forward */
static void compile_rule(nfagrammar *gr, node *n);

static nfagrammar *
newnfagrammar(void)
{
       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;
}

static nfa *
addnfa(nfagrammar *gr, char *name)
{
       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;
}

#ifdef Py_DEBUG

static char REQNFMT[] = "metacompile: less than %d children\n";

#define REQN(i, count) \
       if (i < count) { \
               fprintf(stderr, REQNFMT, count); \
               Py_FatalError("REQN"); \
       } else

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

static nfagrammar *
metacompile(node *n)
{
       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;
}

static void
compile_rule(nfagrammar *gr, node *n)
{
       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);
}

static void
compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
{
       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);
       }
}

static void
compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
{
       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;
       }
}

static void
compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
{
       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);
       }
}

static void
compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
{
       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);
}

static void
dumpstate(labellist *ll, nfa *nf, int istate)
{
       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");
}

static void
dumpnfa(labellist *ll, nfa *nf)
{
       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);
}


/* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */

static void
addclosure(bitset ss, nfa *nf, int istate)
{
       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++;
               }
       }
}

typedef struct _ss_arc {
       bitset  sa_bitset;
       int     sa_arrow;
       int     sa_label;
} ss_arc;

typedef struct _ss_state {
       bitset  ss_ss;
       int     ss_narcs;
       struct _ss_arc  *ss_arc;
       int     ss_deleted;
       int     ss_finish;
       int     ss_rename;
} ss_state;

typedef struct _ss_dfa {
       int     sd_nstates;
       ss_state *sd_state;
} ss_dfa;

/* Forward */
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)
{
       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 */
}

static void
printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
          labellist *ll, char *msg)
{
       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]));
               }
       }
}


/* PART THREE -- SIMPLIFY DFA */

/* Simplify the DFA by repeatedly eliminating states that are
  equivalent to another oner.  This is NOT Algorithm 3.3 from
  [Aho&Ullman 77].  It does not always finds the minimal DFA,
  but it does usually make a much smaller one...  (For an example
  of sub-optimal behavior, try S: x a b+ | y a b+.)
*/

static int
samestate(ss_state *s1, ss_state *s2)
{
       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;
}

static void
renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
{
       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;
               }
       }
}

static void
simplify(int xx_nstates, ss_state *xx_state)
{
       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);
}


/* PART FOUR -- GENERATE PARSING TABLES */

/* Convert the DFA into a grammar that can be used by our parser */

static void
convert(dfa *d, int xx_nstates, ss_state *xx_state)
{
       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;
}


/* PART FIVE -- GLUE IT ALL TOGETHER */

static grammar *
maketables(nfagrammar *gr)
{
       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;
}

grammar *
pgen(node *n)
{
       nfagrammar *gr;
       grammar *g;

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

grammar *
Py_pgen(node *n)
{
 return pgen(n);
}

/*

Description
-----------

Input is a grammar in extended BNF (using * for repetition, + for
at-least-once repetition, [] for optional parts, | for alternatives and
() for grouping).  This has already been parsed and turned into a parse
tree.

Each rule is considered as a regular expression in its own right.
It is turned into a Non-deterministic Finite Automaton (NFA), which
is then turned into a Deterministic Finite Automaton (DFA), which is then
optimized to reduce the number of states.  See [Aho&Ullman 77] chapter 3,
or similar compiler books (this technique is more often used for lexical
analyzers).

The DFA's are used by the parser as parsing tables in a special way
that's probably unique.  Before they are usable, the FIRST sets of all
non-terminals are computed.

Reference
---------

[Aho&Ullman 77]
       Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
       (first edition)

*/

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.