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

    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

    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 *

    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 *

   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 *

   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) \

   140  	if (i < count) { \

   141 		fprintf(stderr, REQNFMT, count); \

   142 		Py_FatalError("REQN"); \

   143 	} else

   144 

   145 #else

   146 #define REQN(i, count)	/* empty */

   147 #endif

   148 

   149 static nfagrammar *

   150 metacompile(node *n)

   151 {

   152 	nfagrammar *gr;

   153 	int i;

   154 

   155 	if (Py_DebugFlag)

   156 		printf("Compiling (meta-) parse tree into NFA grammar\n");

   157 	gr = newnfagrammar();

   158 	REQ(n, MSTART);

   159 	i = n->n_nchildren - 1; /* Last child is ENDMARKER */

   160 	n = n->n_child;

   161 	for (; --i >= 0; n++) {

   162 		if (n->n_type != NEWLINE)

   163 			compile_rule(gr, n);

   164 	}

   165 	return gr;

   166 }

   167 

   168 static void

   169 compile_rule(nfagrammar *gr, node *n)

   170 {

   171 	nfa *nf;

   172 	

   173 	REQ(n, RULE);

   174 	REQN(n->n_nchildren, 4);

   175 	n = n->n_child;

   176 	REQ(n, NAME);

   177 	nf = addnfa(gr, n->n_str);

   178 	n++;

   179 	REQ(n, COLON);

   180 	n++;

   181 	REQ(n, RHS);

   182 	compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);

   183 	n++;

   184 	REQ(n, NEWLINE);

   185 }

   186 

   187 static void

   188 compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

   189 {

   190 	int i;

   191 	int a, b;

   192 	

   193 	REQ(n, RHS);

   194 	i = n->n_nchildren;

   195 	REQN(i, 1);

   196 	n = n->n_child;

   197 	REQ(n, ALT);

   198 	compile_alt(ll, nf, n, pa, pb);

   199 	if (--i <= 0)

   200 		return;

   201 	n++;

   202 	a = *pa;

   203 	b = *pb;

   204 	*pa = addnfastate(nf);

   205 	*pb = addnfastate(nf);

   206 	addnfaarc(nf, *pa, a, EMPTY);

   207 	addnfaarc(nf, b, *pb, EMPTY);

   208 	for (; --i >= 0; n++) {

   209 		REQ(n, VBAR);

   210 		REQN(i, 1);

   211 		--i;

   212 		n++;

   213 		REQ(n, ALT);

   214 		compile_alt(ll, nf, n, &a, &b);

   215 		addnfaarc(nf, *pa, a, EMPTY);

   216 		addnfaarc(nf, b, *pb, EMPTY);

   217 	}

   218 }

   219 

   220 static void

   221 compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

   222 {

   223 	int i;

   224 	int a, b;

   225 	

   226 	REQ(n, ALT);

   227 	i = n->n_nchildren;

   228 	REQN(i, 1);

   229 	n = n->n_child;

   230 	REQ(n, ITEM);

   231 	compile_item(ll, nf, n, pa, pb);

   232 	--i;

   233 	n++;

   234 	for (; --i >= 0; n++) {

   235 		REQ(n, ITEM);

   236 		compile_item(ll, nf, n, &a, &b);

   237 		addnfaarc(nf, *pb, a, EMPTY);

   238 		*pb = b;

   239 	}

   240 }

   241 

   242 static void

   243 compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

   244 {

   245 	int i;

   246 	int a, b;

   247 	

   248 	REQ(n, ITEM);

   249 	i = n->n_nchildren;

   250 	REQN(i, 1);

   251 	n = n->n_child;

   252 	if (n->n_type == LSQB) {

   253 		REQN(i, 3);

   254 		n++;

   255 		REQ(n, RHS);

   256 		*pa = addnfastate(nf);

   257 		*pb = addnfastate(nf);

   258 		addnfaarc(nf, *pa, *pb, EMPTY);

   259 		compile_rhs(ll, nf, n, &a, &b);

   260 		addnfaarc(nf, *pa, a, EMPTY);

   261 		addnfaarc(nf, b, *pb, EMPTY);

   262 		REQN(i, 1);

   263 		n++;

   264 		REQ(n, RSQB);

   265 	}

   266 	else {

   267 		compile_atom(ll, nf, n, pa, pb);

   268 		if (--i <= 0)

   269 			return;

   270 		n++;

   271 		addnfaarc(nf, *pb, *pa, EMPTY);

   272 		if (n->n_type == STAR)

   273 			*pb = *pa;

   274 		else

   275 			REQ(n, PLUS);

   276 	}

   277 }

   278 

   279 static void

   280 compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)

   281 {

   282 	int i;

   283 	

   284 	REQ(n, ATOM);

   285 	i = n->n_nchildren;

   286 	REQN(i, 1);

   287 	n = n->n_child;

   288 	if (n->n_type == LPAR) {

   289 		REQN(i, 3);

   290 		n++;

   291 		REQ(n, RHS);

   292 		compile_rhs(ll, nf, n, pa, pb);

   293 		n++;

   294 		REQ(n, RPAR);

   295 	}

   296 	else if (n->n_type == NAME || n->n_type == STRING) {

   297 		*pa = addnfastate(nf);

   298 		*pb = addnfastate(nf);

   299 		addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));

   300 	}

   301 	else

   302 		REQ(n, NAME);

   303 }

   304 

   305 static void

   306 dumpstate(labellist *ll, nfa *nf, int istate)

   307 {

   308 	nfastate *st;

   309 	int i;

   310 	nfaarc *ar;

   311 	

   312 	printf("%c%2d%c",

   313 		istate == nf->nf_start ? '*' : ' ',

   314 		istate,

   315 		istate == nf->nf_finish ? '.' : ' ');

   316 	st = &nf->nf_state[istate];

   317 	ar = st->st_arc;

   318 	for (i = 0; i < st->st_narcs; i++) {

   319 		if (i > 0)

   320 			printf("\n    ");

   321 		printf("-> %2d  %s", ar->ar_arrow,

   322 			PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));

   323 		ar++;

   324 	}

   325 	printf("\n");

   326 }

   327 

   328 static void

   329 dumpnfa(labellist *ll, nfa *nf)

   330 {

   331 	int i;

   332 	

   333 	printf("NFA '%s' has %d states; start %d, finish %d\n",

   334 		nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);

   335 	for (i = 0; i < nf->nf_nstates; i++)

   336 		dumpstate(ll, nf, i);

   337 }

   338 

   339 

   340 /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */

   341 

   342 static void

   343 addclosure(bitset ss, nfa *nf, int istate)

   344 {

   345 	if (addbit(ss, istate)) {

   346 		nfastate *st = &nf->nf_state[istate];

   347 		nfaarc *ar = st->st_arc;

   348 		int i;

   349 		

   350 		for (i = st->st_narcs; --i >= 0; ) {

   351 			if (ar->ar_label == EMPTY)

   352 				addclosure(ss, nf, ar->ar_arrow);

   353 			ar++;

   354 		}

   355 	}

   356 }

   357 

   358 typedef struct _ss_arc {

   359 	bitset	sa_bitset;

   360 	int	sa_arrow;

   361 	int	sa_label;

   362 } ss_arc;

   363 

   364 typedef struct _ss_state {

   365 	bitset	ss_ss;

   366 	int	ss_narcs;

   367 	struct _ss_arc	*ss_arc;

   368 	int	ss_deleted;

   369 	int	ss_finish;

   370 	int	ss_rename;

   371 } ss_state;

   372 

   373 typedef struct _ss_dfa {

   374 	int	sd_nstates;

   375 	ss_state *sd_state;

   376 } ss_dfa;

   377 

   378 /* Forward */

   379 static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,

   380 		       labellist *ll, char *msg);

   381 static void simplify(int xx_nstates, ss_state *xx_state);

   382 static void convert(dfa *d, int xx_nstates, ss_state *xx_state);

   383 

   384 static void

   385 makedfa(nfagrammar *gr, nfa *nf, dfa *d)

   386 {

   387 	int nbits = nf->nf_nstates;

   388 	bitset ss;

   389 	int xx_nstates;

   390 	ss_state *xx_state, *yy;

   391 	ss_arc *zz;

   392 	int istate, jstate, iarc, jarc, ibit;

   393 	nfastate *st;

   394 	nfaarc *ar;

   395 	

   396 	ss = newbitset(nbits);

   397 	addclosure(ss, nf, nf->nf_start);

   398 	xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));

   399 	if (xx_state == NULL)

   400 		Py_FatalError("no mem for xx_state in makedfa");

   401 	xx_nstates = 1;

   402 	yy = &xx_state[0];

   403 	yy->ss_ss = ss;

   404 	yy->ss_narcs = 0;

   405 	yy->ss_arc = NULL;

   406 	yy->ss_deleted = 0;

   407 	yy->ss_finish = testbit(ss, nf->nf_finish);

   408 	if (yy->ss_finish)

   409 		printf("Error: nonterminal '%s' may produce empty.\n",

   410 			nf->nf_name);

   411 	

   412 	/* This algorithm is from a book written before

   413 	   the invention of structured programming... */

   414 

   415 	/* For each unmarked state... */

   416 	for (istate = 0; istate < xx_nstates; ++istate) {

   417 		size_t size;

   418 		yy = &xx_state[istate];

   419 		ss = yy->ss_ss;

   420 		/* For all its states... */

   421 		for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {

   422 			if (!testbit(ss, ibit))

   423 				continue;

   424 			st = &nf->nf_state[ibit];

   425 			/* For all non-empty arcs from this state... */

   426 			for (iarc = 0; iarc < st->st_narcs; iarc++) {

   427 				ar = &st->st_arc[iarc];

   428 				if (ar->ar_label == EMPTY)

   429 					continue;

   430 				/* Look up in list of arcs from this state */

   431 				for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {

   432 					zz = &yy->ss_arc[jarc];

   433 					if (ar->ar_label == zz->sa_label)

   434 						goto found;

   435 				}

   436 				/* Add new arc for this state */

   437 				size = sizeof(ss_arc) * (yy->ss_narcs + 1);

   438 				yy->ss_arc = (ss_arc *)PyObject_REALLOC(

   439                                                             yy->ss_arc, size);

   440 				if (yy->ss_arc == NULL)

   441 					Py_FatalError("out of mem");

   442 				zz = &yy->ss_arc[yy->ss_narcs++];

   443 				zz->sa_label = ar->ar_label;

   444 				zz->sa_bitset = newbitset(nbits);

   445 				zz->sa_arrow = -1;

   446 			 found:	;

   447 				/* Add destination */

   448 				addclosure(zz->sa_bitset, nf, ar->ar_arrow);

   449 			}

   450 		}

   451 		/* Now look up all the arrow states */

   452 		for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {

   453 			zz = &xx_state[istate].ss_arc[jarc];

   454 			for (jstate = 0; jstate < xx_nstates; jstate++) {

   455 				if (samebitset(zz->sa_bitset,

   456 					xx_state[jstate].ss_ss, nbits)) {

   457 					zz->sa_arrow = jstate;

   458 					goto done;

   459 				}

   460 			}

   461 			size = sizeof(ss_state) * (xx_nstates + 1);

   462 			xx_state = (ss_state *)PyObject_REALLOC(xx_state, 

   463                                                                     size);

   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 	PyObject_FREE(xx_state);

   491 }

   492 

   493 static void

   494 printssdfa(int xx_nstates, ss_state *xx_state, int nbits,

   495 	   labellist *ll, char *msg)

   496 {

   497 	int i, ibit, iarc;

   498 	ss_state *yy;

   499 	ss_arc *zz;

   500 	

   501 	printf("Subset DFA %s\n", msg);

   502 	for (i = 0; i < xx_nstates; i++) {

   503 		yy = &xx_state[i];

   504 		if (yy->ss_deleted)

   505 			continue;

   506 		printf(" Subset %d", i);

   507 		if (yy->ss_finish)

   508 			printf(" (finish)");

   509 		printf(" { ");

   510 		for (ibit = 0; ibit < nbits; ibit++) {

   511 			if (testbit(yy->ss_ss, ibit))

   512 				printf("%d ", ibit);

   513 		}

   514 		printf("}\n");

   515 		for (iarc = 0; iarc < yy->ss_narcs; iarc++) {

   516 			zz = &yy->ss_arc[iarc];

   517 			printf("  Arc to state %d, label %s\n",

   518 				zz->sa_arrow,

   519 				PyGrammar_LabelRepr(

   520 					&ll->ll_label[zz->sa_label]));

   521 		}

   522 	}

   523 }

   524 

   525 

   526 /* PART THREE -- SIMPLIFY DFA */

   527 

   528 /* Simplify the DFA by repeatedly eliminating states that are

   529    equivalent to another oner.  This is NOT Algorithm 3.3 from

   530    [Aho&Ullman 77].  It does not always finds the minimal DFA,

   531    but it does usually make a much smaller one...  (For an example

   532    of sub-optimal behavior, try S: x a b+ | y a b+.)

   533 */

   534 

   535 static int

   536 samestate(ss_state *s1, ss_state *s2)

   537 {

   538 	int i;

   539 	

   540 	if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)

   541 		return 0;

   542 	for (i = 0; i < s1->ss_narcs; i++) {

   543 		if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||

   544 			s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)

   545 			return 0;

   546 	}

   547 	return 1;

   548 }

   549 

   550 static void

   551 renamestates(int xx_nstates, ss_state *xx_state, int from, int to)

   552 {

   553 	int i, j;

   554 	

   555 	if (Py_DebugFlag)

   556 		printf("Rename state %d to %d.\n", from, to);

   557 	for (i = 0; i < xx_nstates; i++) {

   558 		if (xx_state[i].ss_deleted)

   559 			continue;

   560 		for (j = 0; j < xx_state[i].ss_narcs; j++) {

   561 			if (xx_state[i].ss_arc[j].sa_arrow == from)

   562 				xx_state[i].ss_arc[j].sa_arrow = to;

   563 		}

   564 	}

   565 }

   566 

   567 static void

   568 simplify(int xx_nstates, ss_state *xx_state)

   569 {

   570 	int changes;

   571 	int i, j;

   572 	

   573 	do {

   574 		changes = 0;

   575 		for (i = 1; i < xx_nstates; i++) {

   576 			if (xx_state[i].ss_deleted)

   577 				continue;

   578 			for (j = 0; j < i; j++) {

   579 				if (xx_state[j].ss_deleted)

   580 					continue;

   581 				if (samestate(&xx_state[i], &xx_state[j])) {

   582 					xx_state[i].ss_deleted++;

   583 					renamestates(xx_nstates, xx_state,

   584 						     i, j);

   585 					changes++;

   586 					break;

   587 				}

   588 			}

   589 		}

   590 	} while (changes);

   591 }

   592 

   593 

   594 /* PART FOUR -- GENERATE PARSING TABLES */

   595 

   596 /* Convert the DFA into a grammar that can be used by our parser */

   597 

   598 static void

   599 convert(dfa *d, int xx_nstates, ss_state *xx_state)

   600 {

   601 	int i, j;

   602 	ss_state *yy;

   603 	ss_arc *zz;

   604 	

   605 	for (i = 0; i < xx_nstates; i++) {

   606 		yy = &xx_state[i];

   607 		if (yy->ss_deleted)

   608 			continue;

   609 		yy->ss_rename = addstate(d);

   610 	}

   611 	

   612 	for (i = 0; i < xx_nstates; i++) {

   613 		yy = &xx_state[i];

   614 		if (yy->ss_deleted)

   615 			continue;

   616 		for (j = 0; j < yy->ss_narcs; j++) {

   617 			zz = &yy->ss_arc[j];

   618 			addarc(d, yy->ss_rename,

   619 				xx_state[zz->sa_arrow].ss_rename,

   620 				zz->sa_label);

   621 		}

   622 		if (yy->ss_finish)

   623 			addarc(d, yy->ss_rename, yy->ss_rename, 0);

   624 	}

   625 	

   626 	d->d_initial = 0;

   627 }

   628 

   629 

   630 /* PART FIVE -- GLUE IT ALL TOGETHER */

   631 

   632 static grammar *

   633 maketables(nfagrammar *gr)

   634 {

   635 	int i;

   636 	nfa *nf;

   637 	dfa *d;

   638 	grammar *g;

   639 	

   640 	if (gr->gr_nnfas == 0)

   641 		return NULL;

   642 	g = newgrammar(gr->gr_nfa[0]->nf_type);

   643 			/* XXX first rule must be start rule */

   644 	g->g_ll = gr->gr_ll;

   645 	

   646 	for (i = 0; i < gr->gr_nnfas; i++) {

   647 		nf = gr->gr_nfa[i];

   648 		if (Py_DebugFlag) {

   649 			printf("Dump of NFA for '%s' ...\n", nf->nf_name);

   650 			dumpnfa(&gr->gr_ll, nf);

   651 			printf("Making DFA for '%s' ...\n", nf->nf_name);

   652 		}

   653 		d = adddfa(g, nf->nf_type, nf->nf_name);

   654 		makedfa(gr, gr->gr_nfa[i], d);

   655 	}

   656 	

   657 	return g;

   658 }

   659 

   660 grammar *

   661 pgen(node *n)

   662 {

   663 	nfagrammar *gr;

   664 	grammar *g;

   665 	

   666 	gr = metacompile(n);

   667 	g = maketables(gr);

   668 	translatelabels(g);

   669 	addfirstsets(g);

   670 	PyObject_FREE(gr);

   671 	return g;

   672 }

   673 

   674 grammar *

   675 Py_pgen(node *n)

   676 {

   677   return pgen(n);

   678 }

   679 

   680 /*

   681 

   682 Description

   683 -----------

   684 

   685 Input is a grammar in extended BNF (using * for repetition, + for

   686 at-least-once repetition, [] for optional parts, | for alternatives and

   687 () for grouping).  This has already been parsed and turned into a parse

   688 tree.

   689 

   690 Each rule is considered as a regular expression in its own right.

   691 It is turned into a Non-deterministic Finite Automaton (NFA), which

   692 is then turned into a Deterministic Finite Automaton (DFA), which is then

   693 optimized to reduce the number of states.  See [Aho&Ullman 77] chapter 3,

   694 or similar compiler books (this technique is more often used for lexical

   695 analyzers).

   696 

   697 The DFA's are used by the parser as parsing tables in a special way

   698 that's probably unique.  Before they are usable, the FIRST sets of all

   699 non-terminals are computed.

   700 

   701 Reference

   702 ---------

   703 

   704 [Aho&Ullman 77]

   705 	Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977

   706 	(first edition)

   707 

   708 */