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