ยปCore Development>Code coverage>Parser/acceler.c

Python code coverage for Parser/acceler.c

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