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