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 #ifdef Py_DEBUG
  29         fprintf(stderr, "Adding parser accelerators ...\n");
  30 #endif
  31         d = g->g_dfa;
  32         for (i = g->g_ndfas; --i >= 0; d++)
  33                 fixdfa(g, d);
  34         g->g_accel = 1;
  35 #ifdef Py_DEBUG
  36         fprintf(stderr, "Done.\n");
  37 #endif
  38 }
  39
  40 void
  41 PyGrammar_RemoveAccelerators(grammar *g)
  42 {
  43         dfa *d;
  44         int i;
  45         g->g_accel = 0;
  46         d = g->g_dfa;
  47         for (i = g->g_ndfas; --i >= 0; d++) {
  48                 state *s;
  49                 int j;
  50                 s = d->d_state;
  51                 for (j = 0; j < d->d_nstates; j++, s++) {
  52                         if (s->s_accel)
  53                                 PyMem_DEL(s->s_accel);
  54                         s->s_accel = NULL;
  55                 }
  56         }
  57 }
  58
  59 static void
  60 fixdfa(grammar *g, dfa *d)
  61 {
  62         state *s;
  63         int j;
  64         s = d->d_state;
  65         for (j = 0; j < d->d_nstates; j++, s++)
  66                 fixstate(g, s);
  67 }
  68
  69 static void
  70 fixstate(grammar *g, state *s)
  71 {
  72         arc *a;
  73         int k;
  74         int *accel;
  75         int nl = g->g_ll.ll_nlabels;
  76         s->s_accept = 0;
  77         accel = PyMem_NEW(int, nl);
  78         for (k = 0; k < nl; k++)
  79                 accel[k] = -1;
  80         a = s->s_arc;
  81         for (k = s->s_narcs; --k >= 0; a++) {
  82                 int lbl = a->a_lbl;
  83                 label *l = &g->g_ll.ll_label[lbl];
  84                 int type = l->lb_type;
  85                 if (a->a_arrow >= (1 << 7)) {
  86                         printf("XXX too many states!\n");
  87                         continue;
  88                 }
  89                 if (ISNONTERMINAL(type)) {
  90                         dfa *d1 = PyGrammar_FindDFA(g, type);
  91                         int ibit;
  92                         if (type - NT_OFFSET >= (1 << 7)) {
  93                                 printf("XXX too high nonterminal number!\n");
  94                                 continue;
  95                         }
  96                         for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
  97                                 if (testbit(d1->d_first, ibit)) {
  98 #ifdef applec
  99 #define MPW_881_BUG                     /* Undefine if bug below is fixed */
 100 #endif
 101 #ifdef MPW_881_BUG
 102                                         /* In 881 mode MPW 3.1 has a code
 103                                            generation bug which seems to
 104                                            set the upper bits; fix this by
 105                                            explicitly masking them off */
 106                                         int temp;
 107 #endif
 108                                         if (accel[ibit] != -1)
 109                                                 printf("XXX ambiguity!\n");
 110 #ifdef MPW_881_BUG
 111                                         temp = 0xFFFF &
 112                                                 (a->a_arrow | (1 << 7) |
 113                                                  ((type - NT_OFFSET) << 8));
 114                                         accel[ibit] = temp;
 115 #else
 116                                         accel[ibit] = a->a_arrow | (1 << 7) |
 117                                                 ((type - NT_OFFSET) << 8);
 118 #endif
 119                                 }
 120                         }
 121                 }
 122                 else if (lbl == EMPTY)
 123                         s->s_accept = 1;
 124                 else if (lbl >= 0 && lbl < nl)
 125                         accel[lbl] = a->a_arrow;
 126         }
 127         while (nl > 0 && accel[nl-1] == -1)
 128                 nl--;
 129         for (k = 0; k < nl && accel[k] == -1;)
 130                 k++;
 131         if (k < nl) {
 132                 int i;
 133                 s->s_accel = PyMem_NEW(int, nl-k);
 134                 if (s->s_accel == NULL) {
 135                         fprintf(stderr, "no mem to add parser accelerators\n");
 136                         exit(1);
 137                 }
 138                 s->s_lower = k;
 139                 s->s_upper = nl;
 140                 for (i = 0; k < nl; i++, k++)
 141                         s->s_accel[i] = accel[k];
 142         }
 143         PyMem_DEL(accel);
 144 }