grammar.c 5.11 KB
Newer Older
1

Guido van Rossum's avatar
Guido van Rossum committed
2 3
/* Grammar implementation */

4
#include "Python.h"
Guido van Rossum's avatar
Guido van Rossum committed
5 6
#include "pgenheaders.h"

Guido van Rossum's avatar
Guido van Rossum committed
7 8 9 10 11
#include <ctype.h>

#include "token.h"
#include "grammar.h"

12 13 14 15
#ifdef RISCOS
#include <unixlib.h>
#endif

16
extern int Py_DebugFlag;
Guido van Rossum's avatar
Guido van Rossum committed
17 18

grammar *
Thomas Wouters's avatar
Thomas Wouters committed
19
newgrammar(int start)
Guido van Rossum's avatar
Guido van Rossum committed
20 21 22
{
	grammar *g;
	
23
	g = PyMem_NEW(grammar, 1);
Guido van Rossum's avatar
Guido van Rossum committed
24
	if (g == NULL)
25
		Py_FatalError("no mem for new grammar");
Guido van Rossum's avatar
Guido van Rossum committed
26 27 28 29 30
	g->g_ndfas = 0;
	g->g_dfa = NULL;
	g->g_start = start;
	g->g_ll.ll_nlabels = 0;
	g->g_ll.ll_label = NULL;
31
	g->g_accel = 0;
Guido van Rossum's avatar
Guido van Rossum committed
32 33 34 35
	return g;
}

dfa *
Thomas Wouters's avatar
Thomas Wouters committed
36
adddfa(grammar *g, int type, char *name)
Guido van Rossum's avatar
Guido van Rossum committed
37 38 39
{
	dfa *d;
	
40
	PyMem_RESIZE(g->g_dfa, dfa, g->g_ndfas + 1);
Guido van Rossum's avatar
Guido van Rossum committed
41
	if (g->g_dfa == NULL)
42
		Py_FatalError("no mem to resize dfa in adddfa");
Guido van Rossum's avatar
Guido van Rossum committed
43 44
	d = &g->g_dfa[g->g_ndfas++];
	d->d_type = type;
45
	d->d_name = strdup(name);
Guido van Rossum's avatar
Guido van Rossum committed
46 47 48 49 50 51 52 53
	d->d_nstates = 0;
	d->d_state = NULL;
	d->d_initial = -1;
	d->d_first = NULL;
	return d; /* Only use while fresh! */
}

int
Thomas Wouters's avatar
Thomas Wouters committed
54
addstate(dfa *d)
Guido van Rossum's avatar
Guido van Rossum committed
55 56 57
{
	state *s;
	
58
	PyMem_RESIZE(d->d_state, state, d->d_nstates + 1);
Guido van Rossum's avatar
Guido van Rossum committed
59
	if (d->d_state == NULL)
60
		Py_FatalError("no mem to resize state in addstate");
Guido van Rossum's avatar
Guido van Rossum committed
61 62 63
	s = &d->d_state[d->d_nstates++];
	s->s_narcs = 0;
	s->s_arc = NULL;
64 65 66 67
	s->s_lower = 0;
	s->s_upper = 0;
	s->s_accel = NULL;
	s->s_accept = 0;
Guido van Rossum's avatar
Guido van Rossum committed
68 69 70 71
	return s - d->d_state;
}

void
Thomas Wouters's avatar
Thomas Wouters committed
72
addarc(dfa *d, int from, int to, int lbl)
Guido van Rossum's avatar
Guido van Rossum committed
73 74 75 76 77 78 79 80
{
	state *s;
	arc *a;
	
	assert(0 <= from && from < d->d_nstates);
	assert(0 <= to && to < d->d_nstates);
	
	s = &d->d_state[from];
81
	PyMem_RESIZE(s->s_arc, arc, s->s_narcs + 1);
Guido van Rossum's avatar
Guido van Rossum committed
82
	if (s->s_arc == NULL)
83
		Py_FatalError("no mem to resize arc list in addarc");
Guido van Rossum's avatar
Guido van Rossum committed
84 85 86 87 88 89
	a = &s->s_arc[s->s_narcs++];
	a->a_lbl = lbl;
	a->a_arrow = to;
}

int
Thomas Wouters's avatar
Thomas Wouters committed
90
addlabel(labellist *ll, int type, char *str)
Guido van Rossum's avatar
Guido van Rossum committed
91 92 93 94 95 96 97 98 99
{
	int i;
	label *lb;
	
	for (i = 0; i < ll->ll_nlabels; i++) {
		if (ll->ll_label[i].lb_type == type &&
			strcmp(ll->ll_label[i].lb_str, str) == 0)
			return i;
	}
100
	PyMem_RESIZE(ll->ll_label, label, ll->ll_nlabels + 1);
Guido van Rossum's avatar
Guido van Rossum committed
101
	if (ll->ll_label == NULL)
102
		Py_FatalError("no mem to resize labellist in addlabel");
Guido van Rossum's avatar
Guido van Rossum committed
103 104
	lb = &ll->ll_label[ll->ll_nlabels++];
	lb->lb_type = type;
105 106
	lb->lb_str = strdup(str);
	if (Py_DebugFlag)
Guido van Rossum's avatar
Guido van Rossum committed
107
		printf("Label @ %8p, %d: %s\n", ll, ll->ll_nlabels,
108
		       PyGrammar_LabelRepr(lb));
Guido van Rossum's avatar
Guido van Rossum committed
109 110 111 112 113 114
	return lb - ll->ll_label;
}

/* Same, but rather dies than adds */

int
Thomas Wouters's avatar
Thomas Wouters committed
115
findlabel(labellist *ll, int type, char *str)
Guido van Rossum's avatar
Guido van Rossum committed
116 117 118 119 120 121 122 123 124
{
	int i;
	
	for (i = 0; i < ll->ll_nlabels; i++) {
		if (ll->ll_label[i].lb_type == type /*&&
			strcmp(ll->ll_label[i].lb_str, str) == 0*/)
			return i;
	}
	fprintf(stderr, "Label %d/'%s' not found\n", type, str);
125
	Py_FatalError("grammar.c:findlabel()");
Guido van Rossum's avatar
Guido van Rossum committed
126
	return 0; /* Make gcc -Wall happy */
Guido van Rossum's avatar
Guido van Rossum committed
127 128
}

Guido van Rossum's avatar
Guido van Rossum committed
129
/* Forward */
130
static void translabel(grammar *, label *);
Guido van Rossum's avatar
Guido van Rossum committed
131 132

void
Thomas Wouters's avatar
Thomas Wouters committed
133
translatelabels(grammar *g)
Guido van Rossum's avatar
Guido van Rossum committed
134 135
{
	int i;
136

137
#ifdef Py_DEBUG
Guido van Rossum's avatar
Guido van Rossum committed
138
	printf("Translating labels ...\n");
139
#endif
Guido van Rossum's avatar
Guido van Rossum committed
140 141 142 143 144
	/* Don't translate EMPTY */
	for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
		translabel(g, &g->g_ll.ll_label[i]);
}

Guido van Rossum's avatar
Guido van Rossum committed
145
static void
Thomas Wouters's avatar
Thomas Wouters committed
146
translabel(grammar *g, label *lb)
Guido van Rossum's avatar
Guido van Rossum committed
147 148 149
{
	int i;
	
150 151
	if (Py_DebugFlag)
		printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb));
Guido van Rossum's avatar
Guido van Rossum committed
152 153 154 155
	
	if (lb->lb_type == NAME) {
		for (i = 0; i < g->g_ndfas; i++) {
			if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
156 157 158 159 160
				if (Py_DebugFlag)
					printf(
					    "Label %s is non-terminal %d.\n",
					    lb->lb_str,
					    g->g_dfa[i].d_type);
Guido van Rossum's avatar
Guido van Rossum committed
161
				lb->lb_type = g->g_dfa[i].d_type;
162
				free(lb->lb_str);
Guido van Rossum's avatar
Guido van Rossum committed
163 164 165 166 167
				lb->lb_str = NULL;
				return;
			}
		}
		for (i = 0; i < (int)N_TOKENS; i++) {
168 169
			if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) {
				if (Py_DebugFlag)
Guido van Rossum's avatar
Guido van Rossum committed
170 171 172
					printf("Label %s is terminal %d.\n",
						lb->lb_str, i);
				lb->lb_type = i;
173
				free(lb->lb_str);
Guido van Rossum's avatar
Guido van Rossum committed
174 175 176 177 178 179 180 181 182
				lb->lb_str = NULL;
				return;
			}
		}
		printf("Can't translate NAME label '%s'\n", lb->lb_str);
		return;
	}
	
	if (lb->lb_type == STRING) {
183
		if (isalpha((int)(lb->lb_str[1])) || lb->lb_str[1] == '_') {
184
			char *p;
185 186 187
			char *src;
			char *dest;
			size_t name_len;
188
			if (Py_DebugFlag)
Guido van Rossum's avatar
Guido van Rossum committed
189 190
				printf("Label %s is a keyword\n", lb->lb_str);
			lb->lb_type = NAME;
191 192
			src = lb->lb_str + 1;
			p = strchr(src, '\'');
Guido van Rossum's avatar
Guido van Rossum committed
193
			if (p)
194 195 196 197 198 199 200 201
				name_len = p - src;
			else
				name_len = strlen(src);
			dest = malloc(name_len + 1);
			strncpy(dest, src, name_len);
			dest[name_len] = '\0';
			free(lb->lb_str);
			lb->lb_str = dest;
Guido van Rossum's avatar
Guido van Rossum committed
202
		}
203
		else if (lb->lb_str[2] == lb->lb_str[0]) {
204
			int type = (int) PyToken_OneChar(lb->lb_str[1]);
205 206
			if (type != OP) {
				lb->lb_type = type;
207
				free(lb->lb_str);
208 209 210 211 212 213 214
				lb->lb_str = NULL;
			}
			else
				printf("Unknown OP label %s\n",
					lb->lb_str);
		}
		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 217 218
						   lb->lb_str[2]);
			if (type != OP) {
				lb->lb_type = type;
219
				free(lb->lb_str);
220
				lb->lb_str = NULL;
Guido van Rossum's avatar
Guido van Rossum committed
221 222
			}
			else
223
				printf("Unknown OP label %s\n",
Guido van Rossum's avatar
Guido van Rossum committed
224 225
					lb->lb_str);
		}
226 227 228 229 230 231
		else if (lb->lb_str[2] && lb->lb_str[3] && lb->lb_str[4] == lb->lb_str[0]) {
			int type = (int) PyToken_ThreeChars(lb->lb_str[1],
							    lb->lb_str[2],
							    lb->lb_str[3]);
			if (type != OP) {
				lb->lb_type = type;
232
				free(lb->lb_str);
233 234 235 236 237 238
				lb->lb_str = NULL;
			}
			else
				printf("Unknown OP label %s\n",
					lb->lb_str);
		}
239 240 241
		else
			printf("Can't translate STRING label %s\n",
				lb->lb_str);
Guido van Rossum's avatar
Guido van Rossum committed
242 243
	}
	else
244 245
		printf("Can't translate label '%s'\n",
		       PyGrammar_LabelRepr(lb));
Guido van Rossum's avatar
Guido van Rossum committed
246
}