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