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