1*8d3728c6Stedu /* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $ */
2f3bae140Sderaadt /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $ */
3f3bae140Sderaadt
4f3bae140Sderaadt /*
5f3bae140Sderaadt * Copyright (c) 1989 The Regents of the University of California.
6f3bae140Sderaadt * All rights reserved.
7f3bae140Sderaadt *
8f3bae140Sderaadt * This code is derived from software contributed to Berkeley by
9f3bae140Sderaadt * Robert Paul Corbett.
10f3bae140Sderaadt *
11f3bae140Sderaadt * Redistribution and use in source and binary forms, with or without
12f3bae140Sderaadt * modification, are permitted provided that the following conditions
13f3bae140Sderaadt * are met:
14f3bae140Sderaadt * 1. Redistributions of source code must retain the above copyright
15f3bae140Sderaadt * notice, this list of conditions and the following disclaimer.
16f3bae140Sderaadt * 2. Redistributions in binary form must reproduce the above copyright
17f3bae140Sderaadt * notice, this list of conditions and the following disclaimer in the
18f3bae140Sderaadt * documentation and/or other materials provided with the distribution.
19f75387cbSmillert * 3. Neither the name of the University nor the names of its contributors
20f3bae140Sderaadt * may be used to endorse or promote products derived from this software
21f3bae140Sderaadt * without specific prior written permission.
22f3bae140Sderaadt *
23f3bae140Sderaadt * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24f3bae140Sderaadt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25f3bae140Sderaadt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26f3bae140Sderaadt * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27f3bae140Sderaadt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28f3bae140Sderaadt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29f3bae140Sderaadt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30f3bae140Sderaadt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31f3bae140Sderaadt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32f3bae140Sderaadt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33f3bae140Sderaadt * SUCH DAMAGE.
34f3bae140Sderaadt */
35f3bae140Sderaadt
36df930be7Sderaadt #include "defs.h"
37df930be7Sderaadt
38df930be7Sderaadt extern short *itemset;
39df930be7Sderaadt extern short *itemsetend;
40df930be7Sderaadt extern unsigned *ruleset;
41df930be7Sderaadt
42df930be7Sderaadt int nstates;
43df930be7Sderaadt core *first_state;
44df930be7Sderaadt shifts *first_shift;
45df930be7Sderaadt reductions *first_reduction;
46df930be7Sderaadt
47591b5352Smillert short get_state(int);
48c72b5b24Smillert core *new_state(int);
491d699125Spvalchev
50c72b5b24Smillert void allocate_itemsets(void);
51c72b5b24Smillert void allocate_storage(void);
52c72b5b24Smillert void append_states(void);
53c72b5b24Smillert void free_storage(void);
54c72b5b24Smillert void generate_states(void);
55c72b5b24Smillert void initialize_states(void);
56c72b5b24Smillert void new_itemsets(void);
57c72b5b24Smillert void save_shifts(void);
58c72b5b24Smillert void save_reductions(void);
59c72b5b24Smillert void set_derives(void);
60c72b5b24Smillert void print_derives(void);
61c72b5b24Smillert void set_nullable(void);
62df930be7Sderaadt
63df930be7Sderaadt static core **state_set;
64df930be7Sderaadt static core *this_state;
65df930be7Sderaadt static core *last_state;
66df930be7Sderaadt static shifts *last_shift;
67df930be7Sderaadt static reductions *last_reduction;
68df930be7Sderaadt
69df930be7Sderaadt static int nshifts;
70df930be7Sderaadt static short *shift_symbol;
71df930be7Sderaadt
72df930be7Sderaadt static short *redset;
73df930be7Sderaadt static short *shiftset;
74df930be7Sderaadt
75df930be7Sderaadt static short **kernel_base;
76df930be7Sderaadt static short **kernel_end;
77df930be7Sderaadt static short *kernel_items;
78df930be7Sderaadt
791d699125Spvalchev void
allocate_itemsets(void)80d1e49392Spvalchev allocate_itemsets(void)
81df930be7Sderaadt {
82*8d3728c6Stedu short *itemp, *item_end;
83*8d3728c6Stedu int i, count, max, symbol;
84c0932ef1Smpech short *symbol_count;
85df930be7Sderaadt
86df930be7Sderaadt count = 0;
87df930be7Sderaadt symbol_count = NEW2(nsyms, short);
88df930be7Sderaadt
89df930be7Sderaadt item_end = ritem + nitems;
90bfda557dStedu for (itemp = ritem; itemp < item_end; itemp++) {
91df930be7Sderaadt symbol = *itemp;
92bfda557dStedu if (symbol >= 0) {
93df930be7Sderaadt count++;
94df930be7Sderaadt symbol_count[symbol]++;
95df930be7Sderaadt }
96df930be7Sderaadt }
97df930be7Sderaadt
98df930be7Sderaadt kernel_base = NEW2(nsyms, short *);
99df930be7Sderaadt kernel_items = NEW2(count, short);
100df930be7Sderaadt
101df930be7Sderaadt count = 0;
102df930be7Sderaadt max = 0;
103bfda557dStedu for (i = 0; i < nsyms; i++) {
104df930be7Sderaadt kernel_base[i] = kernel_items + count;
105df930be7Sderaadt count += symbol_count[i];
106df930be7Sderaadt if (max < symbol_count[i])
107df930be7Sderaadt max = symbol_count[i];
108df930be7Sderaadt }
109df930be7Sderaadt
110df930be7Sderaadt shift_symbol = symbol_count;
111df930be7Sderaadt kernel_end = NEW2(nsyms, short *);
112df930be7Sderaadt }
113df930be7Sderaadt
1141d699125Spvalchev void
allocate_storage(void)115d1e49392Spvalchev allocate_storage(void)
116df930be7Sderaadt {
117df930be7Sderaadt allocate_itemsets();
118df930be7Sderaadt shiftset = NEW2(nsyms, short);
119df930be7Sderaadt redset = NEW2(nrules + 1, short);
120df930be7Sderaadt state_set = NEW2(nitems, core *);
121df930be7Sderaadt }
122df930be7Sderaadt
1231d699125Spvalchev void
append_states(void)124d1e49392Spvalchev append_states(void)
125df930be7Sderaadt {
126*8d3728c6Stedu int i, j, symbol;
127df930be7Sderaadt
128df930be7Sderaadt #ifdef TRACE
129df930be7Sderaadt fprintf(stderr, "Entering append_states()\n");
130df930be7Sderaadt #endif
131bfda557dStedu for (i = 1; i < nshifts; i++) {
132df930be7Sderaadt symbol = shift_symbol[i];
133df930be7Sderaadt j = i;
134bfda557dStedu while (j > 0 && shift_symbol[j - 1] > symbol) {
135df930be7Sderaadt shift_symbol[j] = shift_symbol[j - 1];
136df930be7Sderaadt j--;
137df930be7Sderaadt }
138df930be7Sderaadt shift_symbol[j] = symbol;
139df930be7Sderaadt }
140df930be7Sderaadt
141bfda557dStedu for (i = 0; i < nshifts; i++) {
142df930be7Sderaadt symbol = shift_symbol[i];
143df930be7Sderaadt shiftset[i] = get_state(symbol);
144df930be7Sderaadt }
145df930be7Sderaadt }
146df930be7Sderaadt
1471d699125Spvalchev void
free_storage(void)148d1e49392Spvalchev free_storage(void)
149df930be7Sderaadt {
150ef356450Smillert free(shift_symbol);
151ef356450Smillert free(redset);
152ef356450Smillert free(shiftset);
153ef356450Smillert free(kernel_base);
154ef356450Smillert free(kernel_end);
155ef356450Smillert free(kernel_items);
156ef356450Smillert free(state_set);
157df930be7Sderaadt }
158df930be7Sderaadt
159df930be7Sderaadt
1601d699125Spvalchev void
generate_states(void)161d1e49392Spvalchev generate_states(void)
162df930be7Sderaadt {
163df930be7Sderaadt allocate_storage();
164df930be7Sderaadt itemset = NEW2(nitems, short);
165df930be7Sderaadt ruleset = NEW2(WORDSIZE(nrules), unsigned);
166df930be7Sderaadt set_first_derives();
167df930be7Sderaadt initialize_states();
168df930be7Sderaadt
169bfda557dStedu while (this_state) {
170df930be7Sderaadt closure(this_state->items, this_state->nitems);
171df930be7Sderaadt save_reductions();
172df930be7Sderaadt new_itemsets();
173df930be7Sderaadt append_states();
174df930be7Sderaadt
175df930be7Sderaadt if (nshifts > 0)
176df930be7Sderaadt save_shifts();
177df930be7Sderaadt
178df930be7Sderaadt this_state = this_state->next;
179df930be7Sderaadt }
180df930be7Sderaadt
181df930be7Sderaadt finalize_closure();
182df930be7Sderaadt free_storage();
183df930be7Sderaadt }
184df930be7Sderaadt
185df930be7Sderaadt
186df930be7Sderaadt
187591b5352Smillert short
get_state(int symbol)188d1e49392Spvalchev get_state(int symbol)
189df930be7Sderaadt {
190*8d3728c6Stedu int n, found, key;
191*8d3728c6Stedu short *isp1, *isp2, *iend;
192c0932ef1Smpech core *sp;
193df930be7Sderaadt
194df930be7Sderaadt #ifdef TRACE
195df930be7Sderaadt fprintf(stderr, "Entering get_state(%d)\n", symbol);
196df930be7Sderaadt #endif
197df930be7Sderaadt
198df930be7Sderaadt isp1 = kernel_base[symbol];
199df930be7Sderaadt iend = kernel_end[symbol];
200df930be7Sderaadt n = iend - isp1;
201df930be7Sderaadt
202df930be7Sderaadt key = *isp1;
203df930be7Sderaadt assert(0 <= key && key < nitems);
204df930be7Sderaadt sp = state_set[key];
205bfda557dStedu if (sp) {
206df930be7Sderaadt found = 0;
207bfda557dStedu while (!found) {
208bfda557dStedu if (sp->nitems == n) {
209df930be7Sderaadt found = 1;
210df930be7Sderaadt isp1 = kernel_base[symbol];
211df930be7Sderaadt isp2 = sp->items;
212df930be7Sderaadt
213bfda557dStedu while (found && isp1 < iend) {
214df930be7Sderaadt if (*isp1++ != *isp2++)
215df930be7Sderaadt found = 0;
216df930be7Sderaadt }
217df930be7Sderaadt }
218bfda557dStedu if (!found) {
219bfda557dStedu if (sp->link) {
220df930be7Sderaadt sp = sp->link;
221bfda557dStedu } else {
222df930be7Sderaadt sp = sp->link = new_state(symbol);
223df930be7Sderaadt found = 1;
224df930be7Sderaadt }
225df930be7Sderaadt }
226df930be7Sderaadt }
227bfda557dStedu } else {
228df930be7Sderaadt state_set[key] = sp = new_state(symbol);
229df930be7Sderaadt }
230df930be7Sderaadt
231df930be7Sderaadt return (sp->number);
232df930be7Sderaadt }
233df930be7Sderaadt
234df930be7Sderaadt
2351d699125Spvalchev void
initialize_states(void)236d1e49392Spvalchev initialize_states(void)
237df930be7Sderaadt {
238c0932ef1Smpech int i;
239c0932ef1Smpech short *start_derives;
240c0932ef1Smpech core *p;
241df930be7Sderaadt
242df930be7Sderaadt start_derives = derives[start_symbol];
243df930be7Sderaadt for (i = 0; start_derives[i] >= 0; ++i)
244df930be7Sderaadt continue;
245df930be7Sderaadt
246bfda557dStedu p = malloc(sizeof(core) + i * sizeof(short));
247bfda557dStedu if (p == NULL)
248bfda557dStedu no_space();
249df930be7Sderaadt
250df930be7Sderaadt p->next = 0;
251df930be7Sderaadt p->link = 0;
252df930be7Sderaadt p->number = 0;
253df930be7Sderaadt p->accessing_symbol = 0;
254df930be7Sderaadt p->nitems = i;
255df930be7Sderaadt
256df930be7Sderaadt for (i = 0; start_derives[i] >= 0; ++i)
257df930be7Sderaadt p->items[i] = rrhs[start_derives[i]];
258df930be7Sderaadt
259df930be7Sderaadt first_state = last_state = this_state = p;
260df930be7Sderaadt nstates = 1;
261df930be7Sderaadt }
262df930be7Sderaadt
2631d699125Spvalchev void
new_itemsets(void)264d1e49392Spvalchev new_itemsets(void)
265df930be7Sderaadt {
266*8d3728c6Stedu int i, shiftcount;
267*8d3728c6Stedu short *isp, *ksp;
268c0932ef1Smpech int symbol;
269df930be7Sderaadt
270fdd8157aSnicm memset(kernel_end, 0, nsyms * sizeof(short *));
271df930be7Sderaadt
272df930be7Sderaadt shiftcount = 0;
273df930be7Sderaadt isp = itemset;
274bfda557dStedu while (isp < itemsetend) {
275df930be7Sderaadt i = *isp++;
276df930be7Sderaadt symbol = ritem[i];
277bfda557dStedu if (symbol > 0) {
278df930be7Sderaadt ksp = kernel_end[symbol];
279bfda557dStedu if (!ksp) {
280df930be7Sderaadt shift_symbol[shiftcount++] = symbol;
281df930be7Sderaadt ksp = kernel_base[symbol];
282df930be7Sderaadt }
283df930be7Sderaadt *ksp++ = i + 1;
284df930be7Sderaadt kernel_end[symbol] = ksp;
285df930be7Sderaadt }
286df930be7Sderaadt }
287df930be7Sderaadt
288df930be7Sderaadt nshifts = shiftcount;
289df930be7Sderaadt }
290df930be7Sderaadt
291df930be7Sderaadt
292df930be7Sderaadt
293df930be7Sderaadt core *
new_state(int symbol)294d1e49392Spvalchev new_state(int symbol)
295df930be7Sderaadt {
296c0932ef1Smpech int n;
297c0932ef1Smpech core *p;
298*8d3728c6Stedu short *isp1, *isp2, *iend;
299df930be7Sderaadt
300df930be7Sderaadt #ifdef TRACE
301df930be7Sderaadt fprintf(stderr, "Entering new_state(%d)\n", symbol);
302df930be7Sderaadt #endif
303df930be7Sderaadt
304df930be7Sderaadt if (nstates >= MAXSHORT)
305df930be7Sderaadt fatal("too many states");
306df930be7Sderaadt
307df930be7Sderaadt isp1 = kernel_base[symbol];
308df930be7Sderaadt iend = kernel_end[symbol];
309df930be7Sderaadt n = iend - isp1;
310df930be7Sderaadt
31107d3058cSmillert p = allocate(sizeof(core) + (n - 1) * sizeof(short));
312df930be7Sderaadt p->accessing_symbol = symbol;
313df930be7Sderaadt p->number = nstates;
314df930be7Sderaadt p->nitems = n;
315df930be7Sderaadt
316df930be7Sderaadt isp2 = p->items;
317df930be7Sderaadt while (isp1 < iend)
318df930be7Sderaadt *isp2++ = *isp1++;
319df930be7Sderaadt
320df930be7Sderaadt last_state->next = p;
321df930be7Sderaadt last_state = p;
322df930be7Sderaadt
323df930be7Sderaadt nstates++;
324df930be7Sderaadt
325df930be7Sderaadt return (p);
326df930be7Sderaadt }
327df930be7Sderaadt
328df930be7Sderaadt
3291d699125Spvalchev void
save_shifts(void)330d1e49392Spvalchev save_shifts(void)
331df930be7Sderaadt {
332c0932ef1Smpech shifts *p;
333*8d3728c6Stedu short *sp1, *sp2, *send;
334df930be7Sderaadt
33507d3058cSmillert p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
336df930be7Sderaadt
337df930be7Sderaadt p->number = this_state->number;
338df930be7Sderaadt p->nshifts = nshifts;
339df930be7Sderaadt
340df930be7Sderaadt sp1 = shiftset;
341df930be7Sderaadt sp2 = p->shift;
342df930be7Sderaadt send = shiftset + nshifts;
343df930be7Sderaadt
344df930be7Sderaadt while (sp1 < send)
345df930be7Sderaadt *sp2++ = *sp1++;
346df930be7Sderaadt
347bfda557dStedu if (last_shift) {
348df930be7Sderaadt last_shift->next = p;
349df930be7Sderaadt last_shift = p;
350bfda557dStedu } else {
351df930be7Sderaadt first_shift = p;
352df930be7Sderaadt last_shift = p;
353df930be7Sderaadt }
354df930be7Sderaadt }
355df930be7Sderaadt
356df930be7Sderaadt
3571d699125Spvalchev void
save_reductions(void)358d1e49392Spvalchev save_reductions(void)
359df930be7Sderaadt {
360*8d3728c6Stedu short *isp, *rp1, *rp2;
361*8d3728c6Stedu int item, count;
362c0932ef1Smpech reductions *p;
363c0932ef1Smpech short *rend;
364df930be7Sderaadt
365df930be7Sderaadt count = 0;
366bfda557dStedu for (isp = itemset; isp < itemsetend; isp++) {
367df930be7Sderaadt item = ritem[*isp];
368bfda557dStedu if (item < 0) {
369df930be7Sderaadt redset[count++] = -item;
370df930be7Sderaadt }
371df930be7Sderaadt }
372df930be7Sderaadt
373bfda557dStedu if (count) {
37407d3058cSmillert p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
375df930be7Sderaadt
376df930be7Sderaadt p->number = this_state->number;
377df930be7Sderaadt p->nreds = count;
378df930be7Sderaadt
379df930be7Sderaadt rp1 = redset;
380df930be7Sderaadt rp2 = p->rules;
381df930be7Sderaadt rend = rp1 + count;
382df930be7Sderaadt
383df930be7Sderaadt while (rp1 < rend)
384df930be7Sderaadt *rp2++ = *rp1++;
385df930be7Sderaadt
386bfda557dStedu if (last_reduction) {
387df930be7Sderaadt last_reduction->next = p;
388df930be7Sderaadt last_reduction = p;
389bfda557dStedu } else {
390df930be7Sderaadt first_reduction = p;
391df930be7Sderaadt last_reduction = p;
392df930be7Sderaadt }
393df930be7Sderaadt }
394df930be7Sderaadt }
395df930be7Sderaadt
3961d699125Spvalchev void
set_derives(void)397d1e49392Spvalchev set_derives(void)
398df930be7Sderaadt {
399*8d3728c6Stedu int i, k, lhs;
400c0932ef1Smpech short *rules;
401df930be7Sderaadt
402df930be7Sderaadt derives = NEW2(nsyms, short *);
403df930be7Sderaadt rules = NEW2(nvars + nrules, short);
404df930be7Sderaadt
405df930be7Sderaadt k = 0;
406bfda557dStedu for (lhs = start_symbol; lhs < nsyms; lhs++) {
407df930be7Sderaadt derives[lhs] = rules + k;
408bfda557dStedu for (i = 0; i < nrules; i++) {
409bfda557dStedu if (rlhs[i] == lhs) {
410df930be7Sderaadt rules[k] = i;
411df930be7Sderaadt k++;
412df930be7Sderaadt }
413df930be7Sderaadt }
414df930be7Sderaadt rules[k] = -1;
415df930be7Sderaadt k++;
416df930be7Sderaadt }
417df930be7Sderaadt
418df930be7Sderaadt #ifdef DEBUG
419df930be7Sderaadt print_derives();
420df930be7Sderaadt #endif
421df930be7Sderaadt }
422df930be7Sderaadt
4231d699125Spvalchev void
free_derives(void)424d1e49392Spvalchev free_derives(void)
425df930be7Sderaadt {
426ef356450Smillert free(derives[start_symbol]);
427ef356450Smillert free(derives);
428df930be7Sderaadt }
429df930be7Sderaadt
430df930be7Sderaadt #ifdef DEBUG
4311d699125Spvalchev void
print_derives(void)432d1e49392Spvalchev print_derives(void)
433df930be7Sderaadt {
434c0932ef1Smpech int i;
435c0932ef1Smpech short *sp;
436df930be7Sderaadt
437df930be7Sderaadt printf("\nDERIVES\n\n");
438df930be7Sderaadt
439bfda557dStedu for (i = start_symbol; i < nsyms; i++) {
440df930be7Sderaadt printf("%s derives ", symbol_name[i]);
441bfda557dStedu for (sp = derives[i]; *sp >= 0; sp++) {
442df930be7Sderaadt printf(" %d", *sp);
443df930be7Sderaadt }
444df930be7Sderaadt putchar('\n');
445df930be7Sderaadt }
446df930be7Sderaadt
447df930be7Sderaadt putchar('\n');
448df930be7Sderaadt }
449df930be7Sderaadt #endif
450df930be7Sderaadt
4511d699125Spvalchev void
set_nullable(void)452d1e49392Spvalchev set_nullable(void)
453df930be7Sderaadt {
454c0932ef1Smpech int i, j;
455c0932ef1Smpech int empty;
456df930be7Sderaadt int done;
457df930be7Sderaadt
458f6169c9eSmillert nullable = calloc(1, nsyms);
459bfda557dStedu if (nullable == NULL)
460bfda557dStedu no_space();
461df930be7Sderaadt
462df930be7Sderaadt done = 0;
463bfda557dStedu while (!done) {
464df930be7Sderaadt done = 1;
465bfda557dStedu for (i = 1; i < nitems; i++) {
466df930be7Sderaadt empty = 1;
467bfda557dStedu while ((j = ritem[i]) >= 0) {
468df930be7Sderaadt if (!nullable[j])
469df930be7Sderaadt empty = 0;
470df930be7Sderaadt ++i;
471df930be7Sderaadt }
472bfda557dStedu if (empty) {
473df930be7Sderaadt j = rlhs[-j];
474bfda557dStedu if (!nullable[j]) {
475df930be7Sderaadt nullable[j] = 1;
476df930be7Sderaadt done = 0;
477df930be7Sderaadt }
478df930be7Sderaadt }
479df930be7Sderaadt }
480df930be7Sderaadt }
481df930be7Sderaadt
482df930be7Sderaadt #ifdef DEBUG
483bfda557dStedu for (i = 0; i < nsyms; i++) {
484df930be7Sderaadt if (nullable[i])
485df930be7Sderaadt printf("%s is nullable\n", symbol_name[i]);
486df930be7Sderaadt else
487df930be7Sderaadt printf("%s is not nullable\n", symbol_name[i]);
488df930be7Sderaadt }
489df930be7Sderaadt #endif
490df930be7Sderaadt }
491df930be7Sderaadt
4921d699125Spvalchev void
free_nullable(void)493d1e49392Spvalchev free_nullable(void)
494df930be7Sderaadt {
495ef356450Smillert free(nullable);
496df930be7Sderaadt }
497df930be7Sderaadt
4981d699125Spvalchev void
lr0(void)499d1e49392Spvalchev lr0(void)
500df930be7Sderaadt {
501df930be7Sderaadt set_derives();
502df930be7Sderaadt set_nullable();
503df930be7Sderaadt generate_states();
504df930be7Sderaadt }
505