blob: 6b2cdeca2ccdb00d25bc38e63f30e2132a11f81e [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 {
Antoine Pitrouc83ea132010-05-09 14:46:46 +000020 int ar_label;
21 int ar_arrow;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000022} nfaarc;
23
24typedef struct _nfastate {
Antoine Pitrouc83ea132010-05-09 14:46:46 +000025 int st_narcs;
26 nfaarc *st_arc;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000027} nfastate;
28
29typedef struct _nfa {
Antoine Pitrouc83ea132010-05-09 14:46:46 +000030 int nf_type;
31 char *nf_name;
32 int nf_nstates;
33 nfastate *nf_state;
34 int nf_start, nf_finish;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000035} 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,
Antoine Pitrouc83ea132010-05-09 14:46:46 +000039 nfa *nf, node *n, int *pa, int *pb);
Tim Petersdbd9ba62000-07-09 03:09:57 +000040static void compile_alt(labellist *ll,
Antoine Pitrouc83ea132010-05-09 14:46:46 +000041 nfa *nf, node *n, int *pa, int *pb);
Tim Petersdbd9ba62000-07-09 03:09:57 +000042static void compile_item(labellist *ll,
Antoine Pitrouc83ea132010-05-09 14:46:46 +000043 nfa *nf, node *n, int *pa, int *pb);
Tim Petersdbd9ba62000-07-09 03:09:57 +000044static void compile_atom(labellist *ll,
Antoine Pitrouc83ea132010-05-09 14:46:46 +000045 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{
Antoine Pitrouc83ea132010-05-09 14:46:46 +000050 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;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000060}
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{
Antoine Pitrouc83ea132010-05-09 14:46:46 +000065 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;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000076}
77
78static nfa *
Thomas Wouters23c9e002000-07-22 19:20:54 +000079newnfa(char *name)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000080{
Antoine Pitrouc83ea132010-05-09 14:46:46 +000081 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;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000093}
94
95typedef struct _nfagrammar {
Antoine Pitrouc83ea132010-05-09 14:46:46 +000096 int gr_nnfas;
97 nfa **gr_nfa;
98 labellist gr_ll;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000099} 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{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000107 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;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000118}
119
Benjamin Peterson482fac72018-06-22 21:04:21 -0700120static void
121freenfagrammar(nfagrammar *gr)
122{
Benjamin Peterson9ee9efa2018-06-22 21:51:44 -0700123 int i;
124 for (i = 0; i < gr->gr_nnfas; i++) {
Benjamin Peterson482fac72018-06-22 21:04:21 -0700125 PyObject_FREE(gr->gr_nfa[i]->nf_state);
126 }
127 PyObject_FREE(gr->gr_nfa);
128 PyObject_FREE(gr);
129}
130
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000131static nfa *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000132addnfa(nfagrammar *gr, char *name)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000133{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000134 nfa *nf;
135
136 nf = newnfa(name);
137 gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
138 sizeof(nfa*) * (gr->gr_nnfas + 1));
139 if (gr->gr_nfa == NULL)
140 Py_FatalError("out of mem");
141 gr->gr_nfa[gr->gr_nnfas++] = nf;
142 addlabel(&gr->gr_ll, NAME, nf->nf_name);
143 return nf;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000144}
145
Guido van Rossum408027e1996-12-30 16:17:54 +0000146#ifdef Py_DEBUG
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000147
148static char REQNFMT[] = "metacompile: less than %d children\n";
149
Serhiy Storchaka6a35bf62016-10-08 09:58:08 +0300150#define REQN(i, count) do { \
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000151 if (i < count) { \
152 fprintf(stderr, REQNFMT, count); \
153 Py_FatalError("REQN"); \
Serhiy Storchaka6a35bf62016-10-08 09:58:08 +0300154 } \
155} while (0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000156
157#else
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000158#define REQN(i, count) /* empty */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000159#endif
160
161static nfagrammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000162metacompile(node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000163{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000164 nfagrammar *gr;
165 int i;
Guido van Rossum25dfe2c2001-09-11 16:43:16 +0000166
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000167 if (Py_DebugFlag)
168 printf("Compiling (meta-) parse tree into NFA grammar\n");
169 gr = newnfagrammar();
170 REQ(n, MSTART);
171 i = n->n_nchildren - 1; /* Last child is ENDMARKER */
172 n = n->n_child;
173 for (; --i >= 0; n++) {
174 if (n->n_type != NEWLINE)
175 compile_rule(gr, n);
176 }
177 return gr;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000178}
179
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000180static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000181compile_rule(nfagrammar *gr, node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000182{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000183 nfa *nf;
184
185 REQ(n, RULE);
186 REQN(n->n_nchildren, 4);
187 n = n->n_child;
188 REQ(n, NAME);
189 nf = addnfa(gr, n->n_str);
190 n++;
191 REQ(n, COLON);
192 n++;
193 REQ(n, RHS);
194 compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
195 n++;
196 REQ(n, NEWLINE);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000197}
198
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000199static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000200compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000201{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000202 int i;
203 int a, b;
204
205 REQ(n, RHS);
206 i = n->n_nchildren;
207 REQN(i, 1);
208 n = n->n_child;
209 REQ(n, ALT);
210 compile_alt(ll, nf, n, pa, pb);
211 if (--i <= 0)
212 return;
213 n++;
214 a = *pa;
215 b = *pb;
216 *pa = addnfastate(nf);
217 *pb = addnfastate(nf);
218 addnfaarc(nf, *pa, a, EMPTY);
219 addnfaarc(nf, b, *pb, EMPTY);
220 for (; --i >= 0; n++) {
221 REQ(n, VBAR);
222 REQN(i, 1);
223 --i;
224 n++;
225 REQ(n, ALT);
226 compile_alt(ll, nf, n, &a, &b);
227 addnfaarc(nf, *pa, a, EMPTY);
228 addnfaarc(nf, b, *pb, EMPTY);
229 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000230}
231
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000232static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000233compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000234{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000235 int i;
236 int a, b;
237
238 REQ(n, ALT);
239 i = n->n_nchildren;
240 REQN(i, 1);
241 n = n->n_child;
242 REQ(n, ITEM);
243 compile_item(ll, nf, n, pa, pb);
244 --i;
245 n++;
246 for (; --i >= 0; n++) {
247 REQ(n, ITEM);
248 compile_item(ll, nf, n, &a, &b);
249 addnfaarc(nf, *pb, a, EMPTY);
250 *pb = b;
251 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000252}
253
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000254static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000255compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000256{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000257 int i;
258 int a, b;
259
260 REQ(n, ITEM);
261 i = n->n_nchildren;
262 REQN(i, 1);
263 n = n->n_child;
264 if (n->n_type == LSQB) {
265 REQN(i, 3);
266 n++;
267 REQ(n, RHS);
268 *pa = addnfastate(nf);
269 *pb = addnfastate(nf);
270 addnfaarc(nf, *pa, *pb, EMPTY);
271 compile_rhs(ll, nf, n, &a, &b);
272 addnfaarc(nf, *pa, a, EMPTY);
273 addnfaarc(nf, b, *pb, EMPTY);
274 REQN(i, 1);
275 n++;
276 REQ(n, RSQB);
277 }
278 else {
279 compile_atom(ll, nf, n, pa, pb);
280 if (--i <= 0)
281 return;
282 n++;
283 addnfaarc(nf, *pb, *pa, EMPTY);
284 if (n->n_type == STAR)
285 *pb = *pa;
286 else
287 REQ(n, PLUS);
288 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000289}
290
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000291static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000292compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000293{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000294 int i;
295
296 REQ(n, ATOM);
297 i = n->n_nchildren;
Martin Panter646b5282016-06-21 23:58:05 +0000298 (void)i; /* Don't warn about set but unused */
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000299 REQN(i, 1);
300 n = n->n_child;
301 if (n->n_type == LPAR) {
302 REQN(i, 3);
303 n++;
304 REQ(n, RHS);
305 compile_rhs(ll, nf, n, pa, pb);
306 n++;
307 REQ(n, RPAR);
308 }
309 else if (n->n_type == NAME || n->n_type == STRING) {
310 *pa = addnfastate(nf);
311 *pb = addnfastate(nf);
312 addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
313 }
314 else
315 REQ(n, NAME);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000316}
317
318static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000319dumpstate(labellist *ll, nfa *nf, int istate)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000320{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000321 nfastate *st;
322 int i;
323 nfaarc *ar;
324
325 printf("%c%2d%c",
326 istate == nf->nf_start ? '*' : ' ',
327 istate,
328 istate == nf->nf_finish ? '.' : ' ');
329 st = &nf->nf_state[istate];
330 ar = st->st_arc;
331 for (i = 0; i < st->st_narcs; i++) {
332 if (i > 0)
333 printf("\n ");
334 printf("-> %2d %s", ar->ar_arrow,
335 PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
336 ar++;
337 }
338 printf("\n");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000339}
340
341static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000342dumpnfa(labellist *ll, nfa *nf)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000343{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000344 int i;
345
346 printf("NFA '%s' has %d states; start %d, finish %d\n",
347 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
348 for (i = 0; i < nf->nf_nstates; i++)
349 dumpstate(ll, nf, i);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000350}
351
352
353/* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */
354
Guido van Rossum588633d1994-12-30 15:46:02 +0000355static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000356addclosure(bitset ss, nfa *nf, int istate)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000357{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000358 if (addbit(ss, istate)) {
359 nfastate *st = &nf->nf_state[istate];
360 nfaarc *ar = st->st_arc;
361 int i;
362
363 for (i = st->st_narcs; --i >= 0; ) {
364 if (ar->ar_label == EMPTY)
365 addclosure(ss, nf, ar->ar_arrow);
366 ar++;
367 }
368 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000369}
370
371typedef struct _ss_arc {
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000372 bitset sa_bitset;
373 int sa_arrow;
374 int sa_label;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000375} ss_arc;
376
377typedef struct _ss_state {
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000378 bitset ss_ss;
379 int ss_narcs;
380 struct _ss_arc *ss_arc;
381 int ss_deleted;
382 int ss_finish;
383 int ss_rename;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000384} ss_state;
385
386typedef struct _ss_dfa {
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000387 int sd_nstates;
388 ss_state *sd_state;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000389} ss_dfa;
390
Guido van Rossum71f477c1991-04-03 19:09:02 +0000391/* Forward */
Tim Petersdbd9ba62000-07-09 03:09:57 +0000392static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000393 labellist *ll, char *msg);
Tim Petersdbd9ba62000-07-09 03:09:57 +0000394static void simplify(int xx_nstates, ss_state *xx_state);
395static void convert(dfa *d, int xx_nstates, ss_state *xx_state);
Guido van Rossum71f477c1991-04-03 19:09:02 +0000396
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000397static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000398makedfa(nfagrammar *gr, nfa *nf, dfa *d)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000399{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000400 int nbits = nf->nf_nstates;
401 bitset ss;
402 int xx_nstates;
403 ss_state *xx_state, *yy;
404 ss_arc *zz;
405 int istate, jstate, iarc, jarc, ibit;
406 nfastate *st;
407 nfaarc *ar;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000408
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000409 ss = newbitset(nbits);
410 addclosure(ss, nf, nf->nf_start);
411 xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
412 if (xx_state == NULL)
413 Py_FatalError("no mem for xx_state in makedfa");
414 xx_nstates = 1;
415 yy = &xx_state[0];
416 yy->ss_ss = ss;
417 yy->ss_narcs = 0;
418 yy->ss_arc = NULL;
419 yy->ss_deleted = 0;
420 yy->ss_finish = testbit(ss, nf->nf_finish);
421 if (yy->ss_finish)
422 printf("Error: nonterminal '%s' may produce empty.\n",
423 nf->nf_name);
424
425 /* This algorithm is from a book written before
426 the invention of structured programming... */
427
428 /* For each unmarked state... */
429 for (istate = 0; istate < xx_nstates; ++istate) {
430 size_t size;
431 yy = &xx_state[istate];
432 ss = yy->ss_ss;
433 /* For all its states... */
434 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
435 if (!testbit(ss, ibit))
436 continue;
437 st = &nf->nf_state[ibit];
438 /* For all non-empty arcs from this state... */
439 for (iarc = 0; iarc < st->st_narcs; iarc++) {
440 ar = &st->st_arc[iarc];
441 if (ar->ar_label == EMPTY)
442 continue;
443 /* Look up in list of arcs from this state */
444 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
445 zz = &yy->ss_arc[jarc];
446 if (ar->ar_label == zz->sa_label)
447 goto found;
448 }
449 /* Add new arc for this state */
450 size = sizeof(ss_arc) * (yy->ss_narcs + 1);
451 yy->ss_arc = (ss_arc *)PyObject_REALLOC(
452 yy->ss_arc, size);
453 if (yy->ss_arc == NULL)
454 Py_FatalError("out of mem");
455 zz = &yy->ss_arc[yy->ss_narcs++];
456 zz->sa_label = ar->ar_label;
457 zz->sa_bitset = newbitset(nbits);
458 zz->sa_arrow = -1;
459 found: ;
460 /* Add destination */
461 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
462 }
463 }
464 /* Now look up all the arrow states */
465 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
466 zz = &xx_state[istate].ss_arc[jarc];
467 for (jstate = 0; jstate < xx_nstates; jstate++) {
468 if (samebitset(zz->sa_bitset,
469 xx_state[jstate].ss_ss, nbits)) {
470 zz->sa_arrow = jstate;
471 goto done;
472 }
473 }
474 size = sizeof(ss_state) * (xx_nstates + 1);
475 xx_state = (ss_state *)PyObject_REALLOC(xx_state,
476 size);
477 if (xx_state == NULL)
478 Py_FatalError("out of mem");
479 zz->sa_arrow = xx_nstates;
480 yy = &xx_state[xx_nstates++];
481 yy->ss_ss = zz->sa_bitset;
482 yy->ss_narcs = 0;
483 yy->ss_arc = NULL;
484 yy->ss_deleted = 0;
485 yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
486 done: ;
487 }
488 }
489
490 if (Py_DebugFlag)
491 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
492 "before minimizing");
493
494 simplify(xx_nstates, xx_state);
495
496 if (Py_DebugFlag)
497 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
498 "after minimizing");
499
500 convert(d, xx_nstates, xx_state);
501
Benjamin Peterson482fac72018-06-22 21:04:21 -0700502 for (int i = 0; i < xx_nstates; i++) {
503 for (int j = 0; j < xx_state[i].ss_narcs; j++)
504 delbitset(xx_state[i].ss_arc[j].sa_bitset);
505 PyObject_FREE(xx_state[i].ss_arc);
506 }
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000507 PyObject_FREE(xx_state);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000508}
509
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000510static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000511printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000512 labellist *ll, char *msg)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000513{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000514 int i, ibit, iarc;
515 ss_state *yy;
516 ss_arc *zz;
517
518 printf("Subset DFA %s\n", msg);
519 for (i = 0; i < xx_nstates; i++) {
520 yy = &xx_state[i];
521 if (yy->ss_deleted)
522 continue;
523 printf(" Subset %d", i);
524 if (yy->ss_finish)
525 printf(" (finish)");
526 printf(" { ");
527 for (ibit = 0; ibit < nbits; ibit++) {
528 if (testbit(yy->ss_ss, ibit))
529 printf("%d ", ibit);
530 }
531 printf("}\n");
532 for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
533 zz = &yy->ss_arc[iarc];
534 printf(" Arc to state %d, label %s\n",
535 zz->sa_arrow,
536 PyGrammar_LabelRepr(
537 &ll->ll_label[zz->sa_label]));
538 }
539 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000540}
541
542
543/* PART THREE -- SIMPLIFY DFA */
544
545/* Simplify the DFA by repeatedly eliminating states that are
546 equivalent to another oner. This is NOT Algorithm 3.3 from
547 [Aho&Ullman 77]. It does not always finds the minimal DFA,
548 but it does usually make a much smaller one... (For an example
Thomas Wouters7e474022000-07-16 12:04:32 +0000549 of sub-optimal behavior, try S: x a b+ | y a b+.)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000550*/
551
552static int
Thomas Wouters23c9e002000-07-22 19:20:54 +0000553samestate(ss_state *s1, ss_state *s2)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000554{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000555 int i;
556
557 if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
558 return 0;
559 for (i = 0; i < s1->ss_narcs; i++) {
560 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
561 s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
562 return 0;
563 }
564 return 1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000565}
566
567static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000568renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000569{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000570 int i, j;
571
572 if (Py_DebugFlag)
573 printf("Rename state %d to %d.\n", from, to);
574 for (i = 0; i < xx_nstates; i++) {
575 if (xx_state[i].ss_deleted)
576 continue;
577 for (j = 0; j < xx_state[i].ss_narcs; j++) {
578 if (xx_state[i].ss_arc[j].sa_arrow == from)
579 xx_state[i].ss_arc[j].sa_arrow = to;
580 }
581 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000582}
583
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000584static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000585simplify(int xx_nstates, ss_state *xx_state)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000586{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000587 int changes;
588 int i, j;
589
590 do {
591 changes = 0;
592 for (i = 1; i < xx_nstates; i++) {
593 if (xx_state[i].ss_deleted)
594 continue;
595 for (j = 0; j < i; j++) {
596 if (xx_state[j].ss_deleted)
597 continue;
598 if (samestate(&xx_state[i], &xx_state[j])) {
599 xx_state[i].ss_deleted++;
600 renamestates(xx_nstates, xx_state,
601 i, j);
602 changes++;
603 break;
604 }
605 }
606 }
607 } while (changes);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000608}
609
610
611/* PART FOUR -- GENERATE PARSING TABLES */
612
613/* Convert the DFA into a grammar that can be used by our parser */
614
Guido van Rossumfd8a3931996-12-02 18:27:33 +0000615static void
Thomas Wouters23c9e002000-07-22 19:20:54 +0000616convert(dfa *d, int xx_nstates, ss_state *xx_state)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000617{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000618 int i, j;
619 ss_state *yy;
620 ss_arc *zz;
621
622 for (i = 0; i < xx_nstates; i++) {
623 yy = &xx_state[i];
624 if (yy->ss_deleted)
625 continue;
626 yy->ss_rename = addstate(d);
627 }
628
629 for (i = 0; i < xx_nstates; i++) {
630 yy = &xx_state[i];
631 if (yy->ss_deleted)
632 continue;
633 for (j = 0; j < yy->ss_narcs; j++) {
634 zz = &yy->ss_arc[j];
635 addarc(d, yy->ss_rename,
636 xx_state[zz->sa_arrow].ss_rename,
637 zz->sa_label);
638 }
639 if (yy->ss_finish)
640 addarc(d, yy->ss_rename, yy->ss_rename, 0);
641 }
642
643 d->d_initial = 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000644}
645
646
647/* PART FIVE -- GLUE IT ALL TOGETHER */
648
649static grammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000650maketables(nfagrammar *gr)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000651{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000652 int i;
653 nfa *nf;
654 dfa *d;
655 grammar *g;
656
657 if (gr->gr_nnfas == 0)
658 return NULL;
659 g = newgrammar(gr->gr_nfa[0]->nf_type);
660 /* XXX first rule must be start rule */
661 g->g_ll = gr->gr_ll;
662
663 for (i = 0; i < gr->gr_nnfas; i++) {
664 nf = gr->gr_nfa[i];
665 if (Py_DebugFlag) {
666 printf("Dump of NFA for '%s' ...\n", nf->nf_name);
667 dumpnfa(&gr->gr_ll, nf);
668 printf("Making DFA for '%s' ...\n", nf->nf_name);
669 }
670 d = adddfa(g, nf->nf_type, nf->nf_name);
671 makedfa(gr, gr->gr_nfa[i], d);
672 }
673
674 return g;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000675}
676
677grammar *
Thomas Wouters23c9e002000-07-22 19:20:54 +0000678pgen(node *n)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000679{
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000680 nfagrammar *gr;
681 grammar *g;
682
683 gr = metacompile(n);
684 g = maketables(gr);
685 translatelabels(g);
686 addfirstsets(g);
Benjamin Peterson482fac72018-06-22 21:04:21 -0700687 freenfagrammar(gr);
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000688 return g;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000689}
690
Guido van Rossumd3ab37f2003-04-17 14:55:42 +0000691grammar *
692Py_pgen(node *n)
693{
694 return pgen(n);
695}
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000696
697/*
698
699Description
700-----------
701
702Input is a grammar in extended BNF (using * for repetition, + for
703at-least-once repetition, [] for optional parts, | for alternatives and
704() for grouping). This has already been parsed and turned into a parse
705tree.
706
707Each rule is considered as a regular expression in its own right.
708It is turned into a Non-deterministic Finite Automaton (NFA), which
709is then turned into a Deterministic Finite Automaton (DFA), which is then
710optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3,
711or similar compiler books (this technique is more often used for lexical
712analyzers).
713
714The DFA's are used by the parser as parsing tables in a special way
715that's probably unique. Before they are usable, the FIRST sets of all
716non-terminals are computed.
717
718Reference
719---------
720
721[Aho&Ullman 77]
Antoine Pitrouc83ea132010-05-09 14:46:46 +0000722 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
723 (first edition)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000724
725*/