]>
git.saurik.com Git - bison.git/blob - src/LR0.c
1 /* Generate the nondeterministic finite state machine for bison,
2 Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
4 This file is part of Bison, the GNU Compiler Compiler.
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)
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.
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. */
22 /* See comments in state.h for the data structures that represent it.
23 The entry point is generate_states. */
34 extern char *nullable
;
35 extern short *itemset
;
36 extern short *itemsetend
;
43 reductions
*first_reduction
;
45 int get_state
PARAMS((int));
46 core
*new_state
PARAMS((int));
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));
63 static core
*this_state
;
64 static core
*last_state
;
65 static shifts
*last_shift
;
66 static reductions
*last_reduction
;
69 static short *shift_symbol
;
72 static short *shiftset
;
74 static short **kernel_base
;
75 static short **kernel_end
;
76 static short *kernel_items
;
78 /* hash table for states, to recognize equivalent ones. */
80 #define STATE_TABLE_SIZE 1009
81 static core
**state_table
;
86 allocate_itemsets (void)
88 register short *itemp
;
92 register short *symbol_count
;
95 symbol_count
= NEW2(nsyms
, short);
104 symbol_count
[symbol
]++;
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. */
115 kernel_base
= NEW2(nsyms
, short *);
116 kernel_items
= NEW2(count
, short);
119 for (i
= 0; i
< nsyms
; i
++)
121 kernel_base
[i
] = kernel_items
+ count
;
122 count
+= symbol_count
[i
];
125 shift_symbol
= symbol_count
;
126 kernel_end
= NEW2(nsyms
, short *);
131 allocate_storage (void)
135 shiftset
= NEW2(nsyms
, short);
136 redset
= NEW2(nrules
+ 1, short);
137 state_table
= NEW2(STATE_TABLE_SIZE
, core
*);
155 /* compute the nondeterministic finite state machine (see state.h for details)
158 generate_states (void)
161 initialize_closure(nitems
);
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 */
172 /* find the itemsets of the states that shifts can reach */
174 /* find or create the core structures for those states */
177 /* create the shifts structures for the shifts to those states,
178 now that the state numbers transitioning to are known */
182 /* states are queued when they are created; process them all */
183 this_state
= this_state
->next
;
186 /* discard various storage */
190 /* set up initial and final states as parser wants them */
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. */
207 register int shiftcount
;
213 fprintf(stderr
, "Entering new_itemsets\n");
216 for (i
= 0; i
< nsyms
; i
++)
217 kernel_end
[i
] = NULL
;
223 while (isp
< itemsetend
)
229 ksp
= kernel_end
[symbol
];
233 shift_symbol
[shiftcount
++] = symbol
;
234 ksp
= kernel_base
[symbol
];
238 kernel_end
[symbol
] = ksp
;
242 nshifts
= shiftcount
;
247 /* Use the information computed by new_itemsets to find the state numbers
248 reached by each shift transition from the current state.
250 shiftset is set up as a vector of state numbers of those states. */
259 fprintf(stderr
, "Entering append_states\n");
262 /* first sort shift_symbol into increasing order */
264 for (i
= 1; i
< nshifts
; i
++)
266 symbol
= shift_symbol
[i
];
268 while (j
> 0 && shift_symbol
[j
- 1] > symbol
)
270 shift_symbol
[j
] = shift_symbol
[j
- 1];
273 shift_symbol
[j
] = symbol
;
276 for (i
= 0; i
< nshifts
; i
++)
278 symbol
= shift_symbol
[i
];
279 shiftset
[i
] = get_state(symbol
);
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 */
291 get_state (int symbol
)
294 register short *isp1
;
295 register short *isp2
;
296 register short *iend
;
303 fprintf(stderr
, "Entering get_state, symbol = %d\n", symbol
);
306 isp1
= kernel_base
[symbol
];
307 iend
= kernel_end
[symbol
];
310 /* add up the target state's active item numbers to get a hash key */
315 key
= key
% STATE_TABLE_SIZE
;
317 sp
= state_table
[key
];
327 isp1
= kernel_base
[symbol
];
330 while (found
&& isp1
< iend
)
332 if (*isp1
++ != *isp2
++)
343 else /* bucket exhausted and no match */
345 sp
= sp
->link
= new_state(symbol
);
351 else /* bucket is empty */
353 state_table
[key
] = sp
= new_state(symbol
);
361 /* subroutine of get_state. create a new state for those items, if necessary. */
364 new_state (int symbol
)
368 register short *isp1
;
369 register short *isp2
;
370 register short *iend
;
373 fprintf(stderr
, "Entering new_state, symbol = %d\n", symbol
);
376 if (nstates
>= MAXSHORT
)
377 fatal (_("too many states (max %d)"), MAXSHORT
);
379 isp1
= kernel_base
[symbol
];
380 iend
= kernel_end
[symbol
];
383 p
= (core
*) xmalloc((unsigned) (sizeof(core
) + (n
- 1) * sizeof(short)));
384 p
->accessing_symbol
= symbol
;
392 last_state
->next
= p
;
402 initialize_states (void)
405 /* register unsigned *rp1; JF unused */
406 /* register unsigned *rp2; JF unused */
407 /* register unsigned *rend; JF unused */
409 p
= (core
*) xmalloc((unsigned) (sizeof(core
) - sizeof(short)));
410 first_state
= last_state
= this_state
= p
;
421 register short *send
;
423 p
= (shifts
*) xmalloc((unsigned) (sizeof(shifts
) +
424 (nshifts
- 1) * sizeof(short)));
426 p
->number
= this_state
->number
;
427 p
->nshifts
= nshifts
;
431 send
= shiftset
+ nshifts
;
438 last_shift
->next
= p
;
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. */
453 save_reductions (void)
460 register reductions
*p
;
464 /* find and count the active items that represent ends of rules */
467 for (isp
= itemset
; isp
< itemsetend
; isp
++)
472 redset
[count
++] = -item
;
476 /* make a reductions structure and copy the data into it. */
480 p
= (reductions
*) xmalloc((unsigned) (sizeof(reductions
) +
481 (count
- 1) * sizeof(short)));
483 p
->number
= this_state
->number
;
495 last_reduction
->next
= p
;
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. */
514 augment_automaton (void)
518 /* register int found; JF unused */
519 register core
*statep
;
521 register shifts
*sp2
;
522 register shifts
*sp1
= NULL
;
531 statep
= first_state
->next
;
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
;
539 if (statep
->accessing_symbol
== start_symbol
)
541 /* We already have a next-to-final state.
542 Make sure it has a shift to what will be the final state. */
545 while (sp
&& sp
->number
< k
)
551 if (sp
&& sp
->number
== k
)
553 sp2
= (shifts
*) xmalloc((unsigned) (sizeof(shifts
)
554 + sp
->nshifts
* sizeof(short)));
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];
561 /* Patch sp2 into the chain of shifts in place of sp,
563 sp2
->next
= sp
->next
;
565 if (sp
== last_shift
)
574 sp2
->shifts
[0] = nstates
;
576 /* Patch sp2 into the chain of shifts between sp1 and sp. */
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). */
590 sp2
= (shifts
*) xmalloc(sizeof(shifts
)
591 + sp
->nshifts
* sizeof(short));
592 sp2
->nshifts
= sp
->nshifts
+ 1;
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
++)
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
;
604 sp2
->shifts
[k
++] = nstates
;
606 /* Patch sp2 into the chain of shifts
607 in place of sp, at the beginning. */
608 sp2
->next
= sp
->next
;
610 if (last_shift
== sp
)
615 /* Create the next-to-final state, with shift to
616 what will be the final state. */
617 insert_start_shift();
622 /* The initial state didn't even have any shifts.
623 Give it one shift, to the next-to-final state. */
626 sp
->shifts
[0] = nstates
;
628 /* Patch sp into the chain of shifts at the beginning. */
629 sp
->next
= first_shift
;
632 /* Create the next-to-final state, with shift to
633 what will be the final state. */
634 insert_start_shift();
639 /* There are no shifts for any state.
640 Make one shift, from the initial state to the next-to-final state. */
644 sp
->shifts
[0] = nstates
;
646 /* Initialize the chain of shifts with sp. */
650 /* Create the next-to-final state, with shift to
651 what will be the final state. */
652 insert_start_shift();
655 /* Make the final state--the one that follows a shift from the
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
;
663 /* Make the shift from the final state to the termination state. */
665 sp
->number
= nstates
++;
667 sp
->shifts
[0] = nstates
;
668 last_shift
->next
= sp
;
671 /* Note that the variable `final_state' refers to what we sometimes call
672 the termination state. */
673 final_state
= nstates
;
675 /* Make the termination state. */
676 statep
= (core
*) xmalloc((unsigned) (sizeof(core
) - sizeof(short)));
677 statep
->number
= nstates
++;
678 last_state
->next
= statep
;
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. */
687 insert_start_shift (void)
689 register core
*statep
;
692 statep
= (core
*) xmalloc((unsigned) (sizeof(core
) - sizeof(short)));
693 statep
->number
= nstates
;
694 statep
->accessing_symbol
= start_symbol
;
696 last_state
->next
= statep
;
699 /* Make a shift from this state to (what will be) the final state. */
701 sp
->number
= nstates
++;
703 sp
->shifts
[0] = nstates
;
705 last_shift
->next
= sp
;