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