Line data    Source code

       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           0 : addfirstsets(grammar *g)
      15             : {
      16             :     int i;
      17             :     dfa *d;
      18             : 
      19           0 :     if (Py_DebugFlag)
      20           0 :         printf("Adding FIRST sets ...\n");
      21           0 :     for (i = 0; i < g->g_ndfas; i++) {
      22           0 :         d = &g->g_dfa[i];
      23           0 :         if (d->d_first == NULL)
      24           0 :             calcfirstset(g, d);
      25             :     }
      26           0 : }
      27             : 
      28             : static void
      29           0 : 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           0 :     if (Py_DebugFlag)
      44           0 :         printf("Calculate FIRST set for '%s'\n", d->d_name);
      45             : 
      46           0 :     if (dummy == NULL)
      47           0 :         dummy = newbitset(1);
      48           0 :     if (d->d_first == dummy) {
      49           0 :         fprintf(stderr, "Left-recursion for '%s'\n", d->d_name);
      50           0 :         return;
      51             :     }
      52           0 :     if (d->d_first != NULL) {
      53           0 :         fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n",
      54             :             d->d_name);
      55             :     }
      56           0 :     d->d_first = dummy;
      57             : 
      58           0 :     l0 = g->g_ll.ll_label;
      59           0 :     nbits = g->g_ll.ll_nlabels;
      60           0 :     result = newbitset(nbits);
      61             : 
      62           0 :     sym = (int *)PyObject_MALLOC(sizeof(int));
      63           0 :     if (sym == NULL)
      64           0 :         Py_FatalError("no mem for new sym in calcfirstset");
      65           0 :     nsyms = 1;
      66           0 :     sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL);
      67             : 
      68           0 :     s = &d->d_state[d->d_initial];
      69           0 :     for (i = 0; i < s->s_narcs; i++) {
      70           0 :         a = &s->s_arc[i];
      71           0 :         for (j = 0; j < nsyms; j++) {
      72           0 :             if (sym[j] == a->a_lbl)
      73           0 :                 break;
      74             :         }
      75           0 :         if (j >= nsyms) { /* New label */
      76           0 :             sym = (int *)PyObject_REALLOC(sym,
      77             :                                     sizeof(int) * (nsyms + 1));
      78           0 :             if (sym == NULL)
      79           0 :                 Py_FatalError(
      80             :                     "no mem to resize sym in calcfirstset");
      81           0 :             sym[nsyms++] = a->a_lbl;
      82           0 :             type = l0[a->a_lbl].lb_type;
      83           0 :             if (ISNONTERMINAL(type)) {
      84           0 :                 d1 = PyGrammar_FindDFA(g, type);
      85           0 :                 if (d1->d_first == dummy) {
      86           0 :                     fprintf(stderr,
      87             :                         "Left-recursion below '%s'\n",
      88             :                         d->d_name);
      89             :                 }
      90             :                 else {
      91           0 :                     if (d1->d_first == NULL)
      92           0 :                         calcfirstset(g, d1);
      93           0 :                     mergebitset(result,
      94             :                                 d1->d_first, nbits);
      95             :                 }
      96             :             }
      97           0 :             else if (ISTERMINAL(type)) {
      98           0 :                 addbit(result, a->a_lbl);
      99             :             }
     100             :         }
     101             :     }
     102           0 :     d->d_first = result;
     103           0 :     if (Py_DebugFlag) {
     104           0 :         printf("FIRST set for '%s': {", d->d_name);
     105           0 :         for (i = 0; i < nbits; i++) {
     106           0 :             if (testbit(result, i))
     107           0 :                 printf(" %s", PyGrammar_LabelRepr(&l0[i]));
     108             :         }
     109           0 :         printf(" }\n");
     110             :     }
     111             : 
     112           0 :     PyObject_FREE(sym);
     113             : }