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