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