Parser/firstsets.c

   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 }