1 /* Parser generator */
2
3 /* For a description, see the comments at end of this file */
4
5 #include "Python.h"
6 #include "pgenheaders.h"
7 #include "token.h"
8 #include "node.h"
9 #include "grammar.h"
10 #include "metagrammar.h"
11 #include "pgen.h"
12
13 extern int Py_DebugFlag;
14 extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */
15
16
17 /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */
18
19 typedef struct _nfaarc {
20 int ar_label;
21 int ar_arrow;
22 } nfaarc;
23
24 typedef struct _nfastate {
25 int st_narcs;
26 nfaarc *st_arc;
27 } nfastate;
28
29 typedef 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
37 /* Forward */
38 static void compile_rhs(labellist *ll,
39 nfa *nf, node *n, int *pa, int *pb);
40 static void compile_alt(labellist *ll,
41 nfa *nf, node *n, int *pa, int *pb);
42 static void compile_item(labellist *ll,
43 nfa *nf, node *n, int *pa, int *pb);
44 static void compile_atom(labellist *ll,
45 nfa *nf, node *n, int *pa, int *pb);
46
47 static int
addnfastate(nfa * nf)48 addnfastate(nfa *nf)
49 {
50 nfastate *st;
51
52 nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,
53 sizeof(nfastate) * (nf->nf_nstates + 1));
54 if (nf->nf_state == NULL)
55 Py_FatalError("out of mem");
56 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
62 static void
addnfaarc(nfa * nf,int from,int to,int lbl)63 addnfaarc(nfa *nf, int from, int to, int lbl)
64 {
65 nfastate *st;
66 nfaarc *ar;
67
68 st = &nf->nf_state[from];
69 st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,
70 sizeof(nfaarc) * (st->st_narcs + 1));
71 if (st->st_arc == NULL)
72 Py_FatalError("out of mem");
73 ar = &st->st_arc[st->st_narcs++];
74 ar->ar_label = lbl;
75 ar->ar_arrow = to;
76 }
77
78 static nfa *
newnfa(char * name)79 newnfa(char *name)
80 {
81 nfa *nf;
82 static int type = NT_OFFSET; /* All types will be disjunct */
83
84 nf = (nfa *)PyObject_MALLOC(sizeof(nfa));
85 if (nf == NULL)
86 Py_FatalError("no mem for new nfa");
87 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
95 typedef struct _nfagrammar {
96 int gr_nnfas;
97 nfa **gr_nfa;
98 labellist gr_ll;
99 } nfagrammar;
100
101 /* Forward */
102 static void compile_rule(nfagrammar *gr, node *n);
103
104 static nfagrammar *
newnfagrammar(void)105 newnfagrammar(void)
106 {
107 nfagrammar *gr;
108
109 gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));
110 if (gr == NULL)
111 Py_FatalError("no mem for new nfa grammar");
112 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
120 static nfa *
addnfa(nfagrammar * gr,char * name)121 addnfa(nfagrammar *gr, char *name)
122 {
123 nfa *nf;
124
125 nf = newnfa(name);
126 gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
127 sizeof(nfa*) * (gr->gr_nnfas + 1));
128 if (gr->gr_nfa == NULL)
129 Py_FatalError("out of mem");
130 gr->gr_nfa[gr->gr_nnfas++] = nf;
131 addlabel(&gr->gr_ll, NAME, nf->nf_name);
132 return nf;
133 }
134
135 #ifdef Py_DEBUG
136
137 static char REQNFMT[] = "metacompile: less than %d children\n";
138
139 #define REQN(i, count) do { \
140 if (i < count) { \
141 fprintf(stderr, REQNFMT, count); \
142 Py_FatalError("REQN"); \
143 } \
144 } while (0)
145
146 #else
147 #define REQN(i, count) /* empty */
148 #endif
149
150 static nfagrammar *
metacompile(node * n)151 metacompile(node *n)
152 {
153 nfagrammar *gr;
154 int i;
155
156 if (Py_DebugFlag)
157 printf("Compiling (meta-) parse tree into NFA grammar\n");
158 gr = newnfagrammar();
159 REQ(n, MSTART);
160 i = n->n_nchildren - 1; /* Last child is ENDMARKER */
161 n = n->n_child;
162 for (; --i >= 0; n++) {
163 if (n->n_type != NEWLINE)
164 compile_rule(gr, n);
165 }
166 return gr;
167 }
168
169 static void
compile_rule(nfagrammar * gr,node * n)170 compile_rule(nfagrammar *gr, node *n)
171 {
172 nfa *nf;
173
174 REQ(n, RULE);
175 REQN(n->n_nchildren, 4);
176 n = n->n_child;
177 REQ(n, NAME);
178 nf = addnfa(gr, n->n_str);
179 n++;
180 REQ(n, COLON);
181 n++;
182 REQ(n, RHS);
183 compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
184 n++;
185 REQ(n, NEWLINE);
186 }
187
188 static void
compile_rhs(labellist * ll,nfa * nf,node * n,int * pa,int * pb)189 compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
190 {
191 int i;
192 int a, b;
193
194 REQ(n, RHS);
195 i = n->n_nchildren;
196 REQN(i, 1);
197 n = n->n_child;
198 REQ(n, ALT);
199 compile_alt(ll, nf, n, pa, pb);
200 if (--i <= 0)
201 return;
202 n++;
203 a = *pa;
204 b = *pb;
205 *pa = addnfastate(nf);
206 *pb = addnfastate(nf);
207 addnfaarc(nf, *pa, a, EMPTY);
208 addnfaarc(nf, b, *pb, EMPTY);
209 for (; --i >= 0; n++) {
210 REQ(n, VBAR);
211 REQN(i, 1);
212 --i;
213 n++;
214 REQ(n, ALT);
215 compile_alt(ll, nf, n, &a, &b);
216 addnfaarc(nf, *pa, a, EMPTY);
217 addnfaarc(nf, b, *pb, EMPTY);
218 }
219 }
220
221 static void
compile_alt(labellist * ll,nfa * nf,node * n,int * pa,int * pb)222 compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
223 {
224 int i;
225 int a, b;
226
227 REQ(n, ALT);
228 i = n->n_nchildren;
229 REQN(i, 1);
230 n = n->n_child;
231 REQ(n, ITEM);
232 compile_item(ll, nf, n, pa, pb);
233 --i;
234 n++;
235 for (; --i >= 0; n++) {
236 REQ(n, ITEM);
237 compile_item(ll, nf, n, &a, &b);
238 addnfaarc(nf, *pb, a, EMPTY);
239 *pb = b;
240 }
241 }
242
243 static void
compile_item(labellist * ll,nfa * nf,node * n,int * pa,int * pb)244 compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
245 {
246 int i;
247 int a, b;
248
249 REQ(n, ITEM);
250 i = n->n_nchildren;
251 REQN(i, 1);
252 n = n->n_child;
253 if (n->n_type == LSQB) {
254 REQN(i, 3);
255 n++;
256 REQ(n, RHS);
257 *pa = addnfastate(nf);
258 *pb = addnfastate(nf);
259 addnfaarc(nf, *pa, *pb, EMPTY);
260 compile_rhs(ll, nf, n, &a, &b);
261 addnfaarc(nf, *pa, a, EMPTY);
262 addnfaarc(nf, b, *pb, EMPTY);
263 REQN(i, 1);
264 n++;
265 REQ(n, RSQB);
266 }
267 else {
268 compile_atom(ll, nf, n, pa, pb);
269 if (--i <= 0)
270 return;
271 n++;
272 addnfaarc(nf, *pb, *pa, EMPTY);
273 if (n->n_type == STAR)
274 *pb = *pa;
275 else
276 REQ(n, PLUS);
277 }
278 }
279
280 static void
compile_atom(labellist * ll,nfa * nf,node * n,int * pa,int * pb)281 compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
282 {
283 int i;
284
285 REQ(n, ATOM);
286 i = n->n_nchildren;
287 (void)i; /* Don't warn about set but unused */
288 REQN(i, 1);
289 n = n->n_child;
290 if (n->n_type == LPAR) {
291 REQN(i, 3);
292 n++;
293 REQ(n, RHS);
294 compile_rhs(ll, nf, n, pa, pb);
295 n++;
296 REQ(n, RPAR);
297 }
298 else if (n->n_type == NAME || n->n_type == STRING) {
299 *pa = addnfastate(nf);
300 *pb = addnfastate(nf);
301 addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
302 }
303 else
304 REQ(n, NAME);
305 }
306
307 static void
dumpstate(labellist * ll,nfa * nf,int istate)308 dumpstate(labellist *ll, nfa *nf, int istate)
309 {
310 nfastate *st;
311 int i;
312 nfaarc *ar;
313
314 printf("%c%2d%c",
315 istate == nf->nf_start ? '*' : ' ',
316 istate,
317 istate == nf->nf_finish ? '.' : ' ');
318 st = &nf->nf_state[istate];
319 ar = st->st_arc;
320 for (i = 0; i < st->st_narcs; i++) {
321 if (i > 0)
322 printf("\n ");
323 printf("-> %2d %s", ar->ar_arrow,
324 PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
325 ar++;
326 }
327 printf("\n");
328 }
329
330 static void
dumpnfa(labellist * ll,nfa * nf)331 dumpnfa(labellist *ll, nfa *nf)
332 {
333 int i;
334
335 printf("NFA '%s' has %d states; start %d, finish %d\n",
336 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
337 for (i = 0; i < nf->nf_nstates; i++)
338 dumpstate(ll, nf, i);
339 }
340
341
342 /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */
343
344 static void
addclosure(bitset ss,nfa * nf,int istate)345 addclosure(bitset ss, nfa *nf, int istate)
346 {
347 if (addbit(ss, istate)) {
348 nfastate *st = &nf->nf_state[istate];
349 nfaarc *ar = st->st_arc;
350 int i;
351
352 for (i = st->st_narcs; --i >= 0; ) {
353 if (ar->ar_label == EMPTY)
354 addclosure(ss, nf, ar->ar_arrow);
355 ar++;
356 }
357 }
358 }
359
360 typedef struct _ss_arc {
361 bitset sa_bitset;
362 int sa_arrow;
363 int sa_label;
364 } ss_arc;
365
366 typedef struct _ss_state {
367 bitset ss_ss;
368 int ss_narcs;
369 struct _ss_arc *ss_arc;
370 int ss_deleted;
371 int ss_finish;
372 int ss_rename;
373 } ss_state;
374
375 typedef struct _ss_dfa {
376 int sd_nstates;
377 ss_state *sd_state;
378 } ss_dfa;
379
380 /* Forward */
381 static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
382 labellist *ll, char *msg);
383 static void simplify(int xx_nstates, ss_state *xx_state);
384 static void convert(dfa *d, int xx_nstates, ss_state *xx_state);
385
386 static void
makedfa(nfagrammar * gr,nfa * nf,dfa * d)387 makedfa(nfagrammar *gr, nfa *nf, dfa *d)
388 {
389 int nbits = nf->nf_nstates;
390 bitset ss;
391 int xx_nstates;
392 ss_state *xx_state, *yy;
393 ss_arc *zz;
394 int istate, jstate, iarc, jarc, ibit;
395 nfastate *st;
396 nfaarc *ar;
397
398 ss = newbitset(nbits);
399 addclosure(ss, nf, nf->nf_start);
400 xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
401 if (xx_state == NULL)
402 Py_FatalError("no mem for xx_state in makedfa");
403 xx_nstates = 1;
404 yy = &xx_state[0];
405 yy->ss_ss = ss;
406 yy->ss_narcs = 0;
407 yy->ss_arc = NULL;
408 yy->ss_deleted = 0;
409 yy->ss_finish = testbit(ss, nf->nf_finish);
410 if (yy->ss_finish)
411 printf("Error: nonterminal '%s' may produce empty.\n",
412 nf->nf_name);
413
414 /* This algorithm is from a book written before
415 the invention of structured programming... */
416
417 /* For each unmarked state... */
418 for (istate = 0; istate < xx_nstates; ++istate) {
419 size_t size;
420 yy = &xx_state[istate];
421 ss = yy->ss_ss;
422 /* For all its states... */
423 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
424 if (!testbit(ss, ibit))
425 continue;
426 st = &nf->nf_state[ibit];
427 /* For all non-empty arcs from this state... */
428 for (iarc = 0; iarc < st->st_narcs; iarc++) {
429 ar = &st->st_arc[iarc];
430 if (ar->ar_label == EMPTY)
431 continue;
432 /* Look up in list of arcs from this state */
433 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
434 zz = &yy->ss_arc[jarc];
435 if (ar->ar_label == zz->sa_label)
436 goto found;
437 }
438 /* Add new arc for this state */
439 size = sizeof(ss_arc) * (yy->ss_narcs + 1);
440 yy->ss_arc = (ss_arc *)PyObject_REALLOC(
441 yy->ss_arc, size);
442 if (yy->ss_arc == NULL)
443 Py_FatalError("out of mem");
444 zz = &yy->ss_arc[yy->ss_narcs++];
445 zz->sa_label = ar->ar_label;
446 zz->sa_bitset = newbitset(nbits);
447 zz->sa_arrow = -1;
448 found: ;
449 /* Add destination */
450 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
451 }
452 }
453 /* Now look up all the arrow states */
454 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
455 zz = &xx_state[istate].ss_arc[jarc];
456 for (jstate = 0; jstate < xx_nstates; jstate++) {
457 if (samebitset(zz->sa_bitset,
458 xx_state[jstate].ss_ss, nbits)) {
459 zz->sa_arrow = jstate;
460 goto done;
461 }
462 }
463 size = sizeof(ss_state) * (xx_nstates + 1);
464 xx_state = (ss_state *)PyObject_REALLOC(xx_state,
465 size);
466 if (xx_state == NULL)
467 Py_FatalError("out of mem");
468 zz->sa_arrow = xx_nstates;
469 yy = &xx_state[xx_nstates++];
470 yy->ss_ss = zz->sa_bitset;
471 yy->ss_narcs = 0;
472 yy->ss_arc = NULL;
473 yy->ss_deleted = 0;
474 yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
475 done: ;
476 }
477 }
478
479 if (Py_DebugFlag)
480 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
481 "before minimizing");
482
483 simplify(xx_nstates, xx_state);
484
485 if (Py_DebugFlag)
486 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
487 "after minimizing");
488
489 convert(d, xx_nstates, xx_state);
490
491 /* XXX cleanup */
492 PyObject_FREE(xx_state);
493 }
494
495 static void
printssdfa(int xx_nstates,ss_state * xx_state,int nbits,labellist * ll,char * msg)496 printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
497 labellist *ll, char *msg)
498 {
499 int i, ibit, iarc;
500 ss_state *yy;
501 ss_arc *zz;
502
503 printf("Subset DFA %s\n", msg);
504 for (i = 0; i < xx_nstates; i++) {
505 yy = &xx_state[i];
506 if (yy->ss_deleted)
507 continue;
508 printf(" Subset %d", i);
509 if (yy->ss_finish)
510 printf(" (finish)");
511 printf(" { ");
512 for (ibit = 0; ibit < nbits; ibit++) {
513 if (testbit(yy->ss_ss, ibit))
514 printf("%d ", ibit);
515 }
516 printf("}\n");
517 for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
518 zz = &yy->ss_arc[iarc];
519 printf(" Arc to state %d, label %s\n",
520 zz->sa_arrow,
521 PyGrammar_LabelRepr(
522 &ll->ll_label[zz->sa_label]));
523 }
524 }
525 }
526
527
528 /* PART THREE -- SIMPLIFY DFA */
529
530 /* Simplify the DFA by repeatedly eliminating states that are
531 equivalent to another oner. This is NOT Algorithm 3.3 from
532 [Aho&Ullman 77]. It does not always finds the minimal DFA,
533 but it does usually make a much smaller one... (For an example
534 of sub-optimal behavior, try S: x a b+ | y a b+.)
535 */
536
537 static int
samestate(ss_state * s1,ss_state * s2)538 samestate(ss_state *s1, ss_state *s2)
539 {
540 int i;
541
542 if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
543 return 0;
544 for (i = 0; i < s1->ss_narcs; i++) {
545 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
546 s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
547 return 0;
548 }
549 return 1;
550 }
551
552 static void
renamestates(int xx_nstates,ss_state * xx_state,int from,int to)553 renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
554 {
555 int i, j;
556
557 if (Py_DebugFlag)
558 printf("Rename state %d to %d.\n", from, to);
559 for (i = 0; i < xx_nstates; i++) {
560 if (xx_state[i].ss_deleted)
561 continue;
562 for (j = 0; j < xx_state[i].ss_narcs; j++) {
563 if (xx_state[i].ss_arc[j].sa_arrow == from)
564 xx_state[i].ss_arc[j].sa_arrow = to;
565 }
566 }
567 }
568
569 static void
simplify(int xx_nstates,ss_state * xx_state)570 simplify(int xx_nstates, ss_state *xx_state)
571 {
572 int changes;
573 int i, j;
574
575 do {
576 changes = 0;
577 for (i = 1; i < xx_nstates; i++) {
578 if (xx_state[i].ss_deleted)
579 continue;
580 for (j = 0; j < i; j++) {
581 if (xx_state[j].ss_deleted)
582 continue;
583 if (samestate(&xx_state[i], &xx_state[j])) {
584 xx_state[i].ss_deleted++;
585 renamestates(xx_nstates, xx_state,
586 i, j);
587 changes++;
588 break;
589 }
590 }
591 }
592 } while (changes);
593 }
594
595
596 /* PART FOUR -- GENERATE PARSING TABLES */
597
598 /* Convert the DFA into a grammar that can be used by our parser */
599
600 static void
convert(dfa * d,int xx_nstates,ss_state * xx_state)601 convert(dfa *d, int xx_nstates, ss_state *xx_state)
602 {
603 int i, j;
604 ss_state *yy;
605 ss_arc *zz;
606
607 for (i = 0; i < xx_nstates; i++) {
608 yy = &xx_state[i];
609 if (yy->ss_deleted)
610 continue;
611 yy->ss_rename = addstate(d);
612 }
613
614 for (i = 0; i < xx_nstates; i++) {
615 yy = &xx_state[i];
616 if (yy->ss_deleted)
617 continue;
618 for (j = 0; j < yy->ss_narcs; j++) {
619 zz = &yy->ss_arc[j];
620 addarc(d, yy->ss_rename,
621 xx_state[zz->sa_arrow].ss_rename,
622 zz->sa_label);
623 }
624 if (yy->ss_finish)
625 addarc(d, yy->ss_rename, yy->ss_rename, 0);
626 }
627
628 d->d_initial = 0;
629 }
630
631
632 /* PART FIVE -- GLUE IT ALL TOGETHER */
633
634 static grammar *
maketables(nfagrammar * gr)635 maketables(nfagrammar *gr)
636 {
637 int i;
638 nfa *nf;
639 dfa *d;
640 grammar *g;
641
642 if (gr->gr_nnfas == 0)
643 return NULL;
644 g = newgrammar(gr->gr_nfa[0]->nf_type);
645 /* XXX first rule must be start rule */
646 g->g_ll = gr->gr_ll;
647
648 for (i = 0; i < gr->gr_nnfas; i++) {
649 nf = gr->gr_nfa[i];
650 if (Py_DebugFlag) {
651 printf("Dump of NFA for '%s' ...\n", nf->nf_name);
652 dumpnfa(&gr->gr_ll, nf);
653 printf("Making DFA for '%s' ...\n", nf->nf_name);
654 }
655 d = adddfa(g, nf->nf_type, nf->nf_name);
656 makedfa(gr, gr->gr_nfa[i], d);
657 }
658
659 return g;
660 }
661
662 grammar *
pgen(node * n)663 pgen(node *n)
664 {
665 nfagrammar *gr;
666 grammar *g;
667
668 gr = metacompile(n);
669 g = maketables(gr);
670 translatelabels(g);
671 addfirstsets(g);
672 PyObject_FREE(gr);
673 return g;
674 }
675
676 grammar *
Py_pgen(node * n)677 Py_pgen(node *n)
678 {
679 return pgen(n);
680 }
681
682 /*
683
684 Description
685 -----------
686
687 Input is a grammar in extended BNF (using * for repetition, + for
688 at-least-once repetition, [] for optional parts, | for alternatives and
689 () for grouping). This has already been parsed and turned into a parse
690 tree.
691
692 Each rule is considered as a regular expression in its own right.
693 It is turned into a Non-deterministic Finite Automaton (NFA), which
694 is then turned into a Deterministic Finite Automaton (DFA), which is then
695 optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3,
696 or similar compiler books (this technique is more often used for lexical
697 analyzers).
698
699 The DFA's are used by the parser as parsing tables in a special way
700 that's probably unique. Before they are usable, the FIRST sets of all
701 non-terminals are computed.
702
703 Reference
704 ---------
705
706 [Aho&Ullman 77]
707 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
708 (first edition)
709
710 */
711