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