GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/yacc/lr0.c Lines: 215 218 98.6 %
Date: 2016-12-06 Branches: 83 88 94.3 %

Line Branch Exec Source
1
/* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $	 */
2
/* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $	 */
3
4
/*
5
 * Copyright (c) 1989 The Regents of the University of California.
6
 * All rights reserved.
7
 *
8
 * This code is derived from software contributed to Berkeley by
9
 * Robert Paul Corbett.
10
 *
11
 * Redistribution and use in source and binary forms, with or without
12
 * modification, are permitted provided that the following conditions
13
 * are met:
14
 * 1. Redistributions of source code must retain the above copyright
15
 *    notice, this list of conditions and the following disclaimer.
16
 * 2. Redistributions in binary form must reproduce the above copyright
17
 *    notice, this list of conditions and the following disclaimer in the
18
 *    documentation and/or other materials provided with the distribution.
19
 * 3. Neither the name of the University nor the names of its contributors
20
 *    may be used to endorse or promote products derived from this software
21
 *    without specific prior written permission.
22
 *
23
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33
 * SUCH DAMAGE.
34
 */
35
36
#include "defs.h"
37
38
extern short *itemset;
39
extern short *itemsetend;
40
extern unsigned *ruleset;
41
42
int nstates;
43
core *first_state;
44
shifts *first_shift;
45
reductions *first_reduction;
46
47
short get_state(int);
48
core *new_state(int);
49
50
void allocate_itemsets(void);
51
void allocate_storage(void);
52
void append_states(void);
53
void free_storage(void);
54
void generate_states(void);
55
void initialize_states(void);
56
void new_itemsets(void);
57
void save_shifts(void);
58
void save_reductions(void);
59
void set_derives(void);
60
void print_derives(void);
61
void set_nullable(void);
62
63
static core **state_set;
64
static core *this_state;
65
static core *last_state;
66
static shifts *last_shift;
67
static reductions *last_reduction;
68
69
static int nshifts;
70
static short *shift_symbol;
71
72
static short *redset;
73
static short *shiftset;
74
75
static short **kernel_base;
76
static short **kernel_end;
77
static short *kernel_items;
78
79
void
80
allocate_itemsets(void)
81
21
{
82
	short *itemp, *item_end;
83
	int i, count, max, symbol;
84
	short *symbol_count;
85
86
21
	count = 0;
87
21
	symbol_count = NEW2(nsyms, short);
88
89
21
	item_end = ritem + nitems;
90
6928
	for (itemp = ritem; itemp < item_end; itemp++) {
91
6907
		symbol = *itemp;
92
6907
		if (symbol >= 0) {
93
4623
			count++;
94
4623
			symbol_count[symbol]++;
95
		}
96
	}
97
98
21
	kernel_base = NEW2(nsyms, short *);
99
21
	kernel_items = NEW2(count, short);
100
101
21
	count = 0;
102
21
	max = 0;
103
2083
	for (i = 0; i < nsyms; i++) {
104
2062
		kernel_base[i] = kernel_items + count;
105
2062
		count += symbol_count[i];
106
2062
		if (max < symbol_count[i])
107
84
			max = symbol_count[i];
108
	}
109
110
21
	shift_symbol = symbol_count;
111
21
	kernel_end = NEW2(nsyms, short *);
112
21
}
113
114
void
115
allocate_storage(void)
116
21
{
117
21
	allocate_itemsets();
118
21
	shiftset = NEW2(nsyms, short);
119
21
	redset = NEW2(nrules + 1, short);
120
21
	state_set = NEW2(nitems, core *);
121
21
}
122
123
void
124
append_states(void)
125
4002
{
126
	int i, j, symbol;
127
128
#ifdef	TRACE
129
	fprintf(stderr, "Entering append_states()\n");
130
#endif
131
8344
	for (i = 1; i < nshifts; i++) {
132
4342
		symbol = shift_symbol[i];
133
4342
		j = i;
134

23530
		while (j > 0 && shift_symbol[j - 1] > symbol) {
135
14846
			shift_symbol[j] = shift_symbol[j - 1];
136
14846
			j--;
137
		}
138
4342
		shift_symbol[j] = symbol;
139
	}
140
141
10441
	for (i = 0; i < nshifts; i++) {
142
6439
		symbol = shift_symbol[i];
143
6439
		shiftset[i] = get_state(symbol);
144
	}
145
4002
}
146
147
void
148
free_storage(void)
149
21
{
150
21
	free(shift_symbol);
151
21
	free(redset);
152
21
	free(shiftset);
153
21
	free(kernel_base);
154
21
	free(kernel_end);
155
21
	free(kernel_items);
156
21
	free(state_set);
157
21
}
158
159
160
void
161
generate_states(void)
162
21
{
163
21
	allocate_storage();
164
21
	itemset = NEW2(nitems, short);
165
21
	ruleset = NEW2(WORDSIZE(nrules), unsigned);
166
21
	set_first_derives();
167
21
	initialize_states();
168
169
4044
	while (this_state) {
170
4002
		closure(this_state->items, this_state->nitems);
171
4002
		save_reductions();
172
4002
		new_itemsets();
173
4002
		append_states();
174
175
4002
		if (nshifts > 0)
176
2097
			save_shifts();
177
178
4002
		this_state = this_state->next;
179
	}
180
181
21
	finalize_closure();
182
21
	free_storage();
183
21
}
184
185
186
187
short
188
get_state(int symbol)
189
6439
{
190
	int n, found, key;
191
	short *isp1, *isp2, *iend;
192
	core *sp;
193
194
#ifdef	TRACE
195
	fprintf(stderr, "Entering get_state(%d)\n", symbol);
196
#endif
197
198
6439
	isp1 = kernel_base[symbol];
199
6439
	iend = kernel_end[symbol];
200
6439
	n = iend - isp1;
201
202
6439
	key = *isp1;
203

6439
	assert(0 <= key && key < nitems);
204
6439
	sp = state_set[key];
205
6439
	if (sp) {
206
2635
		found = 0;
207
19187
		while (!found) {
208
13917
			if (sp->nitems == n) {
209
8319
				found = 1;
210
8319
				isp1 = kernel_base[symbol];
211
8319
				isp2 = sp->items;
212
213
31416
				while (found && isp1 < iend) {
214
14778
					if (*isp1++ != *isp2++)
215
5861
						found = 0;
216
				}
217
			}
218
13917
			if (!found) {
219
11459
				if (sp->link) {
220
11282
					sp = sp->link;
221
				} else {
222
177
					sp = sp->link = new_state(symbol);
223
177
					found = 1;
224
				}
225
			}
226
		}
227
	} else {
228
3804
		state_set[key] = sp = new_state(symbol);
229
	}
230
231
6439
	return (sp->number);
232
}
233
234
235
void
236
initialize_states(void)
237
21
{
238
	int i;
239
	short *start_derives;
240
	core *p;
241
242
21
	start_derives = derives[start_symbol];
243
21
	for (i = 0; start_derives[i] >= 0; ++i)
244
		continue;
245
246
21
	p = malloc(sizeof(core) + i * sizeof(short));
247
21
	if (p == NULL)
248
		no_space();
249
250
21
	p->next = 0;
251
21
	p->link = 0;
252
21
	p->number = 0;
253
21
	p->accessing_symbol = 0;
254
21
	p->nitems = i;
255
256
42
	for (i = 0; start_derives[i] >= 0; ++i)
257
21
		p->items[i] = rrhs[start_derives[i]];
258
259
21
	first_state = last_state = this_state = p;
260
21
	nstates = 1;
261
21
}
262
263
void
264
new_itemsets(void)
265
4002
{
266
	int i, shiftcount;
267
	short *isp, *ksp;
268
	int symbol;
269
270
4002
	memset(kernel_end, 0, nsyms * sizeof(short *));
271
272
4002
	shiftcount = 0;
273
4002
	isp = itemset;
274
18247
	while (isp < itemsetend) {
275
10243
		i = *isp++;
276
10243
		symbol = ritem[i];
277
10243
		if (symbol > 0) {
278
7777
			ksp = kernel_end[symbol];
279
7777
			if (!ksp) {
280
6439
				shift_symbol[shiftcount++] = symbol;
281
6439
				ksp = kernel_base[symbol];
282
			}
283
7777
			*ksp++ = i + 1;
284
7777
			kernel_end[symbol] = ksp;
285
		}
286
	}
287
288
4002
	nshifts = shiftcount;
289
4002
}
290
291
292
293
core *
294
new_state(int symbol)
295
3981
{
296
	int n;
297
	core *p;
298
	short *isp1, *isp2, *iend;
299
300
#ifdef	TRACE
301
	fprintf(stderr, "Entering new_state(%d)\n", symbol);
302
#endif
303
304
3981
	if (nstates >= MAXSHORT)
305
		fatal("too many states");
306
307
3981
	isp1 = kernel_base[symbol];
308
3981
	iend = kernel_end[symbol];
309
3981
	n = iend - isp1;
310
311
3981
	p = allocate(sizeof(core) + (n - 1) * sizeof(short));
312
3981
	p->accessing_symbol = symbol;
313
3981
	p->number = nstates;
314
3981
	p->nitems = n;
315
316
3981
	isp2 = p->items;
317
12795
	while (isp1 < iend)
318
4833
		*isp2++ = *isp1++;
319
320
3981
	last_state->next = p;
321
3981
	last_state = p;
322
323
3981
	nstates++;
324
325
3981
	return (p);
326
}
327
328
329
void
330
save_shifts(void)
331
2097
{
332
	shifts *p;
333
	short *sp1, *sp2, *send;
334
335
2097
	p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
336
337
2097
	p->number = this_state->number;
338
2097
	p->nshifts = nshifts;
339
340
2097
	sp1 = shiftset;
341
2097
	sp2 = p->shift;
342
2097
	send = shiftset + nshifts;
343
344
10633
	while (sp1 < send)
345
6439
		*sp2++ = *sp1++;
346
347
2097
	if (last_shift) {
348
2076
		last_shift->next = p;
349
2076
		last_shift = p;
350
	} else {
351
21
		first_shift = p;
352
21
		last_shift = p;
353
	}
354
2097
}
355
356
357
void
358
save_reductions(void)
359
4002
{
360
	short *isp, *rp1, *rp2;
361
	int item, count;
362
	reductions *p;
363
	short *rend;
364
365
4002
	count = 0;
366
14245
	for (isp = itemset; isp < itemsetend; isp++) {
367
10243
		item = ritem[*isp];
368
10243
		if (item < 0) {
369
2445
			redset[count++] = -item;
370
		}
371
	}
372
373
4002
	if (count) {
374
2419
		p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
375
376
2419
		p->number = this_state->number;
377
2419
		p->nreds = count;
378
379
2419
		rp1 = redset;
380
2419
		rp2 = p->rules;
381
2419
		rend = rp1 + count;
382
383
7283
		while (rp1 < rend)
384
2445
			*rp2++ = *rp1++;
385
386
2419
		if (last_reduction) {
387
2398
			last_reduction->next = p;
388
2398
			last_reduction = p;
389
		} else {
390
21
			first_reduction = p;
391
21
			last_reduction = p;
392
		}
393
	}
394
4002
}
395
396
void
397
set_derives(void)
398
21
{
399
	int i, k, lhs;
400
	short *rules;
401
402
21
	derives = NEW2(nsyms, short *);
403
21
	rules = NEW2(nvars + nrules, short);
404
405
21
	k = 0;
406
908
	for (lhs = start_symbol; lhs < nsyms; lhs++) {
407
887
		derives[lhs] = rules + k;
408
133591
		for (i = 0; i < nrules; i++) {
409
132704
			if (rlhs[i] == lhs) {
410
2263
				rules[k] = i;
411
2263
				k++;
412
			}
413
		}
414
887
		rules[k] = -1;
415
887
		k++;
416
	}
417
418
#ifdef	DEBUG
419
	print_derives();
420
#endif
421
21
}
422
423
void
424
free_derives(void)
425
21
{
426
21
	free(derives[start_symbol]);
427
21
	free(derives);
428
21
}
429
430
#ifdef	DEBUG
431
void
432
print_derives(void)
433
{
434
	int i;
435
	short *sp;
436
437
	printf("\nDERIVES\n\n");
438
439
	for (i = start_symbol; i < nsyms; i++) {
440
		printf("%s derives ", symbol_name[i]);
441
		for (sp = derives[i]; *sp >= 0; sp++) {
442
			printf("  %d", *sp);
443
		}
444
		putchar('\n');
445
	}
446
447
	putchar('\n');
448
}
449
#endif
450
451
void
452
set_nullable(void)
453
21
{
454
	int i, j;
455
	int empty;
456
	int done;
457
458
21
	nullable = calloc(1, nsyms);
459
21
	if (nullable == NULL)
460
		no_space();
461
462
21
	done = 0;
463
86
	while (!done) {
464
44
		done = 1;
465
4819
		for (i = 1; i < nitems; i++) {
466
4775
			empty = 1;
467
19262
			while ((j = ritem[i]) >= 0) {
468
9712
				if (!nullable[j])
469
8758
					empty = 0;
470
9712
				++i;
471
			}
472
4775
			if (empty) {
473
511
				j = rlhs[-j];
474
511
				if (!nullable[j]) {
475
236
					nullable[j] = 1;
476
236
					done = 0;
477
				}
478
			}
479
		}
480
	}
481
482
#ifdef DEBUG
483
	for (i = 0; i < nsyms; i++) {
484
		if (nullable[i])
485
			printf("%s is nullable\n", symbol_name[i]);
486
		else
487
			printf("%s is not nullable\n", symbol_name[i]);
488
	}
489
#endif
490
21
}
491
492
void
493
free_nullable(void)
494
21
{
495
21
	free(nullable);
496
21
}
497
498
void
499
lr0(void)
500
21
{
501
21
	set_derives();
502
21
	set_nullable();
503
21
	generate_states();
504
21
}