Home | History | Annotate | Download | only in Parser 
      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 }
    126