grammar.c revision 6dacd90a83d9a84fd0a30fc7cb53d4c1c4ca17c4 
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 debugging;
43
44grammar *
45newgrammar(start)
46	int start;
47{
48	grammar *g;
49
50	g = NEW(grammar, 1);
51	if (g == NULL)
52		fatal("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	RESIZE(g->g_dfa, dfa, g->g_ndfas + 1);
71	if (g->g_dfa == NULL)
72		fatal("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	RESIZE(d->d_state, state, d->d_nstates + 1);
90	if (d->d_state == NULL)
91		fatal("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	RESIZE(s->s_arc, arc, s->s_narcs + 1);
115	if (s->s_arc == NULL)
116		fatal("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	RESIZE(ll->ll_label, label, ll->ll_nlabels + 1);
137	if (ll->ll_label == NULL)
138		fatal("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	fatal("grammar.c:findlabel()");
162	return 0; /* Make gcc -Wall happy */
163}
164
165/* Forward */
166static void translabel 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 (debugging)
190		printf("Translating label %s ...\n", 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 (debugging)
196					printf("Label %s is non-terminal %d.\n",
197						lb->lb_str,
198						g->g_dfa[i].d_type);
199				lb->lb_type = g->g_dfa[i].d_type;
200				lb->lb_str = NULL;
201				return;
202			}
203		}
204		for (i = 0; i < (int)N_TOKENS; i++) {
205			if (strcmp(lb->lb_str, tok_name[i]) == 0) {
206				if (debugging)
207					printf("Label %s is terminal %d.\n",
208						lb->lb_str, i);
209				lb->lb_type = i;
210				lb->lb_str = NULL;
211				return;
212			}
213		}
214		printf("Can't translate NAME label '%s'\n", lb->lb_str);
215		return;
216	}
217
218	if (lb->lb_type == STRING) {
219		if (isalpha(lb->lb_str[1]) || lb->lb_str[1] == '_') {
220			char *p;
221			if (debugging)
222				printf("Label %s is a keyword\n", lb->lb_str);
223			lb->lb_type = NAME;
224			lb->lb_str++;
225			p = strchr(lb->lb_str, '\'');
226			if (p)
227				*p = '\0';
228		}
229		else if (lb->lb_str[2] == lb->lb_str[0]) {
230			int type = (int) tok_1char(lb->lb_str[1]);
231			if (type != OP) {
232				lb->lb_type = type;
233				lb->lb_str = NULL;
234			}
235			else
236				printf("Unknown OP label %s\n",
237					lb->lb_str);
238		}
239		else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
240			int type = (int) tok_2char(lb->lb_str[1],
241						   lb->lb_str[2]);
242			if (type != OP) {
243				lb->lb_type = type;
244				lb->lb_str = NULL;
245			}
246			else
247				printf("Unknown OP label %s\n",
248					lb->lb_str);
249		}
250		else
251			printf("Can't translate STRING label %s\n",
252				lb->lb_str);
253	}
254	else
255		printf("Can't translate label '%s'\n", labelrepr(lb));
256}
257