blob: 959a5d3443f95398e3cecd223587f00bf0783c7d [file] [log] [blame]
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001/* Parser generator */
2
3/* For a description, see the comments at end of this file */
4
Tim Peters1ca12962001-12-04 03:18:48 +00005#include "Python.h"
Guido van Rossum3f5da241990-12-20 15:06:42 +00006#include "pgenheaders.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00007#include "token.h"
8#include "node.h"
9#include "grammar.h"
10#include "metagrammar.h"
11#include "pgen.h"
12
Guido van Rossum86bea461997-04-29 21:03:06 +000013extern int Py_DebugFlag;
Neal Norwitz5352d8c2002-05-31 13:11:40 +000014extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000015
16
17/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */
18
19typedef struct _nfaarc {
20 int ar_label;
21 int ar_arrow;
22} nfaarc;
23
24typedef struct _nfastate {
25 int st_narcs;
26 nfaarc *st_arc;
27} nfastate;
28
29typedef struct _nfa {
30 int nf_type;
31 char *nf_name;
32 int nf_nstates;
33 nfastate *nf_state;
34 int nf_start, nf_finish;
35} nfa;
36
Guido van Rossum71f477c1991-04-03 19:09:02 +000037/* Forward */
Tim Petersdbd9ba62000-07-09 03:09:57 +000038static void compile_rhs(labellist *ll,
39 nfa *nf, node *n, int *pa, int *pb);
40static void compile_alt(labellist *ll,
41 nfa *nf, node *n, int *pa, int *pb);
42static void compile_item(labellist *ll,
43 nfa *nf, node *n, int *pa, int *pb);
44static void compile_atom(labellist *ll,
45 nfa *nf, node *n, int *pa, int *pb);
Guido van Rossum71f477c1991-04-03 19:09:02 +000046
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000047static int
Thomas Wouters23c9e002000-07-22 19:20:54 +000048addnfastate(nfa *nf)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000049{
50 nfastate *st;
51
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000052 nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,
53 sizeof(nfastate) * (nf->nf_nstates + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000054 if (nf->nf_state == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000055 Py_FatalError("out of mem");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000056 st = &nf->nf_state[nf->nf_nstates++];
57 st->st_narcs = 0;
58 st->st_arc = NULL;
59 return st - nf->nf_state;
60}
61
62static void
Thomas Wouters23c9e002000-07-22 19:20:54 +000063addnfaarc(nfa *nf, int from, int to, int lbl)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000064{
65 nfastate *st;
66 nfaarc *ar;
67
68 st = &nf->nf_state[from];
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000069 st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,
70 sizeof(nfaarc) * (st->st_narcs + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000071 if (st->st_arc == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000072 Py_FatalError("out of mem");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000073 ar = &st->st_arc[st->st_narcs++];
74 ar->ar_label = lbl;
75 ar->ar_arrow = to;
76}
77
78static nfa *
Thomas Wouters23c9e002000-07-22 19:20:54 +000079newnfa(char *name)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000080{
81 nfa *nf;
Guido van Rossumbb3649e1998-04-10 22:09:39 +000082 static int type = NT_OFFSET; /* All types will be disjunct */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000083
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000084 nf = (nfa *)PyObject_MALLOC(sizeof(nfa));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000085 if (nf == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +000086 Py_FatalError("no mem for new nfa");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000087 nf->nf_type = type++;
88 nf->nf_name = name; /* XXX strdup(name) ??? */
89 nf->nf_nstates = 0;
90 nf->nf_state = NULL;
91 nf->nf_start = nf->nf_finish = -1;
92 return nf;
93}
94
95typedef struct _nfagrammar {
96 int gr_nnfas;
97 nfa **gr_nfa;
98 labellist gr_ll;
99} nfagrammar;
100
Guido van Rossum71f477c1991-04-03 19:09:02 +0000101/* Forward */
Tim Petersdbd9ba62000-07-09 03:09:57 +0000102static void compile_rule(nfagrammar *gr, node *n);
Guido van Rossum71f477c1991-04-03 19:09:02 +0000103
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000104static nfagrammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000105newnfagrammar(void)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000106{
107 nfagrammar *gr;
108
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000109 gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000110 if (gr == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +0000111 Py_FatalError("no mem for new nfa grammar");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000112 gr->gr_nnfas = 0;
113 gr->gr_nfa = NULL;
114 gr->gr_ll.ll_nlabels = 0;
115 gr->gr_ll.ll_label = NULL;
116 addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
117 return gr;
118}
119
120static nfa *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000121addnfa(nfagrammar *gr, char *name)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000122{
123 nfa *nf;
124
125 nf = newnfa(name);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000126 gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000127 sizeof(nfa*) * (gr->gr_nnfas + 1));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000128 if (gr->gr_nfa == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +0000129 Py_FatalError("out of mem");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000130 gr->gr_nfa[gr->gr_nnfas++] = nf;
131 addlabel(&gr->gr_ll, NAME, nf->nf_name);
132 return nf;
133}
134
Guido van Rossum408027e1996-12-30 16:17:54 +0000135#ifdef Py_DEBUG
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000136
137static char REQNFMT[] = "metacompile: less than %d children\n";
138
139#define REQN(i, count) \
140 if (i < count) { \
141 fprintf(stderr, REQNFMT, count); \
Guido van Rossum86bea461997-04-29 21:03:06 +0000142 Py_FatalError("REQN"); \
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000143 } else
144
145#else
146#define REQN(i, count) /* empty */
147#endif
148
149static nfagrammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000150metacompile(node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000151{
152 nfagrammar *gr;
153 int i;
Guido van Rossum25dfe2c2001-09-11 16:43:16 +0000154
155 if (Py_DebugFlag)
156 printf("Compiling (meta-) parse tree into NFA grammar\n");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000157 gr = newnfagrammar();
158 REQ(n, MSTART);
159 i = n->n_nchildren - 1; /* Last child is ENDMARKER */
160 n = n->n_child;
161 for (; --i >= 0; n++) {
162 if (n->n_type != NEWLINE)
163 compile_rule(gr, n);
164 }
165 return gr;
166}
167
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000168static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000169compile_rule(nfagrammar *gr, node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000170{
171 nfa *nf;
172
173 REQ(n, RULE);
174 REQN(n->n_nchildren, 4);
175 n = n->n_child;
176 REQ(n, NAME);
177 nf = addnfa(gr, n->n_str);
178 n++;
179 REQ(n, COLON);
180 n++;
181 REQ(n, RHS);
182 compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
183 n++;
184 REQ(n, NEWLINE);
185}
186
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000187static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000188compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000189{
190 int i;
191 int a, b;
192
193 REQ(n, RHS);
194 i = n->n_nchildren;
195 REQN(i, 1);
196 n = n->n_child;
197 REQ(n, ALT);
198 compile_alt(ll, nf, n, pa, pb);
199 if (--i <= 0)
200 return;
201 n++;
202 a = *pa;
203 b = *pb;
204 *pa = addnfastate(nf);
205 *pb = addnfastate(nf);
206 addnfaarc(nf, *pa, a, EMPTY);
207 addnfaarc(nf, b, *pb, EMPTY);
208 for (; --i >= 0; n++) {
209 REQ(n, VBAR);
210 REQN(i, 1);
211 --i;
212 n++;
213 REQ(n, ALT);
214 compile_alt(ll, nf, n, &a, &b);
215 addnfaarc(nf, *pa, a, EMPTY);
216 addnfaarc(nf, b, *pb, EMPTY);
217 }
218}
219
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000220static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000221compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000222{
223 int i;
224 int a, b;
225
226 REQ(n, ALT);
227 i = n->n_nchildren;
228 REQN(i, 1);
229 n = n->n_child;
230 REQ(n, ITEM);
231 compile_item(ll, nf, n, pa, pb);
232 --i;
233 n++;
234 for (; --i >= 0; n++) {
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000235 REQ(n, ITEM);
236 compile_item(ll, nf, n, &a, &b);
237 addnfaarc(nf, *pb, a, EMPTY);
238 *pb = b;
239 }
240}
241
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000242static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000243compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000244{
245 int i;
246 int a, b;
247
248 REQ(n, ITEM);
249 i = n->n_nchildren;
250 REQN(i, 1);
251 n = n->n_child;
252 if (n->n_type == LSQB) {
253 REQN(i, 3);
254 n++;
255 REQ(n, RHS);
256 *pa = addnfastate(nf);
257 *pb = addnfastate(nf);
258 addnfaarc(nf, *pa, *pb, EMPTY);
259 compile_rhs(ll, nf, n, &a, &b);
260 addnfaarc(nf, *pa, a, EMPTY);
261 addnfaarc(nf, b, *pb, EMPTY);
262 REQN(i, 1);
263 n++;
264 REQ(n, RSQB);
265 }
266 else {
267 compile_atom(ll, nf, n, pa, pb);
268 if (--i <= 0)
269 return;
270 n++;
271 addnfaarc(nf, *pb, *pa, EMPTY);
272 if (n->n_type == STAR)
273 *pb = *pa;
274 else
275 REQ(n, PLUS);
276 }
277}
278
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000279static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000280compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000281{
Neal Norwitz46aae192006-01-08 02:06:01 +0000282 int i;
283
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000284 REQ(n, ATOM);
Neal Norwitz46aae192006-01-08 02:06:01 +0000285 i = n->n_nchildren;
286 REQN(i, 1);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000287 n = n->n_child;
288 if (n->n_type == LPAR) {
Neal Norwitz46aae192006-01-08 02:06:01 +0000289 REQN(i, 3);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000290 n++;
291 REQ(n, RHS);
292 compile_rhs(ll, nf, n, pa, pb);
293 n++;
294 REQ(n, RPAR);
295 }
296 else if (n->n_type == NAME || n->n_type == STRING) {
297 *pa = addnfastate(nf);
298 *pb = addnfastate(nf);
299 addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
300 }
301 else
302 REQ(n, NAME);
303}
304
305static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000306dumpstate(labellist *ll, nfa *nf, int istate)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000307{
308 nfastate *st;
309 int i;
310 nfaarc *ar;
311
312 printf("%c%2d%c",
313 istate == nf->nf_start ? '*' : ' ',
314 istate,
315 istate == nf->nf_finish ? '.' : ' ');
316 st = &nf->nf_state[istate];
317 ar = st->st_arc;
318 for (i = 0; i < st->st_narcs; i++) {
319 if (i > 0)
320 printf("\n ");
321 printf("-> %2d %s", ar->ar_arrow,
Guido van Rossum86bea461997-04-29 21:03:06 +0000322 PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000323 ar++;
324 }
325 printf("\n");
326}
327
328static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000329dumpnfa(labellist *ll, nfa *nf)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000330{
331 int i;
332
333 printf("NFA '%s' has %d states; start %d, finish %d\n",
334 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
335 for (i = 0; i < nf->nf_nstates; i++)
336 dumpstate(ll, nf, i);
337}
338
339
340/* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */
341
Guido van Rossum588633d1994-12-30 15:46:02 +0000342static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000343addclosure(bitset ss, nfa *nf, int istate)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000344{
345 if (addbit(ss, istate)) {
346 nfastate *st = &nf->nf_state[istate];
347 nfaarc *ar = st->st_arc;
348 int i;
349
350 for (i = st->st_narcs; --i >= 0; ) {
351 if (ar->ar_label == EMPTY)
352 addclosure(ss, nf, ar->ar_arrow);
353 ar++;
354 }
355 }
356}
357
358typedef struct _ss_arc {
359 bitset sa_bitset;
360 int sa_arrow;
361 int sa_label;
362} ss_arc;
363
364typedef struct _ss_state {
365 bitset ss_ss;
366 int ss_narcs;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000367 struct _ss_arc *ss_arc;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000368 int ss_deleted;
369 int ss_finish;
370 int ss_rename;
371} ss_state;
372
373typedef struct _ss_dfa {
374 int sd_nstates;
375 ss_state *sd_state;
376} ss_dfa;
377
Guido van Rossum71f477c1991-04-03 19:09:02 +0000378/* Forward */
Tim Petersdbd9ba62000-07-09 03:09:57 +0000379static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
380 labellist *ll, char *msg);
381static void simplify(int xx_nstates, ss_state *xx_state);
382static void convert(dfa *d, int xx_nstates, ss_state *xx_state);
Guido van Rossum71f477c1991-04-03 19:09:02 +0000383
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000384static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000385makedfa(nfagrammar *gr, nfa *nf, dfa *d)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000386{
387 int nbits = nf->nf_nstates;
388 bitset ss;
389 int xx_nstates;
390 ss_state *xx_state, *yy;
391 ss_arc *zz;
392 int istate, jstate, iarc, jarc, ibit;
393 nfastate *st;
394 nfaarc *ar;
395
396 ss = newbitset(nbits);
397 addclosure(ss, nf, nf->nf_start);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000398 xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000399 if (xx_state == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +0000400 Py_FatalError("no mem for xx_state in makedfa");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000401 xx_nstates = 1;
402 yy = &xx_state[0];
403 yy->ss_ss = ss;
404 yy->ss_narcs = 0;
405 yy->ss_arc = NULL;
406 yy->ss_deleted = 0;
407 yy->ss_finish = testbit(ss, nf->nf_finish);
408 if (yy->ss_finish)
409 printf("Error: nonterminal '%s' may produce empty.\n",
410 nf->nf_name);
411
412 /* This algorithm is from a book written before
413 the invention of structured programming... */
414
415 /* For each unmarked state... */
416 for (istate = 0; istate < xx_nstates; ++istate) {
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000417 size_t size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000418 yy = &xx_state[istate];
419 ss = yy->ss_ss;
420 /* For all its states... */
421 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
422 if (!testbit(ss, ibit))
423 continue;
424 st = &nf->nf_state[ibit];
425 /* For all non-empty arcs from this state... */
426 for (iarc = 0; iarc < st->st_narcs; iarc++) {
427 ar = &st->st_arc[iarc];
428 if (ar->ar_label == EMPTY)
429 continue;
430 /* Look up in list of arcs from this state */
431 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
432 zz = &yy->ss_arc[jarc];
433 if (ar->ar_label == zz->sa_label)
434 goto found;
435 }
436 /* Add new arc for this state */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000437 size = sizeof(ss_arc) * (yy->ss_narcs + 1);
438 yy->ss_arc = (ss_arc *)PyObject_REALLOC(
439 yy->ss_arc, size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000440 if (yy->ss_arc == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +0000441 Py_FatalError("out of mem");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000442 zz = &yy->ss_arc[yy->ss_narcs++];
443 zz->sa_label = ar->ar_label;
444 zz->sa_bitset = newbitset(nbits);
445 zz->sa_arrow = -1;
446 found: ;
447 /* Add destination */
448 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
449 }
450 }
451 /* Now look up all the arrow states */
452 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
453 zz = &xx_state[istate].ss_arc[jarc];
454 for (jstate = 0; jstate < xx_nstates; jstate++) {
455 if (samebitset(zz->sa_bitset,
456 xx_state[jstate].ss_ss, nbits)) {
457 zz->sa_arrow = jstate;
458 goto done;
459 }
460 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000461 size = sizeof(ss_state) * (xx_nstates + 1);
462 xx_state = (ss_state *)PyObject_REALLOC(xx_state,
463 size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000464 if (xx_state == NULL)
Guido van Rossum86bea461997-04-29 21:03:06 +0000465 Py_FatalError("out of mem");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000466 zz->sa_arrow = xx_nstates;
467 yy = &xx_state[xx_nstates++];
468 yy->ss_ss = zz->sa_bitset;
469 yy->ss_narcs = 0;
470 yy->ss_arc = NULL;
471 yy->ss_deleted = 0;
472 yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
473 done: ;
474 }
475 }
476
Guido van Rossum86bea461997-04-29 21:03:06 +0000477 if (Py_DebugFlag)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000478 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
479 "before minimizing");
480
481 simplify(xx_nstates, xx_state);
482
Guido van Rossum86bea461997-04-29 21:03:06 +0000483 if (Py_DebugFlag)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000484 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
485 "after minimizing");
486
487 convert(d, xx_nstates, xx_state);
488
489 /* XXX cleanup */
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000490 PyObject_FREE(xx_state);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000491}
492
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000493static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000494printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
495 labellist *ll, char *msg)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000496{
497 int i, ibit, iarc;
498 ss_state *yy;
499 ss_arc *zz;
500
501 printf("Subset DFA %s\n", msg);
502 for (i = 0; i < xx_nstates; i++) {
503 yy = &xx_state[i];
504 if (yy->ss_deleted)
505 continue;
506 printf(" Subset %d", i);
507 if (yy->ss_finish)
508 printf(" (finish)");
509 printf(" { ");
510 for (ibit = 0; ibit < nbits; ibit++) {
511 if (testbit(yy->ss_ss, ibit))
512 printf("%d ", ibit);
513 }
514 printf("}\n");
515 for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
516 zz = &yy->ss_arc[iarc];
517 printf(" Arc to state %d, label %s\n",
518 zz->sa_arrow,
Guido van Rossum86bea461997-04-29 21:03:06 +0000519 PyGrammar_LabelRepr(
520 &ll->ll_label[zz->sa_label]));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000521 }
522 }
523}
524
525
526/* PART THREE -- SIMPLIFY DFA */
527
528/* Simplify the DFA by repeatedly eliminating states that are
529 equivalent to another oner. This is NOT Algorithm 3.3 from
530 [Aho&Ullman 77]. It does not always finds the minimal DFA,
531 but it does usually make a much smaller one... (For an example
Thomas Wouters7e474022000-07-16 12:04:32 +0000532 of sub-optimal behavior, try S: x a b+ | y a b+.)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000533*/
534
535static int
Thomas Wouters23c9e002000-07-22 19:20:54 +0000536samestate(ss_state *s1, ss_state *s2)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000537{
538 int i;
539
540 if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
541 return 0;
542 for (i = 0; i < s1->ss_narcs; i++) {
543 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
544 s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
545 return 0;
546 }
547 return 1;
548}
549
550static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000551renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000552{
553 int i, j;
554
Guido van Rossum86bea461997-04-29 21:03:06 +0000555 if (Py_DebugFlag)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000556 printf("Rename state %d to %d.\n", from, to);
557 for (i = 0; i < xx_nstates; i++) {
558 if (xx_state[i].ss_deleted)
559 continue;
560 for (j = 0; j < xx_state[i].ss_narcs; j++) {
561 if (xx_state[i].ss_arc[j].sa_arrow == from)
562 xx_state[i].ss_arc[j].sa_arrow = to;
563 }
564 }
565}
566
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000567static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000568simplify(int xx_nstates, ss_state *xx_state)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000569{
570 int changes;
Guido van Rossum588633d1994-12-30 15:46:02 +0000571 int i, j;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000572
573 do {
574 changes = 0;
575 for (i = 1; i < xx_nstates; i++) {
576 if (xx_state[i].ss_deleted)
577 continue;
578 for (j = 0; j < i; j++) {
579 if (xx_state[j].ss_deleted)
580 continue;
581 if (samestate(&xx_state[i], &xx_state[j])) {
582 xx_state[i].ss_deleted++;
Guido van Rossum86bea461997-04-29 21:03:06 +0000583 renamestates(xx_nstates, xx_state,
584 i, j);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000585 changes++;
586 break;
587 }
588 }
589 }
590 } while (changes);
591}
592
593
594/* PART FOUR -- GENERATE PARSING TABLES */
595
596/* Convert the DFA into a grammar that can be used by our parser */
597
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000598static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000599convert(dfa *d, int xx_nstates, ss_state *xx_state)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000600{
601 int i, j;
602 ss_state *yy;
603 ss_arc *zz;
604
605 for (i = 0; i < xx_nstates; i++) {
606 yy = &xx_state[i];
607 if (yy->ss_deleted)
608 continue;
609 yy->ss_rename = addstate(d);
610 }
611
612 for (i = 0; i < xx_nstates; i++) {
613 yy = &xx_state[i];
614 if (yy->ss_deleted)
615 continue;
616 for (j = 0; j < yy->ss_narcs; j++) {
617 zz = &yy->ss_arc[j];
618 addarc(d, yy->ss_rename,
619 xx_state[zz->sa_arrow].ss_rename,
620 zz->sa_label);
621 }
622 if (yy->ss_finish)
623 addarc(d, yy->ss_rename, yy->ss_rename, 0);
624 }
625
626 d->d_initial = 0;
627}
628
629
630/* PART FIVE -- GLUE IT ALL TOGETHER */
631
632static grammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000633maketables(nfagrammar *gr)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000634{
635 int i;
636 nfa *nf;
637 dfa *d;
638 grammar *g;
639
640 if (gr->gr_nnfas == 0)
641 return NULL;
642 g = newgrammar(gr->gr_nfa[0]->nf_type);
643 /* XXX first rule must be start rule */
644 g->g_ll = gr->gr_ll;
645
646 for (i = 0; i < gr->gr_nnfas; i++) {
647 nf = gr->gr_nfa[i];
Guido van Rossum86bea461997-04-29 21:03:06 +0000648 if (Py_DebugFlag) {
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000649 printf("Dump of NFA for '%s' ...\n", nf->nf_name);
650 dumpnfa(&gr->gr_ll, nf);
Guido van Rossum25dfe2c2001-09-11 16:43:16 +0000651 printf("Making DFA for '%s' ...\n", nf->nf_name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000652 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000653 d = adddfa(g, nf->nf_type, nf->nf_name);
654 makedfa(gr, gr->gr_nfa[i], d);
655 }
656
657 return g;
658}
659
660grammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000661pgen(node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000662{
663 nfagrammar *gr;
664 grammar *g;
665
666 gr = metacompile(n);
667 g = maketables(gr);
668 translatelabels(g);
669 addfirstsets(g);
Christian Heimes679db4a2008-01-18 09:56:22 +0000670 PyObject_FREE(gr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000671 return g;
672}
673
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000674grammar *
675Py_pgen(node *n)
676{
677 return pgen(n);
678}
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000679
680/*
681
682Description
683-----------
684
685Input is a grammar in extended BNF (using * for repetition, + for
686at-least-once repetition, [] for optional parts, | for alternatives and
687() for grouping). This has already been parsed and turned into a parse
688tree.
689
690Each rule is considered as a regular expression in its own right.
691It is turned into a Non-deterministic Finite Automaton (NFA), which
692is then turned into a Deterministic Finite Automaton (DFA), which is then
693optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3,
694or similar compiler books (this technique is more often used for lexical
695analyzers).
696
697The DFA's are used by the parser as parsing tables in a special way
698that's probably unique. Before they are usable, the FIRST sets of all
699non-terminals are computed.
700
701Reference
702---------
703
704[Aho&Ullman 77]
705 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
706 (first edition)
707
708*/