Parser/acceler.c

   1
   2 /* Parser accelerator module */
   3
   4 /* The parser as originally conceived had disappointing performance.
   5    This module does some precomputation that speeds up the selection
   6    of a DFA based upon a token, turning a search through an array
   7    into a simple indexing operation.  The parser now cannot work
   8    without the accelerators installed.  Note that the accelerators
   9    are installed dynamically when the parser is initialized, they
  10    are not part of the static data structure written on graminit.[ch]
  11    by the parser generator. */
  12
  13 #include "pgenheaders.h"
  14 #include "grammar.h"
  15 #include "node.h"
  16 #include "token.h"
  17 #include "parser.h"
  18
  19 /* Forward references */
  20 static void fixdfa(grammar *, dfa *);
  21 static void fixstate(grammar *, state *);
  22
  23 void
  24 PyGrammar_AddAccelerators(grammar *g)
  25 {
  26         dfa *d;
  27         int i;
  28         d = g->g_dfa;
  29         for (i = g->g_ndfas; --i >= 0; d++)
  30                 fixdfa(g, d);
  31         g->g_accel = 1;
  32 }
  33
  34 void
  35 PyGrammar_RemoveAccelerators(grammar *g)
  36 {
  37         dfa *d;
  38         int i;
  39         g->g_accel = 0;
  40         d = g->g_dfa;
  41         for (i = g->g_ndfas; --i >= 0; d++) {
  42                 state *s;
  43                 int j;
  44                 s = d->d_state;
  45                 for (j = 0; j < d->d_nstates; j++, s++) {
  46                         if (s->s_accel)
  47                                 PyObject_FREE(s->s_accel);
  48                         s->s_accel = NULL;
  49                 }
  50         }
  51 }
  52
  53 static void
  54 fixdfa(grammar *g, dfa *d)
  55 {
  56         state *s;
  57         int j;
  58         s = d->d_state;
  59         for (j = 0; j < d->d_nstates; j++, s++)
  60                 fixstate(g, s);
  61 }
  62
  63 static void
  64 fixstate(grammar *g, state *s)
  65 {
  66         arc *a;
  67         int k;
  68         int *accel;
  69         int nl = g->g_ll.ll_nlabels;
  70         s->s_accept = 0;
  71         accel = (int *) PyObject_MALLOC(nl * sizeof(int));
  72         if (accel == NULL) {
  73                 fprintf(stderr, "no mem to build parser accelerators\n");
  74                 exit(1);
  75         }
  76         for (k = 0; k < nl; k++)
  77                 accel[k] = -1;
  78         a = s->s_arc;
  79         for (k = s->s_narcs; --k >= 0; a++) {
  80                 int lbl = a->a_lbl;
  81                 label *l = &g->g_ll.ll_label[lbl];
  82                 int type = l->lb_type;
  83                 if (a->a_arrow >= (1 << 7)) {
  84                         printf("XXX too many states!\n");
  85                         continue;
  86                 }
  87                 if (ISNONTERMINAL(type)) {
  88                         dfa *d1 = PyGrammar_FindDFA(g, type);
  89                         int ibit;
  90                         if (type - NT_OFFSET >= (1 << 7)) {
  91                                 printf("XXX too high nonterminal number!\n");
  92                                 continue;
  93                         }
  94                         for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
  95                                 if (testbit(d1->d_first, ibit)) {
  96                                         if (accel[ibit] != -1)
  97                                                 printf("XXX ambiguity!\n");
  98                                         accel[ibit] = a->a_arrow | (1 << 7) |
  99                                                 ((type - NT_OFFSET) << 8);
 100                                 }
 101                         }
 102                 }
 103                 else if (lbl == EMPTY)
 104                         s->s_accept = 1;
 105                 else if (lbl >= 0 && lbl < nl)
 106                         accel[lbl] = a->a_arrow;
 107         }
 108         while (nl > 0 && accel[nl-1] == -1)
 109                 nl--;
 110         for (k = 0; k < nl && accel[k] == -1;)
 111                 k++;
 112         if (k < nl) {
 113                 int i;
 114                 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
 115                 if (s->s_accel == NULL) {
 116                         fprintf(stderr, "no mem to add parser accelerators\n");
 117                         exit(1);
 118                 }
 119                 s->s_lower = k;
 120                 s->s_upper = nl;
 121                 for (i = 0; k < nl; i++, k++)
 122                         s->s_accel[i] = accel[k];
 123         }
 124         PyObject_FREE(accel);
 125 }