acceler.c 3.08 KB
Newer Older
1

Guido van Rossum's avatar
Guido van Rossum committed
2 3
/* Parser accelerator module */

Guido van Rossum's avatar
Guido van Rossum committed
4 5 6 7 8 9 10 11
/* The parser as originally conceived had disappointing performance.
   This module does some precomputation that speeds up the selection
   of a DFA based upon a token, turning a search through an array
   into a simple indexing operation.  The parser now cannot work
   without the accelerators installed.  Note that the accelerators
   are installed dynamically when the parser is initialized, they
   are not part of the static data structure written on graminit.[ch]
   by the parser generator. */
Guido van Rossum's avatar
Guido van Rossum committed
12

Guido van Rossum's avatar
Guido van Rossum committed
13
#include "pgenheaders.h"
Guido van Rossum's avatar
Guido van Rossum committed
14
#include "grammar.h"
15
#include "node.h"
Guido van Rossum's avatar
Guido van Rossum committed
16
#include "token.h"
Guido van Rossum's avatar
Guido van Rossum committed
17 18 19
#include "parser.h"

/* Forward references */
20 21
static void fixdfa(grammar *, dfa *);
static void fixstate(grammar *, state *);
Guido van Rossum's avatar
Guido van Rossum committed
22 23

void
Thomas Wouters's avatar
Thomas Wouters committed
24
PyGrammar_AddAccelerators(grammar *g)
Guido van Rossum's avatar
Guido van Rossum committed
25 26 27 28 29 30 31 32 33
{
	dfa *d;
	int i;
	d = g->g_dfa;
	for (i = g->g_ndfas; --i >= 0; d++)
		fixdfa(g, d);
	g->g_accel = 1;
}

34
void
Thomas Wouters's avatar
Thomas Wouters committed
35
PyGrammar_RemoveAccelerators(grammar *g)
36 37 38 39 40 41 42 43 44 45 46
{
	dfa *d;
	int i;
	g->g_accel = 0;
	d = g->g_dfa;
	for (i = g->g_ndfas; --i >= 0; d++) {
		state *s;
		int j;
		s = d->d_state;
		for (j = 0; j < d->d_nstates; j++, s++) {
			if (s->s_accel)
Andrew MacIntyre's avatar
Andrew MacIntyre committed
47
				PyObject_FREE(s->s_accel);
48 49 50 51 52
			s->s_accel = NULL;
		}
	}
}

Guido van Rossum's avatar
Guido van Rossum committed
53
static void
Thomas Wouters's avatar
Thomas Wouters committed
54
fixdfa(grammar *g, dfa *d)
Guido van Rossum's avatar
Guido van Rossum committed
55 56 57 58 59
{
	state *s;
	int j;
	s = d->d_state;
	for (j = 0; j < d->d_nstates; j++, s++)
Guido van Rossum's avatar
Guido van Rossum committed
60
		fixstate(g, s);
Guido van Rossum's avatar
Guido van Rossum committed
61
}
Guido van Rossum's avatar
Guido van Rossum committed
62 63

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