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