ยปCore Development>Code coverage>Parser/pgen.c

Python code coverage for Parser/pgen.c

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