home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 15 / AACD15.ISO / AACD / Programming / Python2 / Python20_source / Parser / firstsets.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-10-25  |  2.1 KB  |  110 lines
  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. }
  110.