grammar.c revision 588633daa2fe7276ae4b0c99723094add0d965ff 
1/***********************************************************
2Copyright 1991, 1992, 1993, 1994 by Stichting Mathematisch Centrum,
3Amsterdam, The Netherlands.
4
5                        All Rights Reserved
6
7Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
9provided that the above copyright notice appear in all copies and that
10both that copyright notice and this permission notice appear in
11supporting documentation, and that the names of Stichting Mathematisch
12Centrum or CWI not be used in advertising or publicity pertaining to
13distribution of the software without specific, written prior permission.
14
15STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
16THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
17FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
18FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
20ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
21OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22
23******************************************************************/
24
25/* Grammar implementation */
26
27#include "pgenheaders.h"
28
29#include <ctype.h>
30
31#include "assert.h"
32#include "token.h"
33#include "grammar.h"
34
35extern int debugging;
36
37grammar *
38newgrammar(start)
39	int start;
40{
41	grammar *g;
42
43	g = NEW(grammar, 1);
44	if (g == NULL)
45		fatal("no mem for new grammar");
46	g->g_ndfas = 0;
47	g->g_dfa = NULL;
48	g->g_start = start;
49	g->g_ll.ll_nlabels = 0;
50	g->g_ll.ll_label = NULL;
51	g->g_accel = 0;
52	return g;
53}
54
55dfa *
56adddfa(g, type, name)
57	grammar *g;
58	int type;
59	char *name;
60{
61	dfa *d;
62
63	RESIZE(g->g_dfa, dfa, g->g_ndfas + 1);
64	if (g->g_dfa == NULL)
65		fatal("no mem to resize dfa in adddfa");
66	d = &g->g_dfa[g->g_ndfas++];
67	d->d_type = type;
68	d->d_name = name;
69	d->d_nstates = 0;
70	d->d_state = NULL;
71	d->d_initial = -1;
72	d->d_first = NULL;
73	return d; /* Only use while fresh! */
74}
75
76int
77addstate(d)
78	dfa *d;
79{
80	state *s;
81
82	RESIZE(d->d_state, state, d->d_nstates + 1);
83	if (d->d_state == NULL)
84		fatal("no mem to resize state in addstate");
85	s = &d->d_state[d->d_nstates++];
86	s->s_narcs = 0;
87	s->s_arc = NULL;
88	s->s_lower = 0;
89	s->s_upper = 0;
90	s->s_accel = NULL;
91	s->s_accept = 0;
92	return s - d->d_state;
93}
94
95void
96addarc(d, from, to, lbl)
97	dfa *d;
98	int lbl;
99{
100	state *s;
101	arc *a;
102
103	assert(0 <= from && from < d->d_nstates);
104	assert(0 <= to && to < d->d_nstates);
105
106	s = &d->d_state[from];
107	RESIZE(s->s_arc, arc, s->s_narcs + 1);
108	if (s->s_arc == NULL)
109		fatal("no mem to resize arc list in addarc");
110	a = &s->s_arc[s->s_narcs++];
111	a->a_lbl = lbl;
112	a->a_arrow = to;
113}
114
115int
116addlabel(ll, type, str)
117	labellist *ll;
118	int type;
119	char *str;
120{
121	int i;
122	label *lb;
123
124	for (i = 0; i < ll->ll_nlabels; i++) {
125		if (ll->ll_label[i].lb_type == type &&
126			strcmp(ll->ll_label[i].lb_str, str) == 0)
127			return i;
128	}
129	RESIZE(ll->ll_label, label, ll->ll_nlabels + 1);
130	if (ll->ll_label == NULL)
131		fatal("no mem to resize labellist in addlabel");
132	lb = &ll->ll_label[ll->ll_nlabels++];
133	lb->lb_type = type;
134	lb->lb_str = str; /* XXX strdup(str) ??? */
135	return lb - ll->ll_label;
136}
137
138/* Same, but rather dies than adds */
139
140int
141findlabel(ll, type, str)
142	labellist *ll;
143	int type;
144	char *str;
145{
146	int i;
147
148	for (i = 0; i < ll->ll_nlabels; i++) {
149		if (ll->ll_label[i].lb_type == type /*&&
150			strcmp(ll->ll_label[i].lb_str, str) == 0*/)
151			return i;
152	}
153	fprintf(stderr, "Label %d/'%s' not found\n", type, str);
154	fatal("grammar.c:findlabel()");
155	/*NOTREACHED*/
156}
157
158/* Forward */
159static void translabel PROTO((grammar *, label *));
160
161void
162translatelabels(g)
163	grammar *g;
164{
165	int i;
166
167#ifdef DEBUG
168	printf("Translating labels ...\n");
169#endif
170	/* Don't translate EMPTY */
171	for (i = EMPTY+1; i < g->g_ll.ll_nlabels; i++)
172		translabel(g, &g->g_ll.ll_label[i]);
173}
174
175static void
176translabel(g, lb)
177	grammar *g;
178	label *lb;
179{
180	int i;
181
182	if (debugging)
183		printf("Translating label %s ...\n", labelrepr(lb));
184
185	if (lb->lb_type == NAME) {
186		for (i = 0; i < g->g_ndfas; i++) {
187			if (strcmp(lb->lb_str, g->g_dfa[i].d_name) == 0) {
188				if (debugging)
189					printf("Label %s is non-terminal %d.\n",
190						lb->lb_str,
191						g->g_dfa[i].d_type);
192				lb->lb_type = g->g_dfa[i].d_type;
193				lb->lb_str = NULL;
194				return;
195			}
196		}
197		for (i = 0; i < (int)N_TOKENS; i++) {
198			if (strcmp(lb->lb_str, tok_name[i]) == 0) {
199				if (debugging)
200					printf("Label %s is terminal %d.\n",
201						lb->lb_str, i);
202				lb->lb_type = i;
203				lb->lb_str = NULL;
204				return;
205			}
206		}
207		printf("Can't translate NAME label '%s'\n", lb->lb_str);
208		return;
209	}
210
211	if (lb->lb_type == STRING) {
212		if (isalpha(lb->lb_str[1])) {
213			char *p;
214			if (debugging)
215				printf("Label %s is a keyword\n", lb->lb_str);
216			lb->lb_type = NAME;
217			lb->lb_str++;
218			p = strchr(lb->lb_str, '\'');
219			if (p)
220				*p = '\0';
221		}
222		else if (lb->lb_str[2] == lb->lb_str[0]) {
223			int type = (int) tok_1char(lb->lb_str[1]);
224			if (type != OP) {
225				lb->lb_type = type;
226				lb->lb_str = NULL;
227			}
228			else
229				printf("Unknown OP label %s\n",
230					lb->lb_str);
231		}
232		else if (lb->lb_str[2] && lb->lb_str[3] == lb->lb_str[0]) {
233			int type = (int) tok_2char(lb->lb_str[1],
234						   lb->lb_str[2]);
235			if (type != OP) {
236				lb->lb_type = type;
237				lb->lb_str = NULL;
238			}
239			else
240				printf("Unknown OP label %s\n",
241					lb->lb_str);
242		}
243		else
244			printf("Can't translate STRING label %s\n",
245				lb->lb_str);
246	}
247	else
248		printf("Can't translate label '%s'\n", labelrepr(lb));
249}
250