grammar.c revision bb3649e2ba386adc16fadc2e0d1f2606c047e6aa 
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/* Grammar implementation */
33
34#include "pgenheaders.h"
35
36#include <ctype.h>
37
38#include "assert.h"
39#include "token.h"
40#include "grammar.h"
41
42extern int Py_DebugFlag;
43
44grammar *
45newgrammar(start)
46	int start;
47{
48	grammar *g;
49
50	g = PyMem_NEW(grammar, 1);
51	if (g == NULL)
52		Py_FatalError("no mem for new grammar");
53	g->g_ndfas = 0;
54	g->g_dfa = NULL;
55	g->g_start = start;
56	g->g_ll.ll_nlabels = 0;
57	g->g_ll.ll_label = NULL;
58	g->g_accel = 0;
59	return g;
60}
61
62dfa *
63adddfa(g, type, name)
64	grammar *g;
65	int type;
66	char *name;
67{
68	dfa *d;
69
70	PyMem_RESIZE(g->g_dfa, dfa, g->g_ndfas + 1);
71	if (g->g_dfa == NULL)
72		Py_FatalError("no mem to resize dfa in adddfa");
73	d = &g->g_dfa[g->g_ndfas++];
74	d->d_type = type;
75	d->d_name = name;
76	d->d_nstates = 0;
77	d->d_state = NULL;
78	d->d_initial = -1;
79	d->d_first = NULL;
80	return d; /* Only use while fresh! */
81}
82
83int
84addstate(d)
85	dfa *d;
86{
87	state *s;
88
89	PyMem_RESIZE(d->d_state, state, d->d_nstates + 1);
90	if (d->d_state == NULL)
91		Py_FatalError("no mem to resize state in addstate");
92	s = &d->d_state[d->d_nstates++];
93	s->s_narcs = 0;
94	s->s_arc = NULL;
95	s->s_lower = 0;
96	s->s_upper = 0;
97	s->s_accel = NULL;
98	s->s_accept = 0;
99	return s - d->d_state;
100}
101
102void
103addarc(d, from, to, lbl)
104	dfa *d;
105	int lbl;
106{
107	state *s;
108	arc *a;
109
110	assert(0 <= from && from < d->d_nstates);
111	assert(0 <= to && to < d->d_nstates);
112
113	s = &d->d_state[from];
114	PyMem_RESIZE(s->s_arc, arc, s->s_narcs + 1);
115	if (s->s_arc == NULL)
116		Py_FatalError("no mem to resize arc list in addarc");
117	a = &s->s_arc[s->s_narcs++];
118	a->a_lbl = lbl;
119	a->a_arrow = to;
120}
121
122int
123addlabel(ll, type, str)
124	labellist *ll;
125	int type;
126	char *str;
127{
128	int i;
129	label *lb;
130
131	for (i = 0; i < ll->ll_nlabels; i++) {
132		if (ll->ll_label[i].lb_type == type &&
133			strcmp(ll->ll_label[i].lb_str, str) == 0)
134			return i;
135	}
136	PyMem_RESIZE(ll->ll_label, label, ll->ll_nlabels + 1);
137	if (ll->ll_label == NULL)
138		Py_FatalError("no mem to resize labellist in addlabel");
139	lb = &ll->ll_label[ll->ll_nlabels++];
140	lb->lb_type = type;
141	lb->lb_str = str; /* XXX strdup(str) ??? */
142	return lb - ll->ll_label;
143}
144
145/* Same, but rather dies than adds */
146
147int
148findlabel(ll, type, str)
149	labellist *ll;
150	int type;
151	char *str;
152{
153	int i;
154
155	for (i = 0; i < ll->ll_nlabels; i++) {
156		if (ll->ll_label[i].lb_type == type /*&&
157			strcmp(ll->ll_label[i].lb_str, str) == 0*/)
158			return i;
159	}
160	fprintf(stderr, "Label %d/'%s' not found\n", type, str);
161	Py_FatalError("grammar.c:findlabel()");
162	return 0; /* Make gcc -Wall happy */
163}
164
165/* Forward */
166static void translabel Py_PROTO((grammar *, label *));
167
168void
169translatelabels(g)
170	grammar *g;
171{
172	int i;
173
174#ifdef Py_DEBUG
175	printf("Translating labels ...\n");
176#endif
177	/* Don't translate EMPTY */
178	for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
179		translabel(g, &g->g_ll.ll_label[i]);
180}
181
182static void
183translabel(g, lb)
184	grammar *g;
185	label *lb;
186{
187	int i;
188
189	if (Py_DebugFlag)
190		printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb));
191
192	if (lb->lb_type == NAME) {
193		for (i = 0; i < g->g_ndfas; i++) {
194			if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
195				if (Py_DebugFlag)
196					printf(
197					    "Label %s is non-terminal %d.\n",
198					    lb->lb_str,
199					    g->g_dfa[i].d_type);
200				lb->lb_type = g->g_dfa[i].d_type;
201				lb->lb_str = NULL;
202				return;
203			}
204		}
205		for (i = 0; i < (int)N_TOKENS; i++) {
206			if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) {
207				if (Py_DebugFlag)
208					printf("Label %s is terminal %d.\n",
209						lb->lb_str, i);
210				lb->lb_type = i;
211				lb->lb_str = NULL;
212				return;
213			}
214		}
215		printf("Can't translate NAME label '%s'\n", lb->lb_str);
216		return;
217	}
218
219	if (lb->lb_type == STRING) {
220		if (isalpha((int)(lb->lb_str[1])) || lb->lb_str[1] == '_') {
221			char *p;
222			if (Py_DebugFlag)
223				printf("Label %s is a keyword\n", lb->lb_str);
224			lb->lb_type = NAME;
225			lb->lb_str++;
226			p = strchr(lb->lb_str, '\'');
227			if (p)
228				*p = '\0';
229		}
230		else if (lb->lb_str[2] == lb->lb_str[0]) {
231			int type = (int) PyToken_OneChar(lb->lb_str[1]);
232			if (type != OP) {
233				lb->lb_type = type;
234				lb->lb_str = NULL;
235			}
236			else
237				printf("Unknown OP label %s\n",
238					lb->lb_str);
239		}
240		else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
241			int type = (int) PyToken_TwoChars(lb->lb_str[1],
242						   lb->lb_str[2]);
243			if (type != OP) {
244				lb->lb_type = type;
245				lb->lb_str = NULL;
246			}
247			else
248				printf("Unknown OP label %s\n",
249					lb->lb_str);
250		}
251		else
252			printf("Can't translate STRING label %s\n",
253				lb->lb_str);
254	}
255	else
256		printf("Can't translate label '%s'\n",
257		       PyGrammar_LabelRepr(lb));
258}
259