![[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.6 ! millert 1: /* $OpenBSD: lr0.c,v 1.5 2001/11/19 19:02:18 mpech 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.
19: * 3. All advertising materials mentioning features or use of this software
20: * must display the following acknowledgement:
21: * This product includes software developed by the University of
22: * California, Berkeley and its contributors.
23: * 4. Neither the name of the University nor the names of its contributors
24: * may be used to endorse or promote products derived from this software
25: * without specific prior written permission.
26: *
27: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37: * SUCH DAMAGE.
38: */
39:
1.1 deraadt 40: #ifndef lint
1.2 deraadt 41: #if 0
42: static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
43: #else
1.6 ! millert 44: static char rcsid[] = "$OpenBSD: lr0.c,v 1.5 2001/11/19 19:02:18 mpech Exp $";
1.2 deraadt 45: #endif
1.1 deraadt 46: #endif /* not lint */
47:
48: #include "defs.h"
49:
50: extern short *itemset;
51: extern short *itemsetend;
52: extern unsigned *ruleset;
53:
54: int nstates;
55: core *first_state;
56: shifts *first_shift;
57: reductions *first_reduction;
58:
1.6 ! millert 59: int get_state(int);
! 60: core *new_state(int);
1.4 pvalchev 61:
1.6 ! millert 62: void allocate_itemsets(void);
! 63: void allocate_storage(void);
! 64: void append_states(void);
! 65: void free_storage(void);
! 66: void generate_states(void);
! 67: void initialize_states(void);
! 68: void new_itemsets(void);
! 69: void show_cores(void);
! 70: void show_ritems(void);
! 71: void show_rrhs(void);
! 72: void show_shifts(void);
! 73: void save_shifts(void);
! 74: void save_reductions(void);
! 75: void set_derives(void);
! 76: void print_derives(void);
! 77: void set_nullable(void);
! 78: void free_derives(void);
! 79: void free_nullable(void);
1.1 deraadt 80:
81: static core **state_set;
82: static core *this_state;
83: static core *last_state;
84: static shifts *last_shift;
85: static reductions *last_reduction;
86:
87: static int nshifts;
88: static short *shift_symbol;
89:
90: static short *redset;
91: static short *shiftset;
92:
93: static short **kernel_base;
94: static short **kernel_end;
95: static short *kernel_items;
96:
1.4 pvalchev 97: void
1.1 deraadt 98: allocate_itemsets()
99: {
1.5 mpech 100: short *itemp;
101: short *item_end;
102: int symbol;
103: int i;
104: int count;
105: int max;
106: short *symbol_count;
1.1 deraadt 107:
108: count = 0;
109: symbol_count = NEW2(nsyms, short);
110:
111: item_end = ritem + nitems;
112: for (itemp = ritem; itemp < item_end; itemp++)
113: {
114: symbol = *itemp;
115: if (symbol >= 0)
116: {
117: count++;
118: symbol_count[symbol]++;
119: }
120: }
121:
122: kernel_base = NEW2(nsyms, short *);
123: kernel_items = NEW2(count, short);
124:
125: count = 0;
126: max = 0;
127: for (i = 0; i < nsyms; i++)
128: {
129: kernel_base[i] = kernel_items + count;
130: count += symbol_count[i];
131: if (max < symbol_count[i])
132: max = symbol_count[i];
133: }
134:
135: shift_symbol = symbol_count;
136: kernel_end = NEW2(nsyms, short *);
137: }
138:
1.4 pvalchev 139: void
1.1 deraadt 140: allocate_storage()
141: {
142: allocate_itemsets();
143: shiftset = NEW2(nsyms, short);
144: redset = NEW2(nrules + 1, short);
145: state_set = NEW2(nitems, core *);
146: }
147:
1.4 pvalchev 148: void
1.1 deraadt 149: append_states()
150: {
1.5 mpech 151: int i;
152: int j;
153: int symbol;
1.1 deraadt 154:
155: #ifdef TRACE
156: fprintf(stderr, "Entering append_states()\n");
157: #endif
158: for (i = 1; i < nshifts; i++)
159: {
160: symbol = shift_symbol[i];
161: j = i;
162: while (j > 0 && shift_symbol[j - 1] > symbol)
163: {
164: shift_symbol[j] = shift_symbol[j - 1];
165: j--;
166: }
167: shift_symbol[j] = symbol;
168: }
169:
170: for (i = 0; i < nshifts; i++)
171: {
172: symbol = shift_symbol[i];
173: shiftset[i] = get_state(symbol);
174: }
175: }
176:
1.4 pvalchev 177: void
1.1 deraadt 178: free_storage()
179: {
180: FREE(shift_symbol);
181: FREE(redset);
182: FREE(shiftset);
183: FREE(kernel_base);
184: FREE(kernel_end);
185: FREE(kernel_items);
186: FREE(state_set);
187: }
188:
189:
1.4 pvalchev 190: void
1.1 deraadt 191: generate_states()
192: {
193: allocate_storage();
194: itemset = NEW2(nitems, short);
195: ruleset = NEW2(WORDSIZE(nrules), unsigned);
196: set_first_derives();
197: initialize_states();
198:
199: while (this_state)
200: {
201: closure(this_state->items, this_state->nitems);
202: save_reductions();
203: new_itemsets();
204: append_states();
205:
206: if (nshifts > 0)
207: save_shifts();
208:
209: this_state = this_state->next;
210: }
211:
212: finalize_closure();
213: free_storage();
214: }
215:
216:
217:
218: int
219: get_state(symbol)
220: int symbol;
221: {
1.5 mpech 222: int key;
223: short *isp1;
224: short *isp2;
225: short *iend;
226: core *sp;
227: int found;
228: int n;
1.1 deraadt 229:
230: #ifdef TRACE
231: fprintf(stderr, "Entering get_state(%d)\n", symbol);
232: #endif
233:
234: isp1 = kernel_base[symbol];
235: iend = kernel_end[symbol];
236: n = iend - isp1;
237:
238: key = *isp1;
239: assert(0 <= key && key < nitems);
240: sp = state_set[key];
241: if (sp)
242: {
243: found = 0;
244: while (!found)
245: {
246: if (sp->nitems == n)
247: {
248: found = 1;
249: isp1 = kernel_base[symbol];
250: isp2 = sp->items;
251:
252: while (found && isp1 < iend)
253: {
254: if (*isp1++ != *isp2++)
255: found = 0;
256: }
257: }
258:
259: if (!found)
260: {
261: if (sp->link)
262: {
263: sp = sp->link;
264: }
265: else
266: {
267: sp = sp->link = new_state(symbol);
268: found = 1;
269: }
270: }
271: }
272: }
273: else
274: {
275: state_set[key] = sp = new_state(symbol);
276: }
277:
278: return (sp->number);
279: }
280:
281:
1.4 pvalchev 282: void
1.1 deraadt 283: initialize_states()
284: {
1.5 mpech 285: int i;
286: short *start_derives;
287: core *p;
1.1 deraadt 288:
289: start_derives = derives[start_symbol];
290: for (i = 0; start_derives[i] >= 0; ++i)
291: continue;
292:
293: p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
294: if (p == 0) no_space();
295:
296: p->next = 0;
297: p->link = 0;
298: p->number = 0;
299: p->accessing_symbol = 0;
300: p->nitems = i;
301:
302: for (i = 0; start_derives[i] >= 0; ++i)
303: p->items[i] = rrhs[start_derives[i]];
304:
305: first_state = last_state = this_state = p;
306: nstates = 1;
307: }
308:
1.4 pvalchev 309: void
1.1 deraadt 310: new_itemsets()
311: {
1.5 mpech 312: int i;
313: int shiftcount;
314: short *isp;
315: short *ksp;
316: int symbol;
1.1 deraadt 317:
318: for (i = 0; i < nsyms; i++)
319: kernel_end[i] = 0;
320:
321: shiftcount = 0;
322: isp = itemset;
323: while (isp < itemsetend)
324: {
325: i = *isp++;
326: symbol = ritem[i];
327: if (symbol > 0)
328: {
329: ksp = kernel_end[symbol];
330: if (!ksp)
331: {
332: shift_symbol[shiftcount++] = symbol;
333: ksp = kernel_base[symbol];
334: }
335:
336: *ksp++ = i + 1;
337: kernel_end[symbol] = ksp;
338: }
339: }
340:
341: nshifts = shiftcount;
342: }
343:
344:
345:
346: core *
347: new_state(symbol)
348: int symbol;
349: {
1.5 mpech 350: int n;
351: core *p;
352: short *isp1;
353: short *isp2;
354: short *iend;
1.1 deraadt 355:
356: #ifdef TRACE
357: fprintf(stderr, "Entering new_state(%d)\n", symbol);
358: #endif
359:
360: if (nstates >= MAXSHORT)
361: fatal("too many states");
362:
363: isp1 = kernel_base[symbol];
364: iend = kernel_end[symbol];
365: n = iend - isp1;
366:
367: p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
368: p->accessing_symbol = symbol;
369: p->number = nstates;
370: p->nitems = n;
371:
372: isp2 = p->items;
373: while (isp1 < iend)
374: *isp2++ = *isp1++;
375:
376: last_state->next = p;
377: last_state = p;
378:
379: nstates++;
380:
381: return (p);
382: }
383:
384:
385: /* show_cores is used for debugging */
386:
1.4 pvalchev 387: void
1.1 deraadt 388: show_cores()
389: {
390: core *p;
391: int i, j, k, n;
392: int itemno;
393:
394: k = 0;
395: for (p = first_state; p; ++k, p = p->next)
396: {
397: if (k) printf("\n");
398: printf("state %d, number = %d, accessing symbol = %s\n",
399: k, p->number, symbol_name[p->accessing_symbol]);
400: n = p->nitems;
401: for (i = 0; i < n; ++i)
402: {
403: itemno = p->items[i];
404: printf("%4d ", itemno);
405: j = itemno;
406: while (ritem[j] >= 0) ++j;
407: printf("%s :", symbol_name[rlhs[-ritem[j]]]);
408: j = rrhs[-ritem[j]];
409: while (j < itemno)
410: printf(" %s", symbol_name[ritem[j++]]);
411: printf(" .");
412: while (ritem[j] >= 0)
413: printf(" %s", symbol_name[ritem[j++]]);
414: printf("\n");
415: fflush(stdout);
416: }
417: }
418: }
419:
420:
421: /* show_ritems is used for debugging */
422:
1.4 pvalchev 423: void
1.1 deraadt 424: show_ritems()
425: {
426: int i;
427:
428: for (i = 0; i < nitems; ++i)
429: printf("ritem[%d] = %d\n", i, ritem[i]);
430: }
431:
432:
433: /* show_rrhs is used for debugging */
1.4 pvalchev 434:
435: void
1.1 deraadt 436: show_rrhs()
437: {
438: int i;
439:
440: for (i = 0; i < nrules; ++i)
441: printf("rrhs[%d] = %d\n", i, rrhs[i]);
442: }
443:
444:
445: /* show_shifts is used for debugging */
446:
1.4 pvalchev 447: void
1.1 deraadt 448: show_shifts()
449: {
450: shifts *p;
451: int i, j, k;
452:
453: k = 0;
454: for (p = first_shift; p; ++k, p = p->next)
455: {
456: if (k) printf("\n");
457: printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
458: p->nshifts);
459: j = p->nshifts;
460: for (i = 0; i < j; ++i)
461: printf("\t%d\n", p->shift[i]);
462: }
463: }
464:
1.4 pvalchev 465: void
1.1 deraadt 466: save_shifts()
467: {
1.5 mpech 468: shifts *p;
469: short *sp1;
470: short *sp2;
471: short *send;
1.1 deraadt 472:
473: p = (shifts *) allocate((unsigned) (sizeof(shifts) +
474: (nshifts - 1) * sizeof(short)));
475:
476: p->number = this_state->number;
477: p->nshifts = nshifts;
478:
479: sp1 = shiftset;
480: sp2 = p->shift;
481: send = shiftset + nshifts;
482:
483: while (sp1 < send)
484: *sp2++ = *sp1++;
485:
486: if (last_shift)
487: {
488: last_shift->next = p;
489: last_shift = p;
490: }
491: else
492: {
493: first_shift = p;
494: last_shift = p;
495: }
496: }
497:
498:
1.4 pvalchev 499: void
1.1 deraadt 500: save_reductions()
501: {
1.5 mpech 502: short *isp;
503: short *rp1;
504: short *rp2;
505: int item;
506: int count;
507: reductions *p;
508: short *rend;
1.1 deraadt 509:
510: count = 0;
511: for (isp = itemset; isp < itemsetend; isp++)
512: {
513: item = ritem[*isp];
514: if (item < 0)
515: {
516: redset[count++] = -item;
517: }
518: }
519:
520: if (count)
521: {
522: p = (reductions *) allocate((unsigned) (sizeof(reductions) +
523: (count - 1) * sizeof(short)));
524:
525: p->number = this_state->number;
526: p->nreds = count;
527:
528: rp1 = redset;
529: rp2 = p->rules;
530: rend = rp1 + count;
531:
532: while (rp1 < rend)
533: *rp2++ = *rp1++;
534:
535: if (last_reduction)
536: {
537: last_reduction->next = p;
538: last_reduction = p;
539: }
540: else
541: {
542: first_reduction = p;
543: last_reduction = p;
544: }
545: }
546: }
547:
1.4 pvalchev 548: void
1.1 deraadt 549: set_derives()
550: {
1.5 mpech 551: int i, k;
552: int lhs;
553: short *rules;
1.1 deraadt 554:
555: derives = NEW2(nsyms, short *);
556: rules = NEW2(nvars + nrules, short);
557:
558: k = 0;
559: for (lhs = start_symbol; lhs < nsyms; lhs++)
560: {
561: derives[lhs] = rules + k;
562: for (i = 0; i < nrules; i++)
563: {
564: if (rlhs[i] == lhs)
565: {
566: rules[k] = i;
567: k++;
568: }
569: }
570: rules[k] = -1;
571: k++;
572: }
573:
574: #ifdef DEBUG
575: print_derives();
576: #endif
577: }
578:
1.4 pvalchev 579: void
1.1 deraadt 580: free_derives()
581: {
582: FREE(derives[start_symbol]);
583: FREE(derives);
584: }
585:
586: #ifdef DEBUG
1.4 pvalchev 587: void
1.1 deraadt 588: print_derives()
589: {
1.5 mpech 590: int i;
591: short *sp;
1.1 deraadt 592:
593: printf("\nDERIVES\n\n");
594:
595: for (i = start_symbol; i < nsyms; i++)
596: {
597: printf("%s derives ", symbol_name[i]);
598: for (sp = derives[i]; *sp >= 0; sp++)
599: {
600: printf(" %d", *sp);
601: }
602: putchar('\n');
603: }
604:
605: putchar('\n');
606: }
607: #endif
608:
1.4 pvalchev 609: void
1.1 deraadt 610: set_nullable()
611: {
1.5 mpech 612: int i, j;
613: int empty;
1.1 deraadt 614: int done;
615:
616: nullable = MALLOC(nsyms);
617: if (nullable == 0) no_space();
618:
619: for (i = 0; i < nsyms; ++i)
620: nullable[i] = 0;
621:
622: done = 0;
623: while (!done)
624: {
625: done = 1;
626: for (i = 1; i < nitems; i++)
627: {
628: empty = 1;
629: while ((j = ritem[i]) >= 0)
630: {
631: if (!nullable[j])
632: empty = 0;
633: ++i;
634: }
635: if (empty)
636: {
637: j = rlhs[-j];
638: if (!nullable[j])
639: {
640: nullable[j] = 1;
641: done = 0;
642: }
643: }
644: }
645: }
646:
647: #ifdef DEBUG
648: for (i = 0; i < nsyms; i++)
649: {
650: if (nullable[i])
651: printf("%s is nullable\n", symbol_name[i]);
652: else
653: printf("%s is not nullable\n", symbol_name[i]);
654: }
655: #endif
656: }
657:
1.4 pvalchev 658: void
1.1 deraadt 659: free_nullable()
660: {
661: FREE(nullable);
662: }
663:
1.4 pvalchev 664: void
1.1 deraadt 665: lr0()
666: {
667: set_derives();
668: set_nullable();
669: generate_states();
670: }