acceler.c revision 9bfef44d97d1ae24e03717e3d59024b44626a9de 
1/***********************************************************
2Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
3Amsterdam, The Netherlands.
4
5                        All Rights Reserved
6
7Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
9provided that the above copyright notice appear in all copies and that
10both that copyright notice and this permission notice appear in
11supporting documentation, and that the names of Stichting Mathematisch
12Centrum or CWI not be used in advertising or publicity pertaining to
13distribution of the software without specific, written prior permission.
14
15STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
16THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
17FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
18FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
20ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
21OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22
23******************************************************************/
24
25/* Parser accelerator module */
26
27/* The parser as originally conceived had disappointing performance.
28   This module does some precomputation that speeds up the selection
29   of a DFA based upon a token, turning a search through an array
30   into a simple indexing operation.  The parser now cannot work
31   without the accelerators installed.  Note that the accelerators
32   are installed dynamically when the parser is initialized, they
33   are not part of the static data structure written on graminit.[ch]
34   by the parser generator. */
35
36#include "pgenheaders.h"
37#include "grammar.h"
38#include "token.h"
39#include "parser.h"
40
41/* Forward references */
42static void fixdfa PROTO((grammar *, dfa *));
43static void fixstate PROTO((grammar *, state *));
44
45void
46addaccelerators(g)
47	grammar *g;
48{
49	dfa *d;
50	int i;
51#ifdef DEBUG
52	fprintf(stderr, "Adding parser accelerators ...\n");
53#endif
54	d = g->g_dfa;
55	for (i = g->g_ndfas; --i >= 0; d++)
56		fixdfa(g, d);
57	g->g_accel = 1;
58#ifdef DEBUG
59	fprintf(stderr, "Done.\n");
60#endif
61}
62
63static void
64fixdfa(g, d)
65	grammar *g;
66	dfa *d;
67{
68	state *s;
69	int j;
70	s = d->d_state;
71	for (j = 0; j < d->d_nstates; j++, s++)
72		fixstate(g, s);
73}
74
75static void
76fixstate(g, s)
77	grammar *g;
78	state *s;
79{
80	arc *a;
81	int k;
82	int *accel;
83	int nl = g->g_ll.ll_nlabels;
84	s->s_accept = 0;
85	accel = NEW(int, nl);
86	for (k = 0; k < nl; k++)
87		accel[k] = -1;
88	a = s->s_arc;
89	for (k = s->s_narcs; --k >= 0; a++) {
90		int lbl = a->a_lbl;
91		label *l = &g->g_ll.ll_label[lbl];
92		int type = l->lb_type;
93		if (a->a_arrow >= (1 << 7)) {
94			printf("XXX too many states!\n");
95			continue;
96		}
97		if (ISNONTERMINAL(type)) {
98			dfa *d1 = finddfa(g, type);
99			int ibit;
100			if (type - NT_OFFSET >= (1 << 7)) {
101				printf("XXX too high nonterminal number!\n");
102				continue;
103			}
104			for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
105				if (testbit(d1->d_first, ibit)) {
106#ifdef applec
107#define MPW_881_bug			/* Undefine if bug below is fixed */
108#endif
109#ifdef MPW_881_BUG
110					/* In 881 mode MPW 3.1 has a code
111					   generation bug which seems to
112					   set the upper bits; fix this by
113					   explicitly masking them off */
114					int temp;
115#endif
116					if (accel[ibit] != -1)
117						printf("XXX ambiguity!\n");
118#ifdef MPW_881_BUG
119					temp = 0xFFFF &
120						(a->a_arrow | (1 << 7) |
121						 ((type - NT_OFFSET) << 8));
122					accel[ibit] = temp;
123#else
124					accel[ibit] = a->a_arrow | (1 << 7) |
125						((type - NT_OFFSET) << 8);
126#endif
127				}
128			}
129		}
130		else if (lbl == EMPTY)
131			s->s_accept = 1;
132		else if (lbl >= 0 && lbl < nl)
133			accel[lbl] = a->a_arrow;
134	}
135	while (nl > 0 && accel[nl-1] == -1)
136		nl--;
137	for (k = 0; k < nl && accel[k] == -1;)
138		k++;
139	if (k < nl) {
140		int i;
141		s->s_accel = NEW(int, nl-k);
142		if (s->s_accel == NULL) {
143			fprintf(stderr, "no mem to add parser accelerators\n");
144			exit(1);
145		}
146		s->s_lower = k;
147		s->s_upper = nl;
148		for (i = 0; k < nl; i++, k++)
149			s->s_accel[i] = accel[k];
150	}
151	DEL(accel);
152}
153