acceler.c revision 3f5da24ea304e674a9abbdcffc4d671e32aa70f1 
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 "token.h"
15#include "parser.h"
16
17/* Forward references */
18static void fixdfa PROTO((grammar *, dfa *));
19static void fixstate PROTO((grammar *, dfa *, state *));
20
21void
22addaccelerators(g)
23	grammar *g;
24{
25	dfa *d;
26	int i;
27#ifdef DEBUG
28	printf("Adding parser accellerators ...\n");
29#endif
30	d = g->g_dfa;
31	for (i = g->g_ndfas; --i >= 0; d++)
32		fixdfa(g, d);
33	g->g_accel = 1;
34#ifdef DEBUG
35	printf("Done.\n");
36#endif
37}
38
39static void
40fixdfa(g, d)
41	grammar *g;
42	dfa *d;
43{
44	state *s;
45	int j;
46	s = d->d_state;
47	for (j = 0; j < d->d_nstates; j++, s++)
48		fixstate(g, d, s);
49}
50
51static void
52fixstate(g, d, s)
53	grammar *g;
54	dfa *d;
55	state *s;
56{
57	arc *a;
58	int k;
59	int *accel;
60	int nl = g->g_ll.ll_nlabels;
61	s->s_accept = 0;
62	accel = NEW(int, nl);
63	for (k = 0; k < nl; k++)
64		accel[k] = -1;
65	a = s->s_arc;
66	for (k = s->s_narcs; --k >= 0; a++) {
67		int lbl = a->a_lbl;
68		label *l = &g->g_ll.ll_label[lbl];
69		int type = l->lb_type;
70		if (a->a_arrow >= (1 << 7)) {
71			printf("XXX too many states!\n");
72			continue;
73		}
74		if (ISNONTERMINAL(type)) {
75			dfa *d1 = finddfa(g, type);
76			int ibit;
77			if (type - NT_OFFSET >= (1 << 7)) {
78				printf("XXX too high nonterminal number!\n");
79				continue;
80			}
81			for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
82				if (testbit(d1->d_first, ibit)) {
83					if (accel[ibit] != -1)
84						printf("XXX ambiguity!\n");
85					accel[ibit] = a->a_arrow | (1 << 7) |
86						((type - NT_OFFSET) << 8);
87				}
88			}
89		}
90		else if (lbl == EMPTY)
91			s->s_accept = 1;
92		else if (lbl >= 0 && lbl < nl)
93			accel[lbl] = a->a_arrow;
94	}
95	while (nl > 0 && accel[nl-1] == -1)
96		nl--;
97	for (k = 0; k < nl && accel[k] == -1;)
98		k++;
99	if (k < nl) {
100		int i;
101		s->s_accel = NEW(int, nl-k);
102		if (s->s_accel == NULL) {
103			fprintf(stderr, "no mem to add parser accelerators\n");
104			exit(1);
105		}
106		s->s_lower = k;
107		s->s_upper = nl;
108		for (i = 0; k < nl; i++, k++)
109			s->s_accel[i] = accel[k];
110	}
111	DEL(accel);
112}
113