Home | History | Annotate | Download | only in Parser 
      1 
      2 /* Computation of FIRST stets */
      3 
      4 #include "pgenheaders.h"
      5 #include "grammar.h"
      6 #include "token.h"
      7 
      8 extern int Py_DebugFlag;
      9 
     10 /* Forward */
     11 static void calcfirstset(grammar *, dfa *);
     12 
     13 void
     14 addfirstsets(grammar *g)
     15 {
     16     int i;
     17     dfa *d;
     18 
     19     if (Py_DebugFlag)
     20         printf("Adding FIRST sets ...\n");
     21     for (i = 0; i < g->g_ndfas; i++) {
     22         d = &g->g_dfa[i];
     23         if (d->d_first == NULL)
     24             calcfirstset(g, d);
     25     }
     26 }
     27 
     28 static void
     29 calcfirstset(grammar *g, dfa *d)
     30 {
     31     int i, j;
     32     state *s;
     33     arc *a;
     34     int nsyms;
     35     int *sym;
     36     int nbits;
     37     static bitset dummy;
     38     bitset result;
     39     int type;
     40     dfa *d1;
     41     label *l0;
     42 
     43     if (Py_DebugFlag)
     44         printf("Calculate FIRST set for '%s'\n", d->d_name);
     45 
     46     if (dummy == NULL)
     47         dummy = newbitset(1);
     48     if (d->d_first == dummy) {
     49         fprintf(stderr, "Left-recursion for '%s'\n", d->d_name);
     50         return;
     51     }
     52     if (d->d_first != NULL) {
     53         fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n",
     54             d->d_name);
     55     }
     56     d->d_first = dummy;
     57 
     58     l0 = g->g_ll.ll_label;
     59     nbits = g->g_ll.ll_nlabels;
     60     result = newbitset(nbits);
     61 
     62     sym = (int *)PyObject_MALLOC(sizeof(int));
     63     if (sym == NULL)
     64         Py_FatalError("no mem for new sym in calcfirstset");
     65     nsyms = 1;
     66     sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL);
     67 
     68     s = &d->d_state[d->d_initial];
     69     for (i = 0; i < s->s_narcs; i++) {
     70         a = &s->s_arc[i];
     71         for (j = 0; j < nsyms; j++) {
     72             if (sym[j] == a->a_lbl)
     73                 break;
     74         }
     75         if (j >= nsyms) { /* New label */
     76             sym = (int *)PyObject_REALLOC(sym,
     77                                     sizeof(int) * (nsyms + 1));
     78             if (sym == NULL)
     79                 Py_FatalError(
     80                     "no mem to resize sym in calcfirstset");
     81             sym[nsyms++] = a->a_lbl;
     82             type = l0[a->a_lbl].lb_type;
     83             if (ISNONTERMINAL(type)) {
     84                 d1 = PyGrammar_FindDFA(g, type);
     85                 if (d1->d_first == dummy) {
     86                     fprintf(stderr,
     87                         "Left-recursion below '%s'\n",
     88                         d->d_name);
     89                 }
     90                 else {
     91                     if (d1->d_first == NULL)
     92                         calcfirstset(g, d1);
     93                     mergebitset(result,
     94                                 d1->d_first, nbits);
     95                 }
     96             }
     97             else if (ISTERMINAL(type)) {
     98                 addbit(result, a->a_lbl);
     99             }
    100         }
    101     }
    102     d->d_first = result;
    103     if (Py_DebugFlag) {
    104         printf("FIRST set for '%s': {", d->d_name);
    105         for (i = 0; i < nbits; i++) {
    106             if (testbit(result, i))
    107                 printf(" %s", PyGrammar_LabelRepr(&l0[i]));
    108         }
    109         printf(" }\n");
    110     }
    111 
    112     PyObject_FREE(sym);
    113 }
    114