Annotation of src/usr.bin/yacc/lr0.c, Revision 1.15
1.15 ! millert 1: /* $OpenBSD: lr0.c,v 1.14 2014/01/08 22:30:32 millert Exp $ */
1.2 deraadt 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.
1.7 millert 19: * 3. Neither the name of the University nor the names of its contributors
1.2 deraadt 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: */
1.1 deraadt 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:
1.6 millert 47: int get_state(int);
48: core *new_state(int);
1.4 pvalchev 49:
1.6 millert 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);
1.1 deraadt 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:
1.4 pvalchev 79: void
1.8 pvalchev 80: allocate_itemsets(void)
1.1 deraadt 81: {
1.5 mpech 82: short *itemp;
83: short *item_end;
84: int symbol;
85: int i;
86: int count;
87: int max;
88: short *symbol_count;
1.1 deraadt 89:
90: count = 0;
91: symbol_count = NEW2(nsyms, short);
92:
93: item_end = ritem + nitems;
94: for (itemp = ritem; itemp < item_end; itemp++)
95: {
96: symbol = *itemp;
97: if (symbol >= 0)
98: {
99: count++;
100: symbol_count[symbol]++;
101: }
102: }
103:
104: kernel_base = NEW2(nsyms, short *);
105: kernel_items = NEW2(count, short);
106:
107: count = 0;
108: max = 0;
109: for (i = 0; i < nsyms; i++)
110: {
111: kernel_base[i] = kernel_items + count;
112: count += symbol_count[i];
113: if (max < symbol_count[i])
114: max = symbol_count[i];
115: }
116:
117: shift_symbol = symbol_count;
118: kernel_end = NEW2(nsyms, short *);
119: }
120:
1.4 pvalchev 121: void
1.8 pvalchev 122: allocate_storage(void)
1.1 deraadt 123: {
124: allocate_itemsets();
125: shiftset = NEW2(nsyms, short);
126: redset = NEW2(nrules + 1, short);
127: state_set = NEW2(nitems, core *);
128: }
129:
1.4 pvalchev 130: void
1.8 pvalchev 131: append_states(void)
1.1 deraadt 132: {
1.5 mpech 133: int i;
134: int j;
135: int symbol;
1.1 deraadt 136:
137: #ifdef TRACE
138: fprintf(stderr, "Entering append_states()\n");
139: #endif
140: for (i = 1; i < nshifts; i++)
141: {
142: symbol = shift_symbol[i];
143: j = i;
144: while (j > 0 && shift_symbol[j - 1] > symbol)
145: {
146: shift_symbol[j] = shift_symbol[j - 1];
147: j--;
148: }
149: shift_symbol[j] = symbol;
150: }
151:
152: for (i = 0; i < nshifts; i++)
153: {
154: symbol = shift_symbol[i];
155: shiftset[i] = get_state(symbol);
156: }
157: }
158:
1.4 pvalchev 159: void
1.8 pvalchev 160: free_storage(void)
1.1 deraadt 161: {
1.13 millert 162: free(shift_symbol);
163: free(redset);
164: free(shiftset);
165: free(kernel_base);
166: free(kernel_end);
167: free(kernel_items);
168: free(state_set);
1.1 deraadt 169: }
170:
171:
1.4 pvalchev 172: void
1.8 pvalchev 173: generate_states(void)
1.1 deraadt 174: {
175: allocate_storage();
176: itemset = NEW2(nitems, short);
177: ruleset = NEW2(WORDSIZE(nrules), unsigned);
178: set_first_derives();
179: initialize_states();
180:
181: while (this_state)
182: {
183: closure(this_state->items, this_state->nitems);
184: save_reductions();
185: new_itemsets();
186: append_states();
187:
188: if (nshifts > 0)
189: save_shifts();
190:
191: this_state = this_state->next;
192: }
193:
194: finalize_closure();
195: free_storage();
196: }
197:
198:
199:
200: int
1.8 pvalchev 201: get_state(int symbol)
1.1 deraadt 202: {
1.5 mpech 203: int key;
204: short *isp1;
205: short *isp2;
206: short *iend;
207: core *sp;
208: int found;
209: int n;
1.1 deraadt 210:
211: #ifdef TRACE
212: fprintf(stderr, "Entering get_state(%d)\n", symbol);
213: #endif
214:
215: isp1 = kernel_base[symbol];
216: iend = kernel_end[symbol];
217: n = iend - isp1;
218:
219: key = *isp1;
220: assert(0 <= key && key < nitems);
221: sp = state_set[key];
222: if (sp)
223: {
224: found = 0;
225: while (!found)
226: {
227: if (sp->nitems == n)
228: {
229: found = 1;
230: isp1 = kernel_base[symbol];
231: isp2 = sp->items;
232:
233: while (found && isp1 < iend)
234: {
235: if (*isp1++ != *isp2++)
236: found = 0;
237: }
238: }
239:
240: if (!found)
241: {
242: if (sp->link)
243: {
244: sp = sp->link;
245: }
246: else
247: {
248: sp = sp->link = new_state(symbol);
249: found = 1;
250: }
251: }
252: }
253: }
254: else
255: {
256: state_set[key] = sp = new_state(symbol);
257: }
258:
259: return (sp->number);
260: }
261:
262:
1.4 pvalchev 263: void
1.8 pvalchev 264: initialize_states(void)
1.1 deraadt 265: {
1.5 mpech 266: int i;
267: short *start_derives;
268: core *p;
1.1 deraadt 269:
270: start_derives = derives[start_symbol];
271: for (i = 0; start_derives[i] >= 0; ++i)
272: continue;
273:
1.13 millert 274: p = (core *) malloc(sizeof(core) + i*sizeof(short));
1.1 deraadt 275: if (p == 0) no_space();
276:
277: p->next = 0;
278: p->link = 0;
279: p->number = 0;
280: p->accessing_symbol = 0;
281: p->nitems = i;
282:
283: for (i = 0; start_derives[i] >= 0; ++i)
284: p->items[i] = rrhs[start_derives[i]];
285:
286: first_state = last_state = this_state = p;
287: nstates = 1;
288: }
289:
1.4 pvalchev 290: void
1.8 pvalchev 291: new_itemsets(void)
1.1 deraadt 292: {
1.5 mpech 293: int i;
294: int shiftcount;
295: short *isp;
296: short *ksp;
297: int symbol;
1.1 deraadt 298:
1.12 nicm 299: memset(kernel_end, 0, nsyms * sizeof(short *));
1.1 deraadt 300:
301: shiftcount = 0;
302: isp = itemset;
303: while (isp < itemsetend)
304: {
305: i = *isp++;
306: symbol = ritem[i];
307: if (symbol > 0)
308: {
309: ksp = kernel_end[symbol];
310: if (!ksp)
311: {
312: shift_symbol[shiftcount++] = symbol;
313: ksp = kernel_base[symbol];
314: }
315:
316: *ksp++ = i + 1;
317: kernel_end[symbol] = ksp;
318: }
319: }
320:
321: nshifts = shiftcount;
322: }
323:
324:
325:
326: core *
1.8 pvalchev 327: new_state(int symbol)
1.1 deraadt 328: {
1.5 mpech 329: int n;
330: core *p;
331: short *isp1;
332: short *isp2;
333: short *iend;
1.1 deraadt 334:
335: #ifdef TRACE
336: fprintf(stderr, "Entering new_state(%d)\n", symbol);
337: #endif
338:
339: if (nstates >= MAXSHORT)
340: fatal("too many states");
341:
342: isp1 = kernel_base[symbol];
343: iend = kernel_end[symbol];
344: n = iend - isp1;
345:
1.14 millert 346: p = allocate(sizeof(core) + (n - 1) * sizeof(short));
1.1 deraadt 347: p->accessing_symbol = symbol;
348: p->number = nstates;
349: p->nitems = n;
350:
351: isp2 = p->items;
352: while (isp1 < iend)
353: *isp2++ = *isp1++;
354:
355: last_state->next = p;
356: last_state = p;
357:
358: nstates++;
359:
360: return (p);
361: }
362:
363:
1.4 pvalchev 364: void
1.8 pvalchev 365: save_shifts(void)
1.1 deraadt 366: {
1.5 mpech 367: shifts *p;
368: short *sp1;
369: short *sp2;
370: short *send;
1.1 deraadt 371:
1.14 millert 372: p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
1.1 deraadt 373:
374: p->number = this_state->number;
375: p->nshifts = nshifts;
376:
377: sp1 = shiftset;
378: sp2 = p->shift;
379: send = shiftset + nshifts;
380:
381: while (sp1 < send)
382: *sp2++ = *sp1++;
383:
384: if (last_shift)
385: {
386: last_shift->next = p;
387: last_shift = p;
388: }
389: else
390: {
391: first_shift = p;
392: last_shift = p;
393: }
394: }
395:
396:
1.4 pvalchev 397: void
1.8 pvalchev 398: save_reductions(void)
1.1 deraadt 399: {
1.5 mpech 400: short *isp;
401: short *rp1;
402: short *rp2;
403: int item;
404: int count;
405: reductions *p;
406: short *rend;
1.1 deraadt 407:
408: count = 0;
409: for (isp = itemset; isp < itemsetend; isp++)
410: {
411: item = ritem[*isp];
412: if (item < 0)
413: {
414: redset[count++] = -item;
415: }
416: }
417:
418: if (count)
419: {
1.14 millert 420: p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
1.1 deraadt 421:
422: p->number = this_state->number;
423: p->nreds = count;
424:
425: rp1 = redset;
426: rp2 = p->rules;
427: rend = rp1 + count;
428:
429: while (rp1 < rend)
430: *rp2++ = *rp1++;
431:
432: if (last_reduction)
433: {
434: last_reduction->next = p;
435: last_reduction = p;
436: }
437: else
438: {
439: first_reduction = p;
440: last_reduction = p;
441: }
442: }
443: }
444:
1.4 pvalchev 445: void
1.8 pvalchev 446: set_derives(void)
1.1 deraadt 447: {
1.5 mpech 448: int i, k;
449: int lhs;
450: short *rules;
1.1 deraadt 451:
452: derives = NEW2(nsyms, short *);
453: rules = NEW2(nvars + nrules, short);
454:
455: k = 0;
456: for (lhs = start_symbol; lhs < nsyms; lhs++)
457: {
458: derives[lhs] = rules + k;
459: for (i = 0; i < nrules; i++)
460: {
461: if (rlhs[i] == lhs)
462: {
463: rules[k] = i;
464: k++;
465: }
466: }
467: rules[k] = -1;
468: k++;
469: }
470:
471: #ifdef DEBUG
472: print_derives();
473: #endif
474: }
475:
1.4 pvalchev 476: void
1.8 pvalchev 477: free_derives(void)
1.1 deraadt 478: {
1.13 millert 479: free(derives[start_symbol]);
480: free(derives);
1.1 deraadt 481: }
482:
483: #ifdef DEBUG
1.4 pvalchev 484: void
1.8 pvalchev 485: print_derives(void)
1.1 deraadt 486: {
1.5 mpech 487: int i;
488: short *sp;
1.1 deraadt 489:
490: printf("\nDERIVES\n\n");
491:
492: for (i = start_symbol; i < nsyms; i++)
493: {
494: printf("%s derives ", symbol_name[i]);
495: for (sp = derives[i]; *sp >= 0; sp++)
496: {
497: printf(" %d", *sp);
498: }
499: putchar('\n');
500: }
501:
502: putchar('\n');
503: }
504: #endif
505:
1.4 pvalchev 506: void
1.8 pvalchev 507: set_nullable(void)
1.1 deraadt 508: {
1.5 mpech 509: int i, j;
510: int empty;
1.1 deraadt 511: int done;
512:
1.15 ! millert 513: nullable = calloc(1, nsyms);
1.1 deraadt 514: if (nullable == 0) no_space();
515:
516: done = 0;
517: while (!done)
518: {
519: done = 1;
520: for (i = 1; i < nitems; i++)
521: {
522: empty = 1;
523: while ((j = ritem[i]) >= 0)
524: {
525: if (!nullable[j])
526: empty = 0;
527: ++i;
528: }
529: if (empty)
530: {
531: j = rlhs[-j];
532: if (!nullable[j])
533: {
534: nullable[j] = 1;
535: done = 0;
536: }
537: }
538: }
539: }
540:
541: #ifdef DEBUG
542: for (i = 0; i < nsyms; i++)
543: {
544: if (nullable[i])
545: printf("%s is nullable\n", symbol_name[i]);
546: else
547: printf("%s is not nullable\n", symbol_name[i]);
548: }
549: #endif
550: }
551:
1.4 pvalchev 552: void
1.8 pvalchev 553: free_nullable(void)
1.1 deraadt 554: {
1.13 millert 555: free(nullable);
1.1 deraadt 556: }
557:
1.4 pvalchev 558: void
1.8 pvalchev 559: lr0(void)
1.1 deraadt 560: {
561: set_derives();
562: set_nullable();
563: generate_states();
564: }