No issues found
1 /* Parser accelerator module */
2
3 /* The parser as originally conceived had disappointing performance.
4 This module does some precomputation that speeds up the selection
5 of a DFA based upon a token, turning a search through an array
6 into a simple indexing operation. The parser now cannot work
7 without the accelerators installed. Note that the accelerators
8 are installed dynamically when the parser is initialized, they
9 are not part of the static data structure written on graminit.[ch]
10 by the parser generator. */
11
12 #include "pgenheaders.h"
13 #include "grammar.h"
14 #include "node.h"
15 #include "token.h"
16 #include "parser.h"
17
18 /* Forward references */
19 static void fixdfa(grammar *, dfa *);
20 static void fixstate(grammar *, state *);
21
22 void
23 PyGrammar_AddAccelerators(grammar *g)
24 {
25 dfa *d;
26 int i;
27 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
34 PyGrammar_RemoveAccelerators(grammar *g)
35 {
36 dfa *d;
37 int i;
38 g->g_accel = 0;
39 d = g->g_dfa;
40 for (i = g->g_ndfas; --i >= 0; d++) {
41 state *s;
42 int j;
43 s = d->d_state;
44 for (j = 0; j < d->d_nstates; j++, s++) {
45 if (s->s_accel)
46 PyObject_FREE(s->s_accel);
47 s->s_accel = NULL;
48 }
49 }
50 }
51
52 static void
53 fixdfa(grammar *g, dfa *d)
54 {
55 state *s;
56 int j;
57 s = d->d_state;
58 for (j = 0; j < d->d_nstates; j++, s++)
59 fixstate(g, s);
60 }
61
62 static void
63 fixstate(grammar *g, state *s)
64 {
65 arc *a;
66 int k;
67 int *accel;
68 int nl = g->g_ll.ll_nlabels;
69 s->s_accept = 0;
70 accel = (int *) PyObject_MALLOC(nl * sizeof(int));
71 if (accel == NULL) {
72 fprintf(stderr, "no mem to build parser accelerators\n");
73 exit(1);
74 }
75 for (k = 0; k < nl; k++)
76 accel[k] = -1;
77 a = s->s_arc;
78 for (k = s->s_narcs; --k >= 0; a++) {
79 int lbl = a->a_lbl;
80 label *l = &g->g_ll.ll_label[lbl];
81 int type = l->lb_type;
82 if (a->a_arrow >= (1 << 7)) {
83 printf("XXX too many states!\n");
84 continue;
85 }
86 if (ISNONTERMINAL(type)) {
87 dfa *d1 = PyGrammar_FindDFA(g, type);
88 int ibit;
89 if (type - NT_OFFSET >= (1 << 7)) {
90 printf("XXX too high nonterminal number!\n");
91 continue;
92 }
93 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
94 if (testbit(d1->d_first, ibit)) {
95 if (accel[ibit] != -1)
96 printf("XXX ambiguity!\n");
97 accel[ibit] = a->a_arrow | (1 << 7) |
98 ((type - NT_OFFSET) << 8);
99 }
100 }
101 }
102 else if (lbl == EMPTY)
103 s->s_accept = 1;
104 else if (lbl >= 0 && lbl < nl)
105 accel[lbl] = a->a_arrow;
106 }
107 while (nl > 0 && accel[nl-1] == -1)
108 nl--;
109 for (k = 0; k < nl && accel[k] == -1;)
110 k++;
111 if (k < nl) {
112 int i;
113 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
114 if (s->s_accel == NULL) {
115 fprintf(stderr, "no mem to add parser accelerators\n");
116 exit(1);
117 }
118 s->s_lower = k;
119 s->s_upper = nl;
120 for (i = 0; k < nl; i++, k++)
121 s->s_accel[i] = accel[k];
122 }
123 PyObject_FREE(accel);
124 }