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
PyGrammar_AddAccelerators(grammar * g)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
PyGrammar_RemoveAccelerators(grammar * g)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
fixdfa(grammar * g,dfa * d)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
fixstate(grammar * g,state * s)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