Recorded merge of revisions 81029 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/trunk
........
r81029 | antoine.pitrou | 2010-05-09 16:46:46 +0200 (dim., 09 mai 2010) | 3 lines
Untabify C files. Will watch buildbots.
........
diff --git a/Parser/pgen.c b/Parser/pgen.c
index 959a5d3..beaf53b 100644
--- a/Parser/pgen.c
+++ b/Parser/pgen.c
@@ -17,85 +17,85 @@
/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */
typedef struct _nfaarc {
- int ar_label;
- int ar_arrow;
+ int ar_label;
+ int ar_arrow;
} nfaarc;
typedef struct _nfastate {
- int st_narcs;
- nfaarc *st_arc;
+ 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;
+ 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);
+ nfa *nf, node *n, int *pa, int *pb);
static void compile_alt(labellist *ll,
- nfa *nf, node *n, int *pa, int *pb);
+ nfa *nf, node *n, int *pa, int *pb);
static void compile_item(labellist *ll,
- nfa *nf, node *n, int *pa, int *pb);
+ nfa *nf, node *n, int *pa, int *pb);
static void compile_atom(labellist *ll,
- nfa *nf, node *n, int *pa, int *pb);
+ 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;
+ 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;
+ 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;
+ 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;
+ int gr_nnfas;
+ nfa **gr_nfa;
+ labellist gr_ll;
} nfagrammar;
/* Forward */
@@ -104,32 +104,32 @@
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;
+ 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;
+ 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
@@ -137,203 +137,203 @@
static char REQNFMT[] = "metacompile: less than %d children\n";
#define REQN(i, count) \
- if (i < count) { \
- fprintf(stderr, REQNFMT, count); \
- Py_FatalError("REQN"); \
- } else
+ if (i < count) { \
+ fprintf(stderr, REQNFMT, count); \
+ Py_FatalError("REQN"); \
+ } else
#else
-#define REQN(i, count) /* empty */
+#define REQN(i, count) /* empty */
#endif
static nfagrammar *
metacompile(node *n)
{
- nfagrammar *gr;
- int i;
+ 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;
+ 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);
+ 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);
- }
+ 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;
- }
+ 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);
- }
+ 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);
+ 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");
+ 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);
+ 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);
}
@@ -342,184 +342,184 @@
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++;
- }
- }
+ 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;
+ 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;
+ 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;
+ 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);
+ 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... */
+ 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;
- /* 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);
+ 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);
}
static void
printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
- labellist *ll, char *msg)
+ 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]));
- }
- }
+ 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]));
+ }
+ }
}
@@ -535,59 +535,59 @@
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;
+ 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;
- }
- }
+ 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);
+ 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);
}
@@ -598,32 +598,32 @@
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;
+ 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;
}
@@ -632,43 +632,43 @@
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;
+ 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);
- PyObject_FREE(gr);
- return g;
+ nfagrammar *gr;
+ grammar *g;
+
+ gr = metacompile(n);
+ g = maketables(gr);
+ translatelabels(g);
+ addfirstsets(g);
+ PyObject_FREE(gr);
+ return g;
}
grammar *
@@ -702,7 +702,7 @@
---------
[Aho&Ullman 77]
- Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
- (first edition)
+ Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
+ (first edition)
*/