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