grammar.c revision 8586991099e4ace18ee94163a96b8ea1bed77ebe 
1
2/* Grammar implementation */
3
4#include "pgenheaders.h"
5
6#include <ctype.h>
7
8#include "assert.h"
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 = 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 = str; /* XXX strdup(str) ??? */
102	return lb - ll->ll_label;
103}
104
105/* Same, but rather dies than adds */
106
107int
108findlabel(labellist *ll, int type, char *str)
109{
110	int i;
111
112	for (i = 0; i < ll->ll_nlabels; i++) {
113		if (ll->ll_label[i].lb_type == type /*&&
114			strcmp(ll->ll_label[i].lb_str, str) == 0*/)
115			return i;
116	}
117	fprintf(stderr, "Label %d/'%s' not found\n", type, str);
118	Py_FatalError("grammar.c:findlabel()");
119	return 0; /* Make gcc -Wall happy */
120}
121
122/* Forward */
123static void translabel(grammar *, label *);
124
125void
126translatelabels(grammar *g)
127{
128	int i;
129
130#ifdef Py_DEBUG
131	printf("Translating labels ...\n");
132#endif
133	/* Don't translate EMPTY */
134	for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
135		translabel(g, &g->g_ll.ll_label[i]);
136}
137
138static void
139translabel(grammar *g, label *lb)
140{
141	int i;
142
143	if (Py_DebugFlag)
144		printf("Translating label %s ...\n", PyGrammar_LabelRepr(lb));
145
146	if (lb->lb_type == NAME) {
147		for (i = 0; i < g->g_ndfas; i++) {
148			if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
149				if (Py_DebugFlag)
150					printf(
151					    "Label %s is non-terminal %d.\n",
152					    lb->lb_str,
153					    g->g_dfa[i].d_type);
154				lb->lb_type = g->g_dfa[i].d_type;
155				lb->lb_str = NULL;
156				return;
157			}
158		}
159		for (i = 0; i < (int)N_TOKENS; i++) {
160			if (strcmp(lb->lb_str, _PyParser_TokenNames[i]) == 0) {
161				if (Py_DebugFlag)
162					printf("Label %s is terminal %d.\n",
163						lb->lb_str, i);
164				lb->lb_type = i;
165				lb->lb_str = NULL;
166				return;
167			}
168		}
169		printf("Can't translate NAME label '%s'\n", lb->lb_str);
170		return;
171	}
172
173	if (lb->lb_type == STRING) {
174		if (isalpha((int)(lb->lb_str[1])) || lb->lb_str[1] == '_') {
175			char *p;
176			if (Py_DebugFlag)
177				printf("Label %s is a keyword\n", lb->lb_str);
178			lb->lb_type = NAME;
179			lb->lb_str++;
180			p = strchr(lb->lb_str, '\'');
181			if (p)
182				*p = '\0';
183		}
184		else if (lb->lb_str[2] == lb->lb_str[0]) {
185			int type = (int) PyToken_OneChar(lb->lb_str[1]);
186			if (type != OP) {
187				lb->lb_type = type;
188				lb->lb_str = NULL;
189			}
190			else
191				printf("Unknown OP label %s\n",
192					lb->lb_str);
193		}
194		else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
195			int type = (int) PyToken_TwoChars(lb->lb_str[1],
196						   lb->lb_str[2]);
197			if (type != OP) {
198				lb->lb_type = type;
199				lb->lb_str = NULL;
200			}
201			else
202				printf("Unknown OP label %s\n",
203					lb->lb_str);
204		}
205		else if (lb->lb_str[2] && lb->lb_str[3] && lb->lb_str[4] == lb->lb_str[0]) {
206			int type = (int) PyToken_ThreeChars(lb->lb_str[1],
207							    lb->lb_str[2],
208							    lb->lb_str[3]);
209			if (type != OP) {
210				lb->lb_type = type;
211				lb->lb_str = NULL;
212			}
213			else
214				printf("Unknown OP label %s\n",
215					lb->lb_str);
216		}
217		else
218			printf("Can't translate STRING label %s\n",
219				lb->lb_str);
220	}
221	else
222		printf("Can't translate label '%s'\n",
223		       PyGrammar_LabelRepr(lb));
224}
225