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