AppPkg/Applications/Python/Python-2.7.10/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 }