#include "complain.h"
#include "closure.h"
#include "LR0.h"
-
+#include "reduce.h"
int nstates;
int final_state;
static short *shiftset = NULL;
static short **kernel_base = NULL;
-static short **kernel_end = NULL;
+static int *kernel_size = NULL;
static short *kernel_items = NULL;
/* hash table for states, to recognize equivalent ones. */
allocate_itemsets (void)
{
int i;
- int count;
- short *symbol_count = NULL;
- count = 0;
- symbol_count = XCALLOC (short, nsyms);
+ /* Count the number of occurrences of all the symbols in RITEMS.
+ Note that useless productions (hence useless nonterminals) are
+ browsed too, hence we need to allocate room for _all_ the
+ symbols. */
+ int count = 0;
+ short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
for (i = 0; ritem[i]; ++i)
if (ritem[i] > 0)
count += symbol_count[i];
}
- shift_symbol = symbol_count;
- kernel_end = XCALLOC (short *, nsyms);
+ free (symbol_count);
+ kernel_size = XCALLOC (int, nsyms);
}
static void
free_storage (void)
{
- XFREE (shift_symbol);
- XFREE (redset);
- XFREE (shiftset);
- XFREE (kernel_base);
- XFREE (kernel_end);
+ free (shift_symbol);
+ free (redset);
+ free (shiftset);
+ free (kernel_base);
+ free (kernel_size);
XFREE (kernel_items);
- XFREE (state_table);
+ free (state_table);
}
| shift_symbol is set to a vector of the symbols that can be |
| shifted. For each symbol in the grammar, kernel_base[symbol] |
| points to a vector of item numbers activated if that symbol is |
-| shifted, and kernel_end[symbol] points after the end of that |
-| vector. |
+| shifted, and kernel_size[symbol] is their numbers. |
`----------------------------------------------------------------*/
static void
this_state->number);
for (i = 0; i < nsyms; i++)
- kernel_end[i] = NULL;
+ kernel_size[i] = 0;
+ shift_symbol = XCALLOC (short, nsyms);
shiftcount = 0;
- for (i = 0; i < itemsetend - itemset; ++i)
+ for (i = 0; i < itemsetsize; ++i)
{
int symbol = ritem[itemset[i]];
if (symbol > 0)
{
- short *ksp = kernel_end[symbol];
-
- if (!ksp)
+ if (!kernel_size[symbol])
{
shift_symbol[shiftcount] = symbol;
- ksp = kernel_base[symbol];
shiftcount++;
}
- *ksp++ = itemset[i] + 1;
- kernel_end[symbol] = ksp;
+ kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
+ kernel_size[symbol]++;
}
}
static core *
new_state (int symbol)
{
- int n;
core *p;
if (trace_flag)
if (nstates >= MAXSHORT)
fatal (_("too many states (max %d)"), MAXSHORT);
- n = kernel_end[symbol] - kernel_base[symbol];
-
- p = CORE_ALLOC (n);
+ p = CORE_ALLOC (kernel_size[symbol]);
p->accessing_symbol = symbol;
p->number = nstates;
- p->nitems = n;
+ p->nitems = kernel_size[symbol];
- shortcpy (p->items, kernel_base[symbol], n);
+ shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);
last_state->next = p;
last_state = p;
get_state (int symbol)
{
int key;
- short *isp2;
int i;
core *sp;
- int n = kernel_end[symbol] - kernel_base[symbol];
-
if (trace_flag)
fprintf (stderr, "Entering get_state, state = %d, symbol = %d (%s)\n",
this_state->number, symbol, tags[symbol]);
/* Add up the target state's active item numbers to get a hash key.
*/
key = 0;
- for (i = 0; i < n; ++i)
+ for (i = 0; i < kernel_size[symbol]; ++i)
key += kernel_base[symbol][i];
key = key % STATE_TABLE_SIZE;
sp = state_table[key];
int found = 0;
while (!found)
{
- if (sp->nitems == n)
+ if (sp->nitems == kernel_size[symbol])
{
- int i;
found = 1;
- for (i = 0; i < n; ++i)
+ for (i = 0; i < kernel_size[symbol]; ++i)
if (kernel_base[symbol][i] != sp->items[i])
found = 0;
}
}
+/*------------------------------------------------------------.
+| Save the NSHIFTS of SHIFTSET into the current linked list. |
+`------------------------------------------------------------*/
+
static void
save_shifts (void)
{
- shifts *p = SHIFTS_ALLOC (nshifts);
+ shifts *p = shifts_new (nshifts);
p->number = this_state->number;
- p->nshifts = nshifts;
shortcpy (p->shifts, shiftset, nshifts);
last_state = statep;
/* Make a shift from this state to (what will be) the final state. */
- sp = SHIFTS_ALLOC (1);
+ sp = shifts_new (1);
sp->number = nstates++;
- sp->nshifts = 1;
sp->shifts[0] = nstates;
last_shift->next = sp;
static void
augment_automaton (void)
{
- int i;
- int k;
core *statep;
shifts *sp;
- shifts *sp2;
shifts *sp1 = NULL;
sp = first_shift;
- if (sp)
+ if (!sp->nshifts)
{
- if (sp->number == 0)
- {
- k = sp->nshifts;
- statep = first_state->next;
+ /* There are no shifts for any state. Make one shift, from the
+ initial state to the next-to-final state. */
- /* The states reached by shifts from first_state are numbered 1...K.
- Look for one reached by start_symbol. */
- while (statep->accessing_symbol < start_symbol
- && statep->number < k)
- statep = statep->next;
-
- if (statep->accessing_symbol == start_symbol)
- {
- /* We already have a next-to-final state.
- Make sure it has a shift to what will be the final state. */
- k = statep->number;
+ sp = shifts_new (1);
+ sp->shifts[0] = nstates;
- while (sp && sp->number < k)
- {
- sp1 = sp;
- sp = sp->next;
- }
+ /* Initialize the chain of shifts with sp. */
+ first_shift = sp;
+ last_shift = sp;
- if (sp && sp->number == k)
- {
- sp2 = SHIFTS_ALLOC (sp->nshifts + 1);
- sp2->number = k;
- sp2->nshifts = sp->nshifts + 1;
- sp2->shifts[0] = nstates;
- for (i = sp->nshifts; i > 0; i--)
- sp2->shifts[i] = sp->shifts[i - 1];
-
- /* Patch sp2 into the chain of shifts in place of sp,
- following sp1. */
- sp2->next = sp->next;
- sp1->next = sp2;
- if (sp == last_shift)
- last_shift = sp2;
- XFREE (sp);
- }
- else
- {
- sp2 = SHIFTS_ALLOC (1);
- sp2->number = k;
- sp2->nshifts = 1;
- sp2->shifts[0] = nstates;
-
- /* Patch sp2 into the chain of shifts between sp1 and sp. */
- sp2->next = sp;
- sp1->next = sp2;
- if (sp == 0)
- last_shift = sp2;
- }
- }
- else
- {
- /* There is no next-to-final state as yet. */
- /* Add one more shift in first_shift,
- going to the next-to-final state (yet to be made). */
- sp = first_shift;
+ /* Create the next-to-final state, with shift to
+ what will be the final state. */
+ insert_start_shift ();
+ }
+ else if (sp->number == 0)
+ {
+ statep = first_state->next;
- sp2 = SHIFTS_ALLOC (sp->nshifts + 1);
- sp2->nshifts = sp->nshifts + 1;
+ /* The states reached by shifts from FIRST_STATE are numbered
+ 1..(SP->NSHIFTS). Look for one reached by START_SYMBOL. */
+ while (statep->accessing_symbol < start_symbol
+ && statep->number < sp->nshifts)
+ statep = statep->next;
- /* Stick this shift into the vector at the proper place. */
- statep = first_state->next;
- for (k = 0, i = 0; i < sp->nshifts; k++, i++)
- {
- if (statep->accessing_symbol > start_symbol && i == k)
- sp2->shifts[k++] = nstates;
- sp2->shifts[k] = sp->shifts[i];
- statep = statep->next;
- }
- if (i == k)
- sp2->shifts[k++] = nstates;
+ if (statep->accessing_symbol == start_symbol)
+ {
+ /* We already have a next-to-final state.
+ Make sure it has a shift to what will be the final state. */
+ while (sp && sp->number < statep->number)
+ {
+ sp1 = sp;
+ sp = sp->next;
+ }
- /* Patch sp2 into the chain of shifts
- in place of sp, at the beginning. */
+ if (sp && sp->number == statep->number)
+ {
+ int i;
+ shifts *sp2 = shifts_new (sp->nshifts + 1);
+ sp2->number = statep->number;
+ sp2->shifts[0] = nstates;
+ for (i = sp->nshifts; i > 0; i--)
+ sp2->shifts[i] = sp->shifts[i - 1];
+
+ /* Patch sp2 into the chain of shifts in place of sp,
+ following sp1. */
sp2->next = sp->next;
- first_shift = sp2;
- if (last_shift == sp)
+ sp1->next = sp2;
+ if (sp == last_shift)
last_shift = sp2;
-
XFREE (sp);
-
- /* Create the next-to-final state, with shift to
- what will be the final state. */
- insert_start_shift ();
+ }
+ else
+ {
+ shifts *sp2 = shifts_new (1);
+ sp2->number = statep->number;
+ sp2->shifts[0] = nstates;
+
+ /* Patch sp2 into the chain of shifts between sp1 and sp. */
+ sp2->next = sp;
+ sp1->next = sp2;
+ if (sp == 0)
+ last_shift = sp2;
}
}
else
{
- /* The initial state didn't even have any shifts.
- Give it one shift, to the next-to-final state. */
- sp = SHIFTS_ALLOC (1);
- sp->nshifts = 1;
- sp->shifts[0] = nstates;
+ int i, k;
+ shifts *sp2;
+
+ /* There is no next-to-final state as yet. */
+ /* Add one more shift in first_shift,
+ going to the next-to-final state (yet to be made). */
+ sp = first_shift;
+
+ sp2 = shifts_new (sp->nshifts + 1);
+
+ /* Stick this shift into the vector at the proper place. */
+ statep = first_state->next;
+ for (k = 0, i = 0; i < sp->nshifts; k++, i++)
+ {
+ if (statep->accessing_symbol > start_symbol && i == k)
+ sp2->shifts[k++] = nstates;
+ sp2->shifts[k] = sp->shifts[i];
+ statep = statep->next;
+ }
+ if (i == k)
+ sp2->shifts[k++] = nstates;
- /* Patch sp into the chain of shifts at the beginning. */
- sp->next = first_shift;
- first_shift = sp;
+ /* Patch sp2 into the chain of shifts
+ in place of sp, at the beginning. */
+ sp2->next = sp->next;
+ first_shift = sp2;
+ if (last_shift == sp)
+ last_shift = sp2;
+
+ XFREE (sp);
/* Create the next-to-final state, with shift to
what will be the final state. */
}
else
{
- /* There are no shifts for any state.
- Make one shift, from the initial state to the next-to-final state. */
-
- sp = SHIFTS_ALLOC (1);
- sp->nshifts = 1;
+ /* The initial state didn't even have any shifts.
+ Give it one shift, to the next-to-final state. */
+ sp = shifts_new (1);
sp->shifts[0] = nstates;
- /* Initialize the chain of shifts with sp. */
+ /* Patch sp into the chain of shifts at the beginning. */
+ sp->next = first_shift;
first_shift = sp;
- last_shift = sp;
/* Create the next-to-final state, with shift to
- what will be the final state. */
+ what will be the final state. */
insert_start_shift ();
}
last_state = statep;
/* Make the shift from the final state to the termination state. */
- sp = SHIFTS_ALLOC (1);
+ sp = shifts_new (1);
sp->number = nstates++;
- sp->nshifts = 1;
sp->shifts[0] = nstates;
last_shift->next = sp;
last_shift = sp;
static void
save_reductions (void)
{
- short *isp;
- int item;
int count;
- reductions *p;
-
- short *rend;
+ int i;
/* Find and count the active items that represent ends of rules. */
count = 0;
- for (isp = itemset; isp < itemsetend; isp++)
+ for (i = 0; i < itemsetsize; ++i)
{
- item = ritem[*isp];
+ int item = ritem[itemset[i]];
if (item < 0)
redset[count++] = -item;
}
if (count)
{
- p = REDUCTIONS_ALLOC (count);
+ reductions *p = REDUCTIONS_ALLOC (count);
p->number = this_state->number;
p->nreds = count;
/* create the shifts structures for the shifts to those states,
now that the state numbers transitioning to are known */
- if (nshifts > 0)
- save_shifts ();
+ save_shifts ();
/* states are queued when they are created; process them all */
this_state = this_state->next;
projects / bison.git / blobdiff