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