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