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