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