diff --git a/src/LR0.c b/src/LR0.c index efda69f..667ad3f 100755 --- a/src/LR0.c +++ b/src/LR0.c @@ -1,7 +1,7 @@ /* Generate the nondeterministic finite state machine for Bison. - Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005, 2006, 2007 - Free Software Foundation, Inc. + Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005, 2006, 2007, + 2008 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -77,11 +77,9 @@ state_list_append (symbol_number sym, size_t core_size, item_number *core) return s; } -static int nshifts; -static symbol_number *shift_symbol; +static bitset shift_symbol; static rule **redset; -static state **shiftset; static item_number **kernel_base; static int *kernel_size; @@ -136,19 +134,17 @@ allocate_storage (void) { allocate_itemsets (); - shiftset = xnmalloc (nsyms, sizeof *shiftset); redset = xnmalloc (nrules, sizeof *redset); state_hash_new (); - shift_symbol = xnmalloc (nsyms, sizeof *shift_symbol); + shift_symbol = bitset_create (nsyms, BITSET_FIXED); } static void free_storage (void) { - free (shift_symbol); + bitset_free (shift_symbol); free (redset); - free (shiftset); free (kernel_base); free (kernel_size); free (kernel_items); @@ -183,17 +179,14 @@ new_itemsets (state *s) memset (kernel_size, 0, nsyms * sizeof *kernel_size); - nshifts = 0; + bitset_zero (shift_symbol); for (i = 0; i < nitemset; ++i) if (item_number_is_symbol_number (ritem[itemset[i]])) { symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]); if (!kernel_size[sym]) - { - shift_symbol[nshifts] = sym; - nshifts++; - } + bitset_set (shift_symbol, sym); kernel_base[sym][kernel_size[sym]] = itemset[i] + 1; kernel_size[sym]++; @@ -231,33 +224,25 @@ get_state (symbol_number sym, size_t core_size, item_number *core) | Use the information computed by new_itemsets to find the state | | numbers reached by each shift transition from S. | | | -| SHIFTSET is set up as a vector of those states. | +| Record in the transitions structure. | `---------------------------------------------------------------*/ static void append_states (state *s) { int i; + symbol_number sym; + size_t nshifts = bitset_count (shift_symbol); if (trace_flag & trace_automaton) fprintf (stderr, "Entering append_states, state = %d\n", s->number); - /* First sort shift_symbol into increasing order. */ - - for (i = 1; i < nshifts; i++) - { - symbol_number sym = shift_symbol[i]; - int j; - for (j = i; 0 < j && sym < shift_symbol[j - 1]; j--) - shift_symbol[j] = shift_symbol[j - 1]; - shift_symbol[j] = sym; - } - - for (i = 0; i < nshifts; i++) - { - symbol_number sym = shift_symbol[i]; - shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]); - } + state_transitions_set (s, nshifts); + i = 0; + for (sym = 0; sym < nsyms; sym++) + if (bitset_test (shift_symbol, sym)) + s->transitions->states[i++] + = get_state (sym, kernel_size[sym], kernel_base[sym]); } @@ -314,7 +299,7 @@ set_states (void) computed later, but set_conflicts. */ state *s = this->state; if (!s->transitions) - state_transitions_set (s, 0, 0); + state_transitions_set (s, 0); if (!s->reductions) state_reductions_set (s, 0, 0); @@ -360,12 +345,9 @@ generate_states (void) save_reductions (s); /* Find the itemsets of the states that shifts can reach. */ new_itemsets (s); - /* Find or create the core structures for those states. */ + /* Find or create the core structures for those states. + Record the shifts allowed out of this state. */ append_states (s); - - /* Create the shifts structures for the shifts to those states, - now that the state numbers transitioning to are known. */ - state_transitions_set (s, nshifts, shiftset); } /* discard various storage */ diff --git a/src/state.c b/src/state.c index d3460c1..bf4ad3d 100755 --- a/src/state.c +++ b/src/state.c @@ -1,6 +1,6 @@ /* Type definitions for nondeterministic finite state machine for Bison. - Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -39,12 +39,11 @@ `-----------------------------------------*/ static transitions * -transitions_new (int num, state **the_states) +transitions_new (int num) { - size_t states_size = num * sizeof *the_states; + size_t states_size = num * sizeof (state *); transitions *res = xmalloc (offsetof (transitions, states) + states_size); res->num = num; - memcpy (res->states, the_states, states_size); return res; } @@ -169,15 +168,15 @@ state_free (state *s) } -/*---------------------------. -| Set the transitions of S. | -`---------------------------*/ +/*--------------------------------. +| Allocate the transitions of S. | +`--------------------------------*/ void -state_transitions_set (state *s, int num, state **trans) +state_transitions_set (state *s, int num) { aver (!s->transitions); - s->transitions = transitions_new (num, trans); + s->transitions = transitions_new (num); } diff --git a/src/state.h b/src/state.h index 4afc1f0..422555d 100755 --- a/src/state.h +++ b/src/state.h @@ -1,6 +1,6 @@ /* Type definitions for nondeterministic finite state machine for Bison. - Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007 Free + Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007, 2008 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -223,8 +223,8 @@ extern state *final_state; state *state_new (symbol_number accessing_symbol, size_t core_size, item_number *core); -/* Set the transitions of STATE. */ -void state_transitions_set (state *s, int num, state **trans); +/* Allocate the transitions of STATE. */ +void state_transitions_set (state *s, int num); /* Set the reductions of STATE. */ void state_reductions_set (state *s, int num, rule **reds);