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