![[BACK]](/icons/back.gif){kind=icon}
Return to lr0.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / yacc|
Return to lr0.c CVS log | Up to [local] / src / usr.bin / yacc |
1.9 ! deraadt 1: /* $OpenBSD: lr0.c,v 1.8 2003/06/19 16:34:53 pvalchev 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 show_cores(void);
58: void show_ritems(void);
59: void show_rrhs(void);
60: void show_shifts(void);
61: void save_shifts(void);
62: void save_reductions(void);
63: void set_derives(void);
64: void print_derives(void);
65: void set_nullable(void);
66: void free_derives(void);
67: void free_nullable(void);
1.1 deraadt 68:
69: static core **state_set;
70: static core *this_state;
71: static core *last_state;
72: static shifts *last_shift;
73: static reductions *last_reduction;
74:
75: static int nshifts;
76: static short *shift_symbol;
77:
78: static short *redset;
79: static short *shiftset;
80:
81: static short **kernel_base;
82: static short **kernel_end;
83: static short *kernel_items;
84:
1.4 pvalchev 85: void
1.8 pvalchev 86: allocate_itemsets(void)
1.1 deraadt 87: {
1.5 mpech 88: short *itemp;
89: short *item_end;
90: int symbol;
91: int i;
92: int count;
93: int max;
94: short *symbol_count;
1.1 deraadt 95:
96: count = 0;
97: symbol_count = NEW2(nsyms, short);
98:
99: item_end = ritem + nitems;
100: for (itemp = ritem; itemp < item_end; itemp++)
101: {
102: symbol = *itemp;
103: if (symbol >= 0)
104: {
105: count++;
106: symbol_count[symbol]++;
107: }
108: }
109:
110: kernel_base = NEW2(nsyms, short *);
111: kernel_items = NEW2(count, short);
112:
113: count = 0;
114: max = 0;
115: for (i = 0; i < nsyms; i++)
116: {
117: kernel_base[i] = kernel_items + count;
118: count += symbol_count[i];
119: if (max < symbol_count[i])
120: max = symbol_count[i];
121: }
122:
123: shift_symbol = symbol_count;
124: kernel_end = NEW2(nsyms, short *);
125: }
126:
1.4 pvalchev 127: void
1.8 pvalchev 128: allocate_storage(void)
1.1 deraadt 129: {
130: allocate_itemsets();
131: shiftset = NEW2(nsyms, short);
132: redset = NEW2(nrules + 1, short);
133: state_set = NEW2(nitems, core *);
134: }
135:
1.4 pvalchev 136: void
1.8 pvalchev 137: append_states(void)
1.1 deraadt 138: {
1.5 mpech 139: int i;
140: int j;
141: int symbol;
1.1 deraadt 142:
143: #ifdef TRACE
144: fprintf(stderr, "Entering append_states()\n");
145: #endif
146: for (i = 1; i < nshifts; i++)
147: {
148: symbol = shift_symbol[i];
149: j = i;
150: while (j > 0 && shift_symbol[j - 1] > symbol)
151: {
152: shift_symbol[j] = shift_symbol[j - 1];
153: j--;
154: }
155: shift_symbol[j] = symbol;
156: }
157:
158: for (i = 0; i < nshifts; i++)
159: {
160: symbol = shift_symbol[i];
161: shiftset[i] = get_state(symbol);
162: }
163: }
164:
1.4 pvalchev 165: void
1.8 pvalchev 166: free_storage(void)
1.1 deraadt 167: {
168: FREE(shift_symbol);
169: FREE(redset);
170: FREE(shiftset);
171: FREE(kernel_base);
172: FREE(kernel_end);
173: FREE(kernel_items);
174: FREE(state_set);
175: }
176:
177:
1.4 pvalchev 178: void
1.8 pvalchev 179: generate_states(void)
1.1 deraadt 180: {
181: allocate_storage();
182: itemset = NEW2(nitems, short);
183: ruleset = NEW2(WORDSIZE(nrules), unsigned);
184: set_first_derives();
185: initialize_states();
186:
187: while (this_state)
188: {
189: closure(this_state->items, this_state->nitems);
190: save_reductions();
191: new_itemsets();
192: append_states();
193:
194: if (nshifts > 0)
195: save_shifts();
196:
197: this_state = this_state->next;
198: }
199:
200: finalize_closure();
201: free_storage();
202: }
203:
204:
205:
206: int
1.8 pvalchev 207: get_state(int symbol)
1.1 deraadt 208: {
1.5 mpech 209: int key;
210: short *isp1;
211: short *isp2;
212: short *iend;
213: core *sp;
214: int found;
215: int n;
1.1 deraadt 216:
217: #ifdef TRACE
218: fprintf(stderr, "Entering get_state(%d)\n", symbol);
219: #endif
220:
221: isp1 = kernel_base[symbol];
222: iend = kernel_end[symbol];
223: n = iend - isp1;
224:
225: key = *isp1;
226: assert(0 <= key && key < nitems);
227: sp = state_set[key];
228: if (sp)
229: {
230: found = 0;
231: while (!found)
232: {
233: if (sp->nitems == n)
234: {
235: found = 1;
236: isp1 = kernel_base[symbol];
237: isp2 = sp->items;
238:
239: while (found && isp1 < iend)
240: {
241: if (*isp1++ != *isp2++)
242: found = 0;
243: }
244: }
245:
246: if (!found)
247: {
248: if (sp->link)
249: {
250: sp = sp->link;
251: }
252: else
253: {
254: sp = sp->link = new_state(symbol);
255: found = 1;
256: }
257: }
258: }
259: }
260: else
261: {
262: state_set[key] = sp = new_state(symbol);
263: }
264:
265: return (sp->number);
266: }
267:
268:
1.4 pvalchev 269: void
1.8 pvalchev 270: initialize_states(void)
1.1 deraadt 271: {
1.5 mpech 272: int i;
273: short *start_derives;
274: core *p;
1.1 deraadt 275:
276: start_derives = derives[start_symbol];
277: for (i = 0; start_derives[i] >= 0; ++i)
278: continue;
279:
280: p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
281: if (p == 0) no_space();
282:
283: p->next = 0;
284: p->link = 0;
285: p->number = 0;
286: p->accessing_symbol = 0;
287: p->nitems = i;
288:
289: for (i = 0; start_derives[i] >= 0; ++i)
290: p->items[i] = rrhs[start_derives[i]];
291:
292: first_state = last_state = this_state = p;
293: nstates = 1;
294: }
295:
1.4 pvalchev 296: void
1.8 pvalchev 297: new_itemsets(void)
1.1 deraadt 298: {
1.5 mpech 299: int i;
300: int shiftcount;
301: short *isp;
302: short *ksp;
303: int symbol;
1.1 deraadt 304:
305: for (i = 0; i < nsyms; i++)
306: kernel_end[i] = 0;
307:
308: shiftcount = 0;
309: isp = itemset;
310: while (isp < itemsetend)
311: {
312: i = *isp++;
313: symbol = ritem[i];
314: if (symbol > 0)
315: {
316: ksp = kernel_end[symbol];
317: if (!ksp)
318: {
319: shift_symbol[shiftcount++] = symbol;
320: ksp = kernel_base[symbol];
321: }
322:
323: *ksp++ = i + 1;
324: kernel_end[symbol] = ksp;
325: }
326: }
327:
328: nshifts = shiftcount;
329: }
330:
331:
332:
333: core *
1.8 pvalchev 334: new_state(int symbol)
1.1 deraadt 335: {
1.5 mpech 336: int n;
337: core *p;
338: short *isp1;
339: short *isp2;
340: short *iend;
1.1 deraadt 341:
342: #ifdef TRACE
343: fprintf(stderr, "Entering new_state(%d)\n", symbol);
344: #endif
345:
346: if (nstates >= MAXSHORT)
347: fatal("too many states");
348:
349: isp1 = kernel_base[symbol];
350: iend = kernel_end[symbol];
351: n = iend - isp1;
352:
353: p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
354: p->accessing_symbol = symbol;
355: p->number = nstates;
356: p->nitems = n;
357:
358: isp2 = p->items;
359: while (isp1 < iend)
360: *isp2++ = *isp1++;
361:
362: last_state->next = p;
363: last_state = p;
364:
365: nstates++;
366:
367: return (p);
368: }
369:
370:
371: /* show_cores is used for debugging */
372:
1.4 pvalchev 373: void
1.8 pvalchev 374: show_cores(void)
1.1 deraadt 375: {
376: core *p;
377: int i, j, k, n;
378: int itemno;
379:
380: k = 0;
381: for (p = first_state; p; ++k, p = p->next)
382: {
383: if (k) printf("\n");
384: printf("state %d, number = %d, accessing symbol = %s\n",
385: k, p->number, symbol_name[p->accessing_symbol]);
386: n = p->nitems;
387: for (i = 0; i < n; ++i)
388: {
389: itemno = p->items[i];
390: printf("%4d ", itemno);
391: j = itemno;
392: while (ritem[j] >= 0) ++j;
393: printf("%s :", symbol_name[rlhs[-ritem[j]]]);
394: j = rrhs[-ritem[j]];
395: while (j < itemno)
396: printf(" %s", symbol_name[ritem[j++]]);
397: printf(" .");
398: while (ritem[j] >= 0)
399: printf(" %s", symbol_name[ritem[j++]]);
400: printf("\n");
401: fflush(stdout);
402: }
403: }
404: }
405:
406:
407: /* show_ritems is used for debugging */
408:
1.4 pvalchev 409: void
1.8 pvalchev 410: show_ritems(void)
1.1 deraadt 411: {
412: int i;
413:
414: for (i = 0; i < nitems; ++i)
415: printf("ritem[%d] = %d\n", i, ritem[i]);
416: }
417:
418:
419: /* show_rrhs is used for debugging */
1.4 pvalchev 420:
421: void
1.8 pvalchev 422: show_rrhs(void)
1.1 deraadt 423: {
424: int i;
425:
426: for (i = 0; i < nrules; ++i)
427: printf("rrhs[%d] = %d\n", i, rrhs[i]);
428: }
429:
430:
431: /* show_shifts is used for debugging */
432:
1.4 pvalchev 433: void
1.8 pvalchev 434: show_shifts(void)
1.1 deraadt 435: {
436: shifts *p;
437: int i, j, k;
438:
439: k = 0;
440: for (p = first_shift; p; ++k, p = p->next)
441: {
442: if (k) printf("\n");
443: printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
444: p->nshifts);
445: j = p->nshifts;
446: for (i = 0; i < j; ++i)
447: printf("\t%d\n", p->shift[i]);
448: }
449: }
450:
1.4 pvalchev 451: void
1.8 pvalchev 452: save_shifts(void)
1.1 deraadt 453: {
1.5 mpech 454: shifts *p;
455: short *sp1;
456: short *sp2;
457: short *send;
1.1 deraadt 458:
459: p = (shifts *) allocate((unsigned) (sizeof(shifts) +
460: (nshifts - 1) * sizeof(short)));
461:
462: p->number = this_state->number;
463: p->nshifts = nshifts;
464:
465: sp1 = shiftset;
466: sp2 = p->shift;
467: send = shiftset + nshifts;
468:
469: while (sp1 < send)
470: *sp2++ = *sp1++;
471:
472: if (last_shift)
473: {
474: last_shift->next = p;
475: last_shift = p;
476: }
477: else
478: {
479: first_shift = p;
480: last_shift = p;
481: }
482: }
483:
484:
1.4 pvalchev 485: void
1.8 pvalchev 486: save_reductions(void)
1.1 deraadt 487: {
1.5 mpech 488: short *isp;
489: short *rp1;
490: short *rp2;
491: int item;
492: int count;
493: reductions *p;
494: short *rend;
1.1 deraadt 495:
496: count = 0;
497: for (isp = itemset; isp < itemsetend; isp++)
498: {
499: item = ritem[*isp];
500: if (item < 0)
501: {
502: redset[count++] = -item;
503: }
504: }
505:
506: if (count)
507: {
508: p = (reductions *) allocate((unsigned) (sizeof(reductions) +
509: (count - 1) * sizeof(short)));
510:
511: p->number = this_state->number;
512: p->nreds = count;
513:
514: rp1 = redset;
515: rp2 = p->rules;
516: rend = rp1 + count;
517:
518: while (rp1 < rend)
519: *rp2++ = *rp1++;
520:
521: if (last_reduction)
522: {
523: last_reduction->next = p;
524: last_reduction = p;
525: }
526: else
527: {
528: first_reduction = p;
529: last_reduction = p;
530: }
531: }
532: }
533:
1.4 pvalchev 534: void
1.8 pvalchev 535: set_derives(void)
1.1 deraadt 536: {
1.5 mpech 537: int i, k;
538: int lhs;
539: short *rules;
1.1 deraadt 540:
541: derives = NEW2(nsyms, short *);
542: rules = NEW2(nvars + nrules, short);
543:
544: k = 0;
545: for (lhs = start_symbol; lhs < nsyms; lhs++)
546: {
547: derives[lhs] = rules + k;
548: for (i = 0; i < nrules; i++)
549: {
550: if (rlhs[i] == lhs)
551: {
552: rules[k] = i;
553: k++;
554: }
555: }
556: rules[k] = -1;
557: k++;
558: }
559:
560: #ifdef DEBUG
561: print_derives();
562: #endif
563: }
564:
1.4 pvalchev 565: void
1.8 pvalchev 566: free_derives(void)
1.1 deraadt 567: {
568: FREE(derives[start_symbol]);
569: FREE(derives);
570: }
571:
572: #ifdef DEBUG
1.4 pvalchev 573: void
1.8 pvalchev 574: print_derives(void)
1.1 deraadt 575: {
1.5 mpech 576: int i;
577: short *sp;
1.1 deraadt 578:
579: printf("\nDERIVES\n\n");
580:
581: for (i = start_symbol; i < nsyms; i++)
582: {
583: printf("%s derives ", symbol_name[i]);
584: for (sp = derives[i]; *sp >= 0; sp++)
585: {
586: printf(" %d", *sp);
587: }
588: putchar('\n');
589: }
590:
591: putchar('\n');
592: }
593: #endif
594:
1.4 pvalchev 595: void
1.8 pvalchev 596: set_nullable(void)
1.1 deraadt 597: {
1.5 mpech 598: int i, j;
599: int empty;
1.1 deraadt 600: int done;
601:
602: nullable = MALLOC(nsyms);
603: if (nullable == 0) no_space();
604:
605: for (i = 0; i < nsyms; ++i)
606: nullable[i] = 0;
607:
608: done = 0;
609: while (!done)
610: {
611: done = 1;
612: for (i = 1; i < nitems; i++)
613: {
614: empty = 1;
615: while ((j = ritem[i]) >= 0)
616: {
617: if (!nullable[j])
618: empty = 0;
619: ++i;
620: }
621: if (empty)
622: {
623: j = rlhs[-j];
624: if (!nullable[j])
625: {
626: nullable[j] = 1;
627: done = 0;
628: }
629: }
630: }
631: }
632:
633: #ifdef DEBUG
634: for (i = 0; i < nsyms; i++)
635: {
636: if (nullable[i])
637: printf("%s is nullable\n", symbol_name[i]);
638: else
639: printf("%s is not nullable\n", symbol_name[i]);
640: }
641: #endif
642: }
643:
1.4 pvalchev 644: void
1.8 pvalchev 645: free_nullable(void)
1.1 deraadt 646: {
647: FREE(nullable);
648: }
649:
1.4 pvalchev 650: void
1.8 pvalchev 651: lr0(void)
1.1 deraadt 652: {
653: set_derives();
654: set_nullable();
655: generate_states();
656: }