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