Line data    Source code

       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           3 : PyGrammar_AddAccelerators(grammar *g)
      25             : {
      26             :     dfa *d;
      27             :     int i;
      28           3 :     d = g->g_dfa;
      29         258 :     for (i = g->g_ndfas; --i >= 0; d++)
      30         255 :         fixdfa(g, d);
      31           3 :     g->g_accel = 1;
      32           3 : }
      33             : 
      34             : void
      35           3 : PyGrammar_RemoveAccelerators(grammar *g)
      36             : {
      37             :     dfa *d;
      38             :     int i;
      39           3 :     g->g_accel = 0;
      40           3 :     d = g->g_dfa;
      41         258 :     for (i = g->g_ndfas; --i >= 0; d++) {
      42             :         state *s;
      43             :         int j;
      44         255 :         s = d->d_state;
      45        1341 :         for (j = 0; j < d->d_nstates; j++, s++) {
      46        1086 :             if (s->s_accel)
      47         894 :                 PyObject_FREE(s->s_accel);
      48        1086 :             s->s_accel = NULL;
      49             :         }
      50             :     }
      51           3 : }
      52             : 
      53             : static void
      54         255 : fixdfa(grammar *g, dfa *d)
      55             : {
      56             :     state *s;
      57             :     int j;
      58         255 :     s = d->d_state;
      59        1341 :     for (j = 0; j < d->d_nstates; j++, s++)
      60        1086 :         fixstate(g, s);
      61         255 : }
      62             : 
      63             : static void
      64        1086 : fixstate(grammar *g, state *s)
      65             : {
      66             :     arc *a;
      67             :     int k;
      68             :     int *accel;
      69        1086 :     int nl = g->g_ll.ll_nlabels;
      70        1086 :     s->s_accept = 0;
      71        1086 :     accel = (int *) PyObject_MALLOC(nl * sizeof(int));
      72        1086 :     if (accel == NULL) {
      73           0 :         fprintf(stderr, "no mem to build parser accelerators\n");
      74           0 :         exit(1);
      75             :     }
      76      184620 :     for (k = 0; k < nl; k++)
      77      183534 :         accel[k] = -1;
      78        1086 :     a = s->s_arc;
      79        2787 :     for (k = s->s_narcs; --k >= 0; a++) {
      80        1701 :         int lbl = a->a_lbl;
      81        1701 :         label *l = &g->g_ll.ll_label[lbl];
      82        1701 :         int type = l->lb_type;
      83        1701 :         if (a->a_arrow >= (1 << 7)) {
      84           0 :             printf("XXX too many states!\n");
      85           0 :             continue;
      86             :         }
      87        1701 :         if (ISNONTERMINAL(type)) {
      88         573 :             dfa *d1 = PyGrammar_FindDFA(g, type);
      89             :             int ibit;
      90         573 :             if (type - NT_OFFSET >= (1 << 7)) {
      91           0 :                 printf("XXX too high nonterminal number!\n");
      92           0 :                 continue;
      93             :             }
      94       97410 :             for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
      95       96837 :                 if (testbit(d1->d_first, ibit)) {
      96        5379 :                     if (accel[ibit] != -1)
      97           0 :                         printf("XXX ambiguity!\n");
      98       10758 :                     accel[ibit] = a->a_arrow | (1 << 7) |
      99        5379 :                         ((type - NT_OFFSET) << 8);
     100             :                 }
     101             :             }
     102             :         }
     103        1128 :         else if (lbl == EMPTY)
     104         447 :             s->s_accept = 1;
     105         681 :         else if (lbl >= 0 && lbl < nl)
     106         681 :             accel[lbl] = a->a_arrow;
     107             :     }
     108       96561 :     while (nl > 0 && accel[nl-1] == -1)
     109       94389 :         nl--;
     110       33891 :     for (k = 0; k < nl && accel[k] == -1;)
     111       31719 :         k++;
     112        1086 :     if (k < nl) {
     113             :         int i;
     114         894 :         s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
     115         894 :         if (s->s_accel == NULL) {
     116           0 :             fprintf(stderr, "no mem to add parser accelerators\n");
     117           0 :             exit(1);
     118             :         }
     119         894 :         s->s_lower = k;
     120         894 :         s->s_upper = nl;
     121       58320 :         for (i = 0; k < nl; i++, k++)
     122       57426 :             s->s_accel[i] = accel[k];
     123             :     }
     124        1086 :     PyObject_FREE(accel);
     125        1086 : }