* src/LR0.c (STATE_HASH_SIZE, state_hash): Remove.
(allocate_storage): Use state_hash_new.
(free_storage): Use state_hash_free.
(new_state, get_state): Adjust.
* src/lalr.h, src/lalr.c (states): Move to...
* src/states.h (state_t): Remove the `link' member, no longer
used.
* src/states.h, src/states.c: here.
(state_hash_new, state_hash_free, state_hash_lookup)
(state_hash_insert, states_free): New.
* src/states.c (state_table, state_compare, state_hash): New.
* src/output.c (output_actions): Do not free states now, since we
still need to know the final_state number in `prepare', called
afterwards. Do it...
* src/main.c (main): here: call states_free after `output'.
+2002-06-30 Akim Demaille <akim@epita.fr>
+
+ Use hash.h for the state hash table.
+
+ * src/LR0.c (STATE_HASH_SIZE, state_hash): Remove.
+ (allocate_storage): Use state_hash_new.
+ (free_storage): Use state_hash_free.
+ (new_state, get_state): Adjust.
+ * src/lalr.h, src/lalr.c (states): Move to...
+ * src/states.h (state_t): Remove the `link' member, no longer
+ used.
+ * src/states.h, src/states.c: here.
+ (state_hash_new, state_hash_free, state_hash_lookup)
+ (state_hash_insert, states_free): New.
+ * src/states.c (state_table, state_compare, state_hash): New.
+ * src/output.c (output_actions): Do not free states now, since we
+ still need to know the final_state number in `prepare', called
+ afterwards. Do it...
+ * src/main.c (main): here: call states_free after `output'.
+
+
2002-06-30 Akim Demaille <akim@epita.fr>
* src/state.h, src/state.c (state_new): New, extracted from...
static int *kernel_size = NULL;
static item_number_t *kernel_items = NULL;
-/* hash table for states, to recognize equivalent ones. */
-
-#define STATE_HASH_SIZE 1009
-static state_t **state_hash = NULL;
-
\f
static void
allocate_itemsets (void)
shiftset = XCALLOC (state_number_t, nsyms);
redset = XCALLOC (short, nrules + 1);
- state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
+ state_hash_new ();
shift_symbol = XCALLOC (symbol_number_t, nsyms);
}
free (kernel_base);
free (kernel_size);
XFREE (kernel_items);
- free (state_hash);
+ state_hash_free ();
}
nstates, symbol, symbol_tag_get (symbols[symbol]));
res = state_new (symbol, core_size, core);
+ state_hash_insert (res);
/* If this is the eoftoken, and this is not the initial state, then
this is the final state. */
static state_number_t
get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
{
- int key;
- size_t i;
state_t *sp;
if (trace_flag)
this_state->number, symbol,
symbol_tag_get (symbols[symbol]));
- /* Add up the target state's active item numbers to get a hash key.
- */
- key = 0;
- for (i = 0; i < core_size; ++i)
- key += core[i];
- key = key % STATE_HASH_SIZE;
- sp = state_hash[key];
-
- if (sp)
- {
- int found = 0;
- while (!found)
- {
- if (sp->nitems == core_size)
- {
- found = 1;
- for (i = 0; i < core_size; ++i)
- if (core[i] != sp->items[i])
- found = 0;
- }
-
- if (!found)
- {
- if (sp->link)
- {
- sp = sp->link;
- }
- else /* bucket exhausted and no match */
- {
- sp = sp->link = new_state (symbol, core_size, core);
- found = 1;
- }
- }
- }
- }
- else /* bucket is empty */
- {
- state_hash[key] = sp = new_state (symbol, core_size, core);
- }
+ sp = state_hash_lookup (core_size, core);
+ if (!sp)
+ sp = new_state (symbol, core_size, core);
if (trace_flag)
fprintf (stderr, "Exiting get_state => %d\n", sp->number);
}
}
+
/*-------------------------------------------------------------------.
| Compute the nondeterministic finite state machine (see state.h for |
| details) from the grammar. |
#include "derives.h"
#include "getargs.h"
-/* All the decorated states, indexed by the state number. */
-state_t **states = NULL;
-
rule_t **LArule = NULL;
bitsetv LA = NULL;
size_t nLA;
extern bitsetv LA;
-/* All the states, indexed by the state number. */
-extern state_t **states;
-
#endif /* !LALR_H_ */
/* Output the tables and the parser to ftable. In file output. */
output ();
+ states_free ();
reduce_free ();
conflicts_free ();
free_nullable ();
static void
output_actions (void)
{
- state_number_t i;
-
/* That's a poor way to make sure the sizes are properly corelated,
in particular the signedness is not taking into account, but it's
not useless. */
output_conflicts ();
output_check ();
-
- for (i = 0; i < nstates; ++i)
- {
- free (states[i]->shifts);
- XFREE (states[i]->reductions);
- free (states[i]->errs);
- free (states[i]);
- }
- XFREE (states);
}
\f
#include "system.h"
+#include "hash.h"
#include "complain.h"
#include "gram.h"
#include "state.h"
`-------------------*/
-/*---------------------------------.
-| Create a new array of N shitfs. |
-`---------------------------------*/
+/*---------------------------------------.
+| Create a new array of N shifts/gotos. |
+`---------------------------------------*/
#define SHIFTS_ALLOC(Nshifts) \
(shifts *) xcalloc ((unsigned) (sizeof (shifts) \
accessing symbol: EOF. */
state_t *final_state = NULL;
+#define STATE_ALLOC(Nitems) \
+ (state_t *) xcalloc ((unsigned) (sizeof (state_t) \
+ + (Nitems - 1) * sizeof (item_number_t)), 1)
+
/*------------------------------------------------------------.
| Create a new state with ACCESSING_SYMBOL, for those items. |
`------------------------------------------------------------*/
if (nstates >= STATE_NUMBER_MAX)
fatal (_("too many states (max %d)"), STATE_NUMBER_MAX);
-#define STATE_ALLOC(Nitems) \
- (state_t *) xcalloc ((unsigned) (sizeof (state_t) \
- + (Nitems - 1) * sizeof (item_number_t)), 1)
-
res = STATE_ALLOC (core_size);
res->accessing_symbol = accessing_symbol;
res->number = nstates;
fprintf (out, "]");
}
}
+
+
+/*----------------------.
+| A state hash table. |
+`----------------------*/
+
+/* Initial capacity of states hash table. */
+#define HT_INITIAL_CAPACITY 257
+
+static struct hash_table *state_table = NULL;
+
+/* Two states are equal if they have the same core items. */
+static bool
+state_compare (const state_t *s1, const state_t *s2)
+{
+ int i;
+
+ if (s1->nitems != s2->nitems)
+ return FALSE;
+
+ for (i = 0; i < s1->nitems; ++i)
+ if (s1->items[i] != s2->items[i])
+ return FALSE;
+
+ return TRUE;
+}
+
+static unsigned int
+state_hash (const state_t *state, unsigned int tablesize)
+{
+ /* Add up the state's item numbers to get a hash key. */
+ int key = 0;
+ int i;
+ for (i = 0; i < state->nitems; ++i)
+ key += state->items[i];
+ return key % tablesize;
+}
+
+
+/*-------------------------------.
+| Create the states hash table. |
+`-------------------------------*/
+
+void
+state_hash_new (void)
+{
+ state_table = hash_initialize (HT_INITIAL_CAPACITY,
+ NULL,
+ (Hash_hasher) state_hash,
+ (Hash_comparator) state_compare,
+ (Hash_data_freer) NULL);
+}
+
+
+/*---------------------------------------------.
+| Free the states hash table, not the states. |
+`---------------------------------------------*/
+
+void
+state_hash_free (void)
+{
+ hash_free (state_table);
+}
+
+
+/*---------------------------------------.
+| Insert STATE in the state hash table. |
+`---------------------------------------*/
+
+void
+state_hash_insert (state_t *state)
+{
+ hash_insert (state_table, state);
+}
+
+
+/*------------------------------------------------------------------.
+| Find the state associated to the CORE, and return it. If it does |
+| not exist yet, return NULL. |
+`------------------------------------------------------------------*/
+
+state_t *
+state_hash_lookup (size_t core_size, item_number_t *core)
+{
+ state_t *probe = STATE_ALLOC (core_size);
+ state_t *entry;
+
+ probe->nitems = core_size;
+ memcpy (probe->items, core, core_size * sizeof (core[0]));
+ entry = hash_lookup (state_table, probe);
+ free (probe);
+ return entry;
+}
+
+/* All the decorated states, indexed by the state number. */
+state_t **states = NULL;
+
+
+/*----------------------.
+| Free all the states. |
+`----------------------*/
+
+void
+states_free (void)
+{
+ state_number_t i;
+
+ for (i = 0; i < nstates; ++i)
+ {
+ free (states[i]->shifts);
+ XFREE (states[i]->reductions);
+ free (states[i]->errs);
+ free (states[i]);
+ }
+ XFREE (states);
+}
Each core contains a vector of NITEMS items which are the indices
in the RITEMS vector of the items that are selected in this state.
- The link field is used for chaining symbols that hash states by
- their itemsets. This is for recognizing equivalent states and
- combining them when the states are generated.
-
The two types of transitions are shifts (push the lookahead token
and read another) and reductions (combine the last n things on the
stack via a rule, replace them with the symbol that the rule
typedef struct state_s
{
struct state_s *next;
- struct state_s *link;
state_number_t number;
symbol_number_t accessing_symbol;
void state_rule_lookaheads_print PARAMS ((state_t *state, rule_t *rule,
FILE *out));
+/* Create/destroy the states hash table. */
+void state_hash_new PARAMS ((void));
+void state_hash_free PARAMS ((void));
+
+/* Find the state associated to the CORE, and return it. If it does
+ not exist yet, return NULL. */
+state_t *state_hash_lookup PARAMS ((size_t core_size, item_number_t *core));
+
+/* Insert STATE in the state hash table. */
+void state_hash_insert PARAMS ((state_t *state));
+
+/* All the states, indexed by the state number. */
+extern state_t **states;
+
+/* Free all the states. */
+void states_free PARAMS ((void));
#endif /* !STATE_H_ */
projects / bison.git / commitdiff
