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 */
20static void fixdfa(grammar *, dfa *);
21static void fixstate(grammar *, state *);
22
23void
24PyGrammar_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
34void
35PyGrammar_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
53static void
54fixdfa(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
63static void
64fixstate(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