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         for (k = 0; k < nl; k++)
  73                 accel[k] = -1;
  74         a = s->s_arc;
  75         for (k = s->s_narcs; --k >= 0; a++) {
  76                 int lbl = a->a_lbl;
  77                 label *l = &g->g_ll.ll_label[lbl];
  78                 int type = l->lb_type;
  79                 if (a->a_arrow >= (1 << 7)) {
  80                         printf("XXX too many states!\n");
  81                         continue;
  82                 }
  83                 if (ISNONTERMINAL(type)) {
  84                         dfa *d1 = PyGrammar_FindDFA(g, type);
  85                         int ibit;
  86                         if (type - NT_OFFSET >= (1 << 7)) {
  87                                 printf("XXX too high nonterminal number!\n");
  88                                 continue;
  89                         }
  90                         for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
  91                                 if (testbit(d1->d_first, ibit)) {
  92 #ifdef applec
  93 #define MPW_881_BUG                     /* Undefine if bug below is fixed */
  94 #endif
  95 #ifdef MPW_881_BUG
  96                                         /* In 881 mode MPW 3.1 has a code
  97                                            generation bug which seems to
  98                                            set the upper bits; fix this by
  99                                            explicitly masking them off */
 100                                         int temp;
 101 #endif
 102                                         if (accel[ibit] != -1)
 103                                                 printf("XXX ambiguity!\n");
 104 #ifdef MPW_881_BUG
 105                                         temp = 0xFFFF &
 106                                                 (a->a_arrow | (1 << 7) |
 107                                                  ((type - NT_OFFSET) << 8));
 108                                         accel[ibit] = temp;
 109 #else
 110                                         accel[ibit] = a->a_arrow | (1 << 7) |
 111                                                 ((type - NT_OFFSET) << 8);
 112 #endif
 113                                 }
 114                         }
 115                 }
 116                 else if (lbl == EMPTY)
 117                         s->s_accept = 1;
 118                 else if (lbl >= 0 && lbl < nl)
 119                         accel[lbl] = a->a_arrow;
 120         }
 121         while (nl > 0 && accel[nl-1] == -1)
 122                 nl--;
 123         for (k = 0; k < nl && accel[k] == -1;)
 124                 k++;
 125         if (k < nl) {
 126                 int i;
 127                 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
 128                 if (s->s_accel == NULL) {
 129                         fprintf(stderr, "no mem to add parser accelerators\n");
 130                         exit(1);
 131                 }
 132                 s->s_lower = k;
 133                 s->s_upper = nl;
 134                 for (i = 0; k < nl; i++, k++)
 135                         s->s_accel[i] = accel[k];
 136         }
 137         PyObject_FREE(accel);
 138 }