acceler.c revision 7b4c8e485c6ec3cc4605b6e1a24bd3a324f1c0a5 
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				PyMem_DEL(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 = PyMem_NEW(int, nl);
72	for (k = 0; k < nl; k++)
73		accel[k] = -1;
74	a = s->s_arc;
75	for (k = s->s_narcs; --k >= 0; a++) {
76		int lbl = a->a_lbl;
77		label *l = &g->g_ll.ll_label[lbl];
78		int type = l->lb_type;
79		if (a->a_arrow >= (1 << 7)) {
80			printf("XXX too many states!\n");
81			continue;
82		}
83		if (ISNONTERMINAL(type)) {
84			dfa *d1 = PyGrammar_FindDFA(g, type);
85			int ibit;
86			if (type - NT_OFFSET >= (1 << 7)) {
87				printf("XXX too high nonterminal number!\n");
88				continue;
89			}
90			for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
91				if (testbit(d1->d_first, ibit)) {
92#ifdef applec
93#define MPW_881_BUG			/* Undefine if bug below is fixed */
94#endif
95#ifdef MPW_881_BUG
96					/* In 881 mode MPW 3.1 has a code
97					   generation bug which seems to
98					   set the upper bits; fix this by
99					   explicitly masking them off */
100					int temp;
101#endif
102					if (accel[ibit] != -1)
103						printf("XXX ambiguity!\n");
104#ifdef MPW_881_BUG
105					temp = 0xFFFF &
106						(a->a_arrow | (1 << 7) |
107						 ((type - NT_OFFSET) << 8));
108					accel[ibit] = temp;
109#else
110					accel[ibit] = a->a_arrow | (1 << 7) |
111						((type - NT_OFFSET) << 8);
112#endif
113				}
114			}
115		}
116		else if (lbl == EMPTY)
117			s->s_accept = 1;
118		else if (lbl >= 0 && lbl < nl)
119			accel[lbl] = a->a_arrow;
120	}
121	while (nl > 0 && accel[nl-1] == -1)
122		nl--;
123	for (k = 0; k < nl && accel[k] == -1;)
124		k++;
125	if (k < nl) {
126		int i;
127		s->s_accel = PyMem_NEW(int, nl-k);
128		if (s->s_accel == NULL) {
129			fprintf(stderr, "no mem to add parser accelerators\n");
130			exit(1);
131		}
132		s->s_lower = k;
133		s->s_upper = nl;
134		for (i = 0; k < nl; i++, k++)
135			s->s_accel[i] = accel[k];
136	}
137	PyMem_DEL(accel);
138}
139