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