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