#include "system.h"
#include "getargs.h"
+#include "reader.h"
#include "gram.h"
#include "state.h"
#include "complain.h"
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. */
static void
allocate_itemsets (void)
{
- short *itemp = NULL;
- int symbol;
int i;
int count;
short *symbol_count = NULL;
count = 0;
symbol_count = XCALLOC (short, nsyms);
- itemp = ritem;
- symbol = *itemp++;
- while (symbol)
- {
- if (symbol > 0)
- {
- count++;
- symbol_count[symbol]++;
- }
- symbol = *itemp++;
- }
+ for (i = 0; ritem[i]; ++i)
+ if (ritem[i] > 0)
+ {
+ count++;
+ symbol_count[ritem[i]]++;
+ }
/* See comments before new_itemsets. All the vectors of items
live inside KERNEL_ITEMS. The number of active items after
}
shift_symbol = symbol_count;
- kernel_end = XCALLOC (short *, nsyms);
+ kernel_size = XCALLOC (int, nsyms);
}
XFREE (redset);
XFREE (shiftset);
XFREE (kernel_base);
- XFREE (kernel_end);
+ XFREE (kernel_size);
XFREE (kernel_items);
XFREE (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
int shiftcount;
if (trace_flag)
- fprintf (stderr, "Entering new_itemsets, state = %d\n", nstates);
+ fprintf (stderr, "Entering new_itemsets, state = %d\n",
+ this_state->number);
for (i = 0; i < nsyms; i++)
- kernel_end[i] = NULL;
+ kernel_size[i] = 0;
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)
- fprintf (stderr, "Entering new_state, state = %d, symbol = %d\n",
- nstates, symbol);
+ fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
+ this_state->number, symbol, tags[symbol]);
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\n",
- nstates, symbol);
+ 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;
}
state_table[key] = sp = new_state (symbol);
}
+ if (trace_flag)
+ fprintf (stderr, "Exiting get_state => %d\n", sp->number);
+
return sp->number;
}
int symbol;
if (trace_flag)
- fprintf (stderr, "Entering append_states\n");
-
+ fprintf (stderr, "Entering append_states, state = %d\n",
+ this_state->number);
/* first sort shift_symbol into increasing order */
}
+/*---------------------------------.
+| Create a new array of N shitfs. |
+`---------------------------------*/
+
+static shifts *
+shifts_new (int n)
+{
+ shifts *res = SHIFTS_ALLOC (n);
+ res->nshifts = n;
+ return res;
+}
+
+
+/*------------------------------------------------------------.
+| 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;
if (sp && sp->number == k)
{
- sp2 = SHIFTS_ALLOC (sp->nshifts + 1);
+ sp2 = shifts_new (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];
}
else
{
- sp2 = SHIFTS_ALLOC (1);
+ sp2 = shifts_new (1);
sp2->number = k;
- sp2->nshifts = 1;
sp2->shifts[0] = nstates;
/* Patch sp2 into the chain of shifts between sp1 and sp. */
going to the next-to-final state (yet to be made). */
sp = first_shift;
- sp2 = SHIFTS_ALLOC (sp->nshifts + 1);
- sp2->nshifts = sp->nshifts + 1;
+ sp2 = shifts_new (sp->nshifts + 1);
/* Stick this shift into the vector at the proper place. */
statep = first_state->next;
{
/* 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_new (1);
sp->shifts[0] = nstates;
/* Patch sp into the chain of shifts at the beginning. */
/* 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;
+ sp = shifts_new (1);
sp->shifts[0] = nstates;
/* Initialize the chain of shifts with sp. */
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;
projects / bison.git / blobdiff