![[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 [Apple XNU] / GNUtools / bison|
Return to LR0.c CVS log | Up to [Apple XNU] / GNUtools / bison |
1.1 root 1: /* Generate the nondeterministic finite state machine for bison,
2: Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
3:
4: This file is part of Bison, the GNU Compiler Compiler.
5:
6: Bison is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: Bison is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with Bison; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* See comments in state.h for the data structures that represent it.
22: The entry point is generate_states. */
23:
24: #include <stdio.h>
25: #include "system.h"
26: #include "machine.h"
27: #include "new.h"
28: #include "gram.h"
29: #include "state.h"
30:
31:
32: extern char *nullable;
33: extern short *itemset;
34: extern short *itemsetend;
35:
36:
37: int nstates;
38: int final_state;
39: core *first_state;
40: shifts *first_shift;
41: reductions *first_reduction;
42:
43: int get_state();
44: core *new_state();
45:
46: void new_itemsets();
47: void append_states();
48: void initialize_states();
49: void save_shifts();
50: void save_reductions();
51: void augment_automaton();
52: void insert_start_shift();
53: extern void initialize_closure();
54: extern void closure();
55: extern void finalize_closure();
56: extern void toomany();
57:
58: static core *this_state;
59: static core *last_state;
60: static shifts *last_shift;
61: static reductions *last_reduction;
62:
63: static int nshifts;
64: static short *shift_symbol;
65:
66: static short *redset;
67: static short *shiftset;
68:
69: static short **kernel_base;
70: static short **kernel_end;
71: static short *kernel_items;
72:
73: /* hash table for states, to recognize equivalent ones. */
74:
75: #define STATE_TABLE_SIZE 1009
76: static core **state_table;
77:
78:
79:
80: void
81: allocate_itemsets()
82: {
83: register short *itemp;
84: register int symbol;
85: register int i;
86: register int count;
87: register short *symbol_count;
88:
89: count = 0;
90: symbol_count = NEW2(nsyms, short);
91:
92: itemp = ritem;
93: symbol = *itemp++;
94: while (symbol)
95: {
96: if (symbol > 0)
97: {
98: count++;
99: symbol_count[symbol]++;
100: }
101: symbol = *itemp++;
102: }
103:
104: /* see comments before new_itemsets. All the vectors of items
105: live inside kernel_items. The number of active items after
106: some symbol cannot be more than the number of times that symbol
107: appears as an item, which is symbol_count[symbol].
108: We allocate that much space for each symbol. */
109:
110: kernel_base = NEW2(nsyms, short *);
111: kernel_items = NEW2(count, short);
112:
113: count = 0;
114: for (i = 0; i < nsyms; i++)
115: {
116: kernel_base[i] = kernel_items + count;
117: count += symbol_count[i];
118: }
119:
120: shift_symbol = symbol_count;
121: kernel_end = NEW2(nsyms, short *);
122: }
123:
124:
125: void
126: allocate_storage()
127: {
128: allocate_itemsets();
129:
130: shiftset = NEW2(nsyms, short);
131: redset = NEW2(nrules + 1, short);
132: state_table = NEW2(STATE_TABLE_SIZE, core *);
133: }
134:
135:
136: void
137: free_storage()
138: {
139: FREE(shift_symbol);
140: FREE(redset);
141: FREE(shiftset);
142: FREE(kernel_base);
143: FREE(kernel_end);
144: FREE(kernel_items);
145: FREE(state_table);
146: }
147:
148:
149:
150: /* compute the nondeterministic finite state machine (see state.h for details)
151: from the grammar. */
152: void
153: generate_states()
154: {
155: allocate_storage();
156: initialize_closure(nitems);
157: initialize_states();
158:
159: while (this_state)
160: {
161: /* Set up ruleset and itemset for the transitions out of this state.
162: ruleset gets a 1 bit for each rule that could reduce now.
163: itemset gets a vector of all the items that could be accepted next. */
164: closure(this_state->items, this_state->nitems);
165: /* record the reductions allowed out of this state */
166: save_reductions();
167: /* find the itemsets of the states that shifts can reach */
168: new_itemsets();
169: /* find or create the core structures for those states */
170: append_states();
171:
172: /* create the shifts structures for the shifts to those states,
173: now that the state numbers transitioning to are known */
174: if (nshifts > 0)
175: save_shifts();
176:
177: /* states are queued when they are created; process them all */
178: this_state = this_state->next;
179: }
180:
181: /* discard various storage */
182: finalize_closure();
183: free_storage();
184:
185: /* set up initial and final states as parser wants them */
186: augment_automaton();
187: }
188:
189:
190:
191: /* Find which symbols can be shifted in the current state,
192: and for each one record which items would be active after that shift.
193: Uses the contents of itemset.
194: shift_symbol is set to a vector of the symbols that can be shifted.
195: For each symbol in the grammar, kernel_base[symbol] points to
196: a vector of item numbers activated if that symbol is shifted,
197: and kernel_end[symbol] points after the end of that vector. */
198: void
199: new_itemsets()
200: {
201: register int i;
202: register int shiftcount;
203: register short *isp;
204: register short *ksp;
205: register int symbol;
206:
207: #ifdef TRACE
208: fprintf(stderr, "Entering new_itemsets\n");
209: #endif
210:
211: for (i = 0; i < nsyms; i++)
212: kernel_end[i] = NULL;
213:
214: shiftcount = 0;
215:
216: isp = itemset;
217:
218: while (isp < itemsetend)
219: {
220: i = *isp++;
221: symbol = ritem[i];
222: if (symbol > 0)
223: {
224: ksp = kernel_end[symbol];
225:
226: if (!ksp)
227: {
228: shift_symbol[shiftcount++] = symbol;
229: ksp = kernel_base[symbol];
230: }
231:
232: *ksp++ = i + 1;
233: kernel_end[symbol] = ksp;
234: }
235: }
236:
237: nshifts = shiftcount;
238: }
239:
240:
241:
242: /* Use the information computed by new_itemsets to find the state numbers
243: reached by each shift transition from the current state.
244:
245: shiftset is set up as a vector of state numbers of those states. */
246: void
247: append_states()
248: {
249: register int i;
250: register int j;
251: register int symbol;
252:
253: #ifdef TRACE
254: fprintf(stderr, "Entering append_states\n");
255: #endif
256:
257: /* first sort shift_symbol into increasing order */
258:
259: for (i = 1; i < nshifts; i++)
260: {
261: symbol = shift_symbol[i];
262: j = i;
263: while (j > 0 && shift_symbol[j - 1] > symbol)
264: {
265: shift_symbol[j] = shift_symbol[j - 1];
266: j--;
267: }
268: shift_symbol[j] = symbol;
269: }
270:
271: for (i = 0; i < nshifts; i++)
272: {
273: symbol = shift_symbol[i];
274: shiftset[i] = get_state(symbol);
275: }
276: }
277:
278:
279:
280: /* find the state number for the state we would get to
281: (from the current state) by shifting symbol.
282: Create a new state if no equivalent one exists already.
283: Used by append_states */
284:
285: int
286: get_state(symbol)
287: int symbol;
288: {
289: register int key;
290: register short *isp1;
291: register short *isp2;
292: register short *iend;
293: register core *sp;
294: register int found;
295:
296: int n;
297:
298: #ifdef TRACE
299: fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
300: #endif
301:
302: isp1 = kernel_base[symbol];
303: iend = kernel_end[symbol];
304: n = iend - isp1;
305:
306: /* add up the target state's active item numbers to get a hash key */
307: key = 0;
308: while (isp1 < iend)
309: key += *isp1++;
310:
311: key = key % STATE_TABLE_SIZE;
312:
313: sp = state_table[key];
314:
315: if (sp)
316: {
317: found = 0;
318: while (!found)
319: {
320: if (sp->nitems == n)
321: {
322: found = 1;
323: isp1 = kernel_base[symbol];
324: isp2 = sp->items;
325:
326: while (found && isp1 < iend)
327: {
328: if (*isp1++ != *isp2++)
329: found = 0;
330: }
331: }
332:
333: if (!found)
334: {
335: if (sp->link)
336: {
337: sp = sp->link;
338: }
339: else /* bucket exhausted and no match */
340: {
341: sp = sp->link = new_state(symbol);
342: found = 1;
343: }
344: }
345: }
346: }
347: else /* bucket is empty */
348: {
349: state_table[key] = sp = new_state(symbol);
350: }
351:
352: return (sp->number);
353: }
354:
355:
356:
357: /* subroutine of get_state. create a new state for those items, if necessary. */
358:
359: core *
360: new_state(symbol)
361: int symbol;
362: {
363: register int n;
364: register core *p;
365: register short *isp1;
366: register short *isp2;
367: register short *iend;
368:
369: #ifdef TRACE
370: fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
371: #endif
372:
373: if (nstates >= MAXSHORT)
374: toomany("states");
375:
376: isp1 = kernel_base[symbol];
377: iend = kernel_end[symbol];
378: n = iend - isp1;
379:
380: p = (core *) xmalloc((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
381: p->accessing_symbol = symbol;
382: p->number = nstates;
383: p->nitems = n;
384:
385: isp2 = p->items;
386: while (isp1 < iend)
387: *isp2++ = *isp1++;
388:
389: last_state->next = p;
390: last_state = p;
391:
392: nstates++;
393:
394: return (p);
395: }
396:
397:
398: void
399: initialize_states()
400: {
401: register core *p;
402: /* register unsigned *rp1; JF unused */
403: /* register unsigned *rp2; JF unused */
404: /* register unsigned *rend; JF unused */
405:
406: p = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
407: first_state = last_state = this_state = p;
408: nstates = 1;
409: }
410:
411:
412: void
413: save_shifts()
414: {
415: register shifts *p;
416: register short *sp1;
417: register short *sp2;
418: register short *send;
419:
420: p = (shifts *) xmalloc((unsigned) (sizeof(shifts) +
421: (nshifts - 1) * sizeof(short)));
422:
423: p->number = this_state->number;
424: p->nshifts = nshifts;
425:
426: sp1 = shiftset;
427: sp2 = p->shifts;
428: send = shiftset + nshifts;
429:
430: while (sp1 < send)
431: *sp2++ = *sp1++;
432:
433: if (last_shift)
434: {
435: last_shift->next = p;
436: last_shift = p;
437: }
438: else
439: {
440: first_shift = p;
441: last_shift = p;
442: }
443: }
444:
445:
446:
447: /* find which rules can be used for reduction transitions from the current state
448: and make a reductions structure for the state to record their rule numbers. */
449: void
450: save_reductions()
451: {
452: register short *isp;
453: register short *rp1;
454: register short *rp2;
455: register int item;
456: register int count;
457: register reductions *p;
458:
459: short *rend;
460:
461: /* find and count the active items that represent ends of rules */
462:
463: count = 0;
464: for (isp = itemset; isp < itemsetend; isp++)
465: {
466: item = ritem[*isp];
467: if (item < 0)
468: {
469: redset[count++] = -item;
470: }
471: }
472:
473: /* make a reductions structure and copy the data into it. */
474:
475: if (count)
476: {
477: p = (reductions *) xmalloc((unsigned) (sizeof(reductions) +
478: (count - 1) * sizeof(short)));
479:
480: p->number = this_state->number;
481: p->nreds = count;
482:
483: rp1 = redset;
484: rp2 = p->rules;
485: rend = rp1 + count;
486:
487: while (rp1 < rend)
488: *rp2++ = *rp1++;
489:
490: if (last_reduction)
491: {
492: last_reduction->next = p;
493: last_reduction = p;
494: }
495: else
496: {
497: first_reduction = p;
498: last_reduction = p;
499: }
500: }
501: }
502:
503:
504:
505: /* Make sure that the initial state has a shift that accepts the
506: grammar's start symbol and goes to the next-to-final state,
507: which has a shift going to the final state, which has a shift
508: to the termination state.
509: Create such states and shifts if they don't happen to exist already. */
510: void
511: augment_automaton()
512: {
513: register int i;
514: register int k;
515: /* register int found; JF unused */
516: register core *statep;
517: register shifts *sp;
518: register shifts *sp2;
519: register shifts *sp1;
520:
521: sp = first_shift;
522:
523: if (sp)
524: {
525: if (sp->number == 0)
526: {
527: k = sp->nshifts;
528: statep = first_state->next;
529:
530: /* The states reached by shifts from first_state are numbered 1...K.
531: Look for one reached by start_symbol. */
532: while (statep->accessing_symbol < start_symbol
533: && statep->number < k)
534: statep = statep->next;
535:
536: if (statep->accessing_symbol == start_symbol)
537: {
538: /* We already have a next-to-final state.
539: Make sure it has a shift to what will be the final state. */
540: k = statep->number;
541:
542: while (sp && sp->number < k)
543: {
544: sp1 = sp;
545: sp = sp->next;
546: }
547:
548: if (sp && sp->number == k)
549: {
550: sp2 = (shifts *) xmalloc((unsigned) (sizeof(shifts)
551: + sp->nshifts * sizeof(short)));
552: sp2->number = k;
553: sp2->nshifts = sp->nshifts + 1;
554: sp2->shifts[0] = nstates;
555: for (i = sp->nshifts; i > 0; i--)
556: sp2->shifts[i] = sp->shifts[i - 1];
557:
558: /* Patch sp2 into the chain of shifts in place of sp,
559: following sp1. */
560: sp2->next = sp->next;
561: sp1->next = sp2;
562: if (sp == last_shift)
563: last_shift = sp2;
564: FREE(sp);
565: }
566: else
567: {
568: sp2 = NEW(shifts);
569: sp2->number = k;
570: sp2->nshifts = 1;
571: sp2->shifts[0] = nstates;
572:
573: /* Patch sp2 into the chain of shifts between sp1 and sp. */
574: sp2->next = sp;
575: sp1->next = sp2;
576: if (sp == 0)
577: last_shift = sp2;
578: }
579: }
580: else
581: {
582: /* There is no next-to-final state as yet. */
583: /* Add one more shift in first_shift,
584: going to the next-to-final state (yet to be made). */
585: sp = first_shift;
586:
587: sp2 = (shifts *) xmalloc(sizeof(shifts)
588: + sp->nshifts * sizeof(short));
589: sp2->nshifts = sp->nshifts + 1;
590:
591: /* Stick this shift into the vector at the proper place. */
592: statep = first_state->next;
593: for (k = 0, i = 0; i < sp->nshifts; k++, i++)
594: {
595: if (statep->accessing_symbol > start_symbol && i == k)
596: sp2->shifts[k++] = nstates;
597: sp2->shifts[k] = sp->shifts[i];
598: statep = statep->next;
599: }
600: if (i == k)
601: sp2->shifts[k++] = nstates;
602:
603: /* Patch sp2 into the chain of shifts
604: in place of sp, at the beginning. */
605: sp2->next = sp->next;
606: first_shift = sp2;
607: if (last_shift == sp)
608: last_shift = sp2;
609:
610: FREE(sp);
611:
612: /* Create the next-to-final state, with shift to
613: what will be the final state. */
614: insert_start_shift();
615: }
616: }
617: else
618: {
619: /* The initial state didn't even have any shifts.
620: Give it one shift, to the next-to-final state. */
621: sp = NEW(shifts);
622: sp->nshifts = 1;
623: sp->shifts[0] = nstates;
624:
625: /* Patch sp into the chain of shifts at the beginning. */
626: sp->next = first_shift;
627: first_shift = sp;
628:
629: /* Create the next-to-final state, with shift to
630: what will be the final state. */
631: insert_start_shift();
632: }
633: }
634: else
635: {
636: /* There are no shifts for any state.
637: Make one shift, from the initial state to the next-to-final state. */
638:
639: sp = NEW(shifts);
640: sp->nshifts = 1;
641: sp->shifts[0] = nstates;
642:
643: /* Initialize the chain of shifts with sp. */
644: first_shift = sp;
645: last_shift = sp;
646:
647: /* Create the next-to-final state, with shift to
648: what will be the final state. */
649: insert_start_shift();
650: }
651:
652: /* Make the final state--the one that follows a shift from the
653: next-to-final state.
654: The symbol for that shift is 0 (end-of-file). */
655: statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
656: statep->number = nstates;
657: last_state->next = statep;
658: last_state = statep;
659:
660: /* Make the shift from the final state to the termination state. */
661: sp = NEW(shifts);
662: sp->number = nstates++;
663: sp->nshifts = 1;
664: sp->shifts[0] = nstates;
665: last_shift->next = sp;
666: last_shift = sp;
667:
668: /* Note that the variable `final_state' refers to what we sometimes call
669: the termination state. */
670: final_state = nstates;
671:
672: /* Make the termination state. */
673: statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
674: statep->number = nstates++;
675: last_state->next = statep;
676: last_state = statep;
677: }
678:
679:
680: /* subroutine of augment_automaton.
681: Create the next-to-final state, to which a shift has already been made in
682: the initial state. */
683: void
684: insert_start_shift()
685: {
686: register core *statep;
687: register shifts *sp;
688:
689: statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
690: statep->number = nstates;
691: statep->accessing_symbol = start_symbol;
692:
693: last_state->next = statep;
694: last_state = statep;
695:
696: /* Make a shift from this state to (what will be) the final state. */
697: sp = NEW(shifts);
698: sp->number = nstates++;
699: sp->nshifts = 1;
700: sp->shifts[0] = nstates;
701:
702: last_shift->next = sp;
703: last_shift = sp;
704: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.