[bison.git] / src / LR0.c

/* Generate the nondeterministic finite state machine for bison,
   Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.

This file is part of Bison, the GNU Compiler Compiler.

Bison is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

Bison is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Bison; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */


/* See comments in state.h for the data structures that represent it.
   The entry point is generate_states.  */

#include <stdio.h>
#include "system.h"
#include "machine.h"
#include "alloc.h"
#include "gram.h"
#include "state.h"


extern char *nullable;
extern short *itemset;
extern short *itemsetend;


int nstates;
int final_state;
core *first_state;
shifts *first_shift;
reductions *first_reduction;

int get_state PARAMS((int));
core *new_state PARAMS((int));

void allocate_itemsets PARAMS((void));
void allocate_storage PARAMS((void));
void free_storage PARAMS((void));
void generate_states PARAMS((void));
void new_itemsets PARAMS((void));
void append_states PARAMS((void));
void initialize_states PARAMS((void));
void save_shifts PARAMS((void));
void save_reductions PARAMS((void));
void augment_automaton PARAMS((void));
void insert_start_shift PARAMS((void));
extern void initialize_closure PARAMS((int));
extern void closure PARAMS((short *, int));
extern void finalize_closure PARAMS((void));
extern void toomany PARAMS((char *));

static core *this_state;
static core *last_state;
static shifts *last_shift;
static reductions *last_reduction;

static int nshifts;
static short *shift_symbol;

static short *redset;
static short *shiftset;

static short **kernel_base;
static short **kernel_end;
static short *kernel_items;

/* hash table for states, to recognize equivalent ones.  */

#define	STATE_TABLE_SIZE	1009
static core **state_table;


void
allocate_itemsets (void)
{
  register short *itemp;
  register int symbol;
  register int i;
  register int count;
  register short *symbol_count;

  count = 0;
  symbol_count = NEW2(nsyms, short);

  itemp = ritem;
  symbol = *itemp++;
  while (symbol)
    {
      if (symbol > 0)
	{
	  count++;
	  symbol_count[symbol]++;
	}
      symbol = *itemp++;
    }

  /* see comments before new_itemsets.  All the vectors of items
     live inside kernel_items.  The number of active items after
     some symbol cannot be more than the number of times that symbol
     appears as an item, which is symbol_count[symbol].
     We allocate that much space for each symbol.  */

  kernel_base = NEW2(nsyms, short *);
  kernel_items = NEW2(count, short);

  count = 0;
  for (i = 0; i < nsyms; i++)
    {
      kernel_base[i] = kernel_items + count;
      count += symbol_count[i];
    }

  shift_symbol = symbol_count;
  kernel_end = NEW2(nsyms, short *);
}


void
allocate_storage (void)
{
  allocate_itemsets();

  shiftset = NEW2(nsyms, short);
  redset = NEW2(nrules + 1, short);
  state_table = NEW2(STATE_TABLE_SIZE, core *);
}


void
free_storage (void)
{
  FREE(shift_symbol);
  FREE(redset);
  FREE(shiftset);
  FREE(kernel_base);
  FREE(kernel_end);
  FREE(kernel_items);
  FREE(state_table);
}


/* compute the nondeterministic finite state machine (see state.h for details)
from the grammar.  */
void
generate_states (void)
{
  allocate_storage();
  initialize_closure(nitems);
  initialize_states();

  while (this_state)
    {
      /* Set up ruleset and itemset for the transitions out of this state.
         ruleset gets a 1 bit for each rule that could reduce now.
	 itemset gets a vector of all the items that could be accepted next.  */
      closure(this_state->items, this_state->nitems);
      /* record the reductions allowed out of this state */
      save_reductions();
      /* find the itemsets of the states that shifts can reach */
      new_itemsets();
      /* find or create the core structures for those states */
      append_states();

      /* create the shifts structures for the shifts to those states,
         now that the state numbers transitioning to are known */
      if (nshifts > 0)
        save_shifts();

      /* states are queued when they are created; process them all */
      this_state = this_state->next;
    }

  /* discard various storage */
  finalize_closure();
  free_storage();

  /* set up initial and final states as parser wants them */
  augment_automaton();
}


/* Find which symbols can be shifted in the current state,
   and for each one record which items would be active after that shift.
   Uses the contents of itemset.
   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.  */
void
new_itemsets (void)
{
  register int i;
  register int shiftcount;
  register short *isp;
  register short *ksp;
  register int symbol;

#ifdef	TRACE
  fprintf(stderr, "Entering new_itemsets\n");
#endif

  for (i = 0; i < nsyms; i++)
    kernel_end[i] = NULL;

  shiftcount = 0;

  isp = itemset;

  while (isp < itemsetend)
    {
      i = *isp++;
      symbol = ritem[i];
      if (symbol > 0)
	{
          ksp = kernel_end[symbol];

          if (!ksp)
	    {
	      shift_symbol[shiftcount++] = symbol;
	      ksp = kernel_base[symbol];
	    }

          *ksp++ = i + 1;
          kernel_end[symbol] = ksp;
	}
    }

  nshifts = shiftcount;
}


/* Use the information computed by new_itemsets to find the state numbers
   reached by each shift transition from the current state.

   shiftset is set up as a vector of state numbers of those states.  */
void
append_states (void)
{
  register int i;
  register int j;
  register int symbol;

#ifdef	TRACE
  fprintf(stderr, "Entering append_states\n");
#endif

  /* first sort shift_symbol into increasing order */

  for (i = 1; i < nshifts; i++)
    {
      symbol = shift_symbol[i];
      j = i;
      while (j > 0 && shift_symbol[j - 1] > symbol)
	{
	  shift_symbol[j] = shift_symbol[j - 1];
	  j--;
	}
      shift_symbol[j] = symbol;
    }

  for (i = 0; i < nshifts; i++)
    {
      symbol = shift_symbol[i];
      shiftset[i] = get_state(symbol);
    }
}


/* find the state number for the state we would get to
(from the current state) by shifting symbol.
Create a new state if no equivalent one exists already.
Used by append_states  */

int
get_state (int symbol)
{
  register int key;
  register short *isp1;
  register short *isp2;
  register short *iend;
  register core *sp;
  register int found;

  int n;

#ifdef	TRACE
  fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
#endif

  isp1 = kernel_base[symbol];
  iend = kernel_end[symbol];
  n = iend - isp1;

  /* add up the target state's active item numbers to get a hash key */
  key = 0;
  while (isp1 < iend)
    key += *isp1++;

  key = key % STATE_TABLE_SIZE;

  sp = state_table[key];

  if (sp)
    {
      found = 0;
      while (!found)
	{
	  if (sp->nitems == n)
	    {
	      found = 1;
	      isp1 = kernel_base[symbol];
	      isp2 = sp->items;

	      while (found && isp1 < iend)
		{
		  if (*isp1++ != *isp2++)
		    found = 0;
		}
	    }

	  if (!found)
	    {
	      if (sp->link)
		{
		  sp = sp->link;
		}
	      else   /* bucket exhausted and no match */
		{
		  sp = sp->link = new_state(symbol);
		  found = 1;
		}
	    }
	}
    }
  else      /* bucket is empty */
    {
      state_table[key] = sp = new_state(symbol);
    }

  return (sp->number);
}


/* subroutine of get_state.  create a new state for those items, if necessary.  */

core *
new_state (int symbol)
{
  register int n;
  register core *p;
  register short *isp1;
  register short *isp2;
  register short *iend;

#ifdef	TRACE
  fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
#endif

  if (nstates >= MAXSHORT)
    toomany("states");

  isp1 = kernel_base[symbol];
  iend = kernel_end[symbol];
  n = iend - isp1;

  p = (core *) xmalloc((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  p->accessing_symbol = symbol;
  p->number = nstates;
  p->nitems = n;

  isp2 = p->items;
  while (isp1 < iend)
    *isp2++ = *isp1++;

  last_state->next = p;
  last_state = p;

  nstates++;

  return (p);
}


void
initialize_states (void)
{
  register core *p;
/*  register unsigned *rp1; JF unused */
/*  register unsigned *rp2; JF unused */
/*  register unsigned *rend; JF unused */

  p = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  first_state = last_state = this_state = p;
  nstates = 1;
}


void
save_shifts (void)
{
  register shifts *p;
  register short *sp1;
  register short *sp2;
  register short *send;

  p = (shifts *) xmalloc((unsigned) (sizeof(shifts) +
				     (nshifts - 1) * sizeof(short)));

  p->number = this_state->number;
  p->nshifts = nshifts;

  sp1 = shiftset;
  sp2 = p->shifts;
  send = shiftset + nshifts;

  while (sp1 < send)
    *sp2++ = *sp1++;

  if (last_shift)
    {
      last_shift->next = p;
      last_shift = p;
    }
  else
    {
      first_shift = p;
      last_shift = p;
    }
}


/* find which rules can be used for reduction transitions from the current state
   and make a reductions structure for the state to record their rule numbers.  */
void
save_reductions (void)
{
  register short *isp;
  register short *rp1;
  register short *rp2;
  register int item;
  register int count;
  register reductions *p;

  short *rend;

  /* find and count the active items that represent ends of rules */

  count = 0;
  for (isp = itemset; isp < itemsetend; isp++)
    {
      item = ritem[*isp];
      if (item < 0)
	{
	  redset[count++] = -item;
	}
    }

  /* make a reductions structure and copy the data into it.  */

  if (count)
    {
      p = (reductions *) xmalloc((unsigned) (sizeof(reductions) +
					     (count - 1) * sizeof(short)));

      p->number = this_state->number;
      p->nreds = count;

      rp1 = redset;
      rp2 = p->rules;
      rend = rp1 + count;

      while (rp1 < rend)
	*rp2++ = *rp1++;

      if (last_reduction)
	{
	  last_reduction->next = p;
	  last_reduction = p;
	}
      else
	{
	  first_reduction = p;
	  last_reduction = p;
	}
    }
}


/* Make sure that the initial state has a shift that accepts the
grammar's start symbol and goes to the next-to-final state,
which has a shift going to the final state, which has a shift
to the termination state.
Create such states and shifts if they don't happen to exist already.  */
void
augment_automaton (void)
{
  register int i;
  register int k;
/*  register int found; JF unused */
  register core *statep;
  register shifts *sp;
  register shifts *sp2;
  register shifts *sp1;

  sp = first_shift;

  if (sp)
    {
      if (sp->number == 0)
	{
	  k = sp->nshifts;
	  statep = first_state->next;

	  /* 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;

	      while (sp && sp->number < k)
		{
		  sp1 = sp;
		  sp = sp->next;
		}

	      if (sp && sp->number == k)
		{
		  sp2 = (shifts *) xmalloc((unsigned) (sizeof(shifts)
						       + sp->nshifts * sizeof(short)));
		  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;
		  FREE(sp);
		}
	      else
		{
		  sp2 = NEW(shifts);
		  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;

	      sp2 = (shifts *) xmalloc(sizeof(shifts)
					 + sp->nshifts * sizeof(short));
	      sp2->nshifts = 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 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;

	      FREE(sp);

	      /* Create the next-to-final state, with shift to
		 what will be the final state.  */
	      insert_start_shift();
	    }
	}
      else
	{
	  /* The initial state didn't even have any shifts.
	     Give it one shift, to the next-to-final state.  */
	  sp = NEW(shifts);
	  sp->nshifts = 1;
	  sp->shifts[0] = nstates;

	  /* Patch sp into the chain of shifts at the beginning.  */
	  sp->next = first_shift;
	  first_shift = sp;

	  /* Create the next-to-final state, with shift to
	     what will be the final state.  */
	  insert_start_shift();
	}
    }
  else
    {
      /* There are no shifts for any state.
	 Make one shift, from the initial state to the next-to-final state.  */

      sp = NEW(shifts);
      sp->nshifts = 1;
      sp->shifts[0] = nstates;

      /* Initialize the chain of shifts with sp.  */
      first_shift = sp;
      last_shift = sp;

      /* Create the next-to-final state, with shift to
	 what will be the final state.  */
      insert_start_shift();
    }

  /* Make the final state--the one that follows a shift from the
     next-to-final state.
     The symbol for that shift is 0 (end-of-file).  */
  statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  statep->number = nstates;
  last_state->next = statep;
  last_state = statep;

  /* Make the shift from the final state to the termination state.  */
  sp = NEW(shifts);
  sp->number = nstates++;
  sp->nshifts = 1;
  sp->shifts[0] = nstates;
  last_shift->next = sp;
  last_shift = sp;

  /* Note that the variable `final_state' refers to what we sometimes call
     the termination state.  */
  final_state = nstates;

  /* Make the termination state.  */
  statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  statep->number = nstates++;
  last_state->next = statep;
  last_state = statep;
}


/* subroutine of augment_automaton.
   Create the next-to-final state, to which a shift has already been made in
   the initial state.  */
void
insert_start_shift (void)
{
  register core *statep;
  register shifts *sp;

  statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
  statep->number = nstates;
  statep->accessing_symbol = start_symbol;

  last_state->next = statep;
  last_state = statep;

  /* Make a shift from this state to (what will be) the final state.  */
  sp = NEW(shifts);
  sp->number = nstates++;
  sp->nshifts = 1;
  sp->shifts[0] = nstates;

  last_shift->next = sp;
  last_shift = sp;
}
Commit	Line	Data
40675e7c DM	1	/* Generate the nondeterministic finite state machine for bison,
	2	Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
	3
	4	This file is part of Bison, the GNU Compiler Compiler.
	5
	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)
	9	any later version.
	10
	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.
	15
	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, 675 Mass Ave, Cambridge, MA 02139, USA. */
	19
	20
	21	/* See comments in state.h for the data structures that represent it.
	22	The entry point is generate_states. */
	23
	24	#include <stdio.h>
	25	#include "system.h"
	26	#include "machine.h"
7612000c	27	#include "alloc.h"
40675e7c DM	28	#include "gram.h"
	29	#include "state.h"
	30
	31
	32	extern char *nullable;
	33	extern short *itemset;
	34	extern short *itemsetend;
	35
	36
	37	int nstates;
	38	int final_state;
	39	core *first_state;
	40	shifts *first_shift;
	41	reductions *first_reduction;
	42
d2729d44 JT	43	int get_state PARAMS((int));
	44	core *new_state PARAMS((int));
	45
	46	void allocate_itemsets PARAMS((void));
	47	void allocate_storage PARAMS((void));
	48	void free_storage PARAMS((void));
	49	void generate_states PARAMS((void));
	50	void new_itemsets PARAMS((void));
	51	void append_states PARAMS((void));
	52	void initialize_states PARAMS((void));
	53	void save_shifts PARAMS((void));
	54	void save_reductions PARAMS((void));
	55	void augment_automaton PARAMS((void));
	56	void insert_start_shift PARAMS((void));
	57	extern void initialize_closure PARAMS((int));
	58	extern void closure PARAMS((short *, int));
	59	extern void finalize_closure PARAMS((void));
	60	extern void toomany PARAMS((char *));
40675e7c DM	61
	62	static core *this_state;
	63	static core *last_state;
	64	static shifts *last_shift;
	65	static reductions *last_reduction;
	66
	67	static int nshifts;
	68	static short *shift_symbol;
	69
	70	static short *redset;
	71	static short *shiftset;
	72
	73	static short **kernel_base;
	74	static short **kernel_end;
	75	static short *kernel_items;
	76
	77	/* hash table for states, to recognize equivalent ones. */
	78
	79	#define STATE_TABLE_SIZE 1009
	80	static core **state_table;
	81
	82
	83
	84	void
d2729d44	85	allocate_itemsets (void)
40675e7c DM	86	{
	87	register short *itemp;
	88	register int symbol;
	89	register int i;
	90	register int count;
	91	register short *symbol_count;
	92
	93	count = 0;
	94	symbol_count = NEW2(nsyms, short);
	95
	96	itemp = ritem;
	97	symbol = *itemp++;
	98	while (symbol)
	99	{
	100	if (symbol > 0)
	101	{
	102	count++;
	103	symbol_count[symbol]++;
	104	}
	105	symbol = *itemp++;
	106	}
	107
	108	/* see comments before new_itemsets. All the vectors of items
	109	live inside kernel_items. The number of active items after
	110	some symbol cannot be more than the number of times that symbol
	111	appears as an item, which is symbol_count[symbol].
	112	We allocate that much space for each symbol. */
	113
	114	kernel_base = NEW2(nsyms, short *);
	115	kernel_items = NEW2(count, short);
	116
	117	count = 0;
	118	for (i = 0; i < nsyms; i++)
	119	{
	120	kernel_base[i] = kernel_items + count;
	121	count += symbol_count[i];
	122	}
	123
	124	shift_symbol = symbol_count;
	125	kernel_end = NEW2(nsyms, short *);
	126	}
	127
	128
	129	void
d2729d44	130	allocate_storage (void)
40675e7c DM	131	{
	132	allocate_itemsets();
	133
	134	shiftset = NEW2(nsyms, short);
	135	redset = NEW2(nrules + 1, short);
	136	state_table = NEW2(STATE_TABLE_SIZE, core *);
	137	}
	138
	139
	140	void
d2729d44	141	free_storage (void)
40675e7c DM	142	{
	143	FREE(shift_symbol);
	144	FREE(redset);
	145	FREE(shiftset);
	146	FREE(kernel_base);
	147	FREE(kernel_end);
	148	FREE(kernel_items);
	149	FREE(state_table);
	150	}
	151
	152
	153
	154	/* compute the nondeterministic finite state machine (see state.h for details)
	155	from the grammar. */
	156	void
d2729d44	157	generate_states (void)
40675e7c DM	158	{
	159	allocate_storage();
	160	initialize_closure(nitems);
	161	initialize_states();
	162
	163	while (this_state)
	164	{
	165	/* Set up ruleset and itemset for the transitions out of this state.
	166	ruleset gets a 1 bit for each rule that could reduce now.
	167	itemset gets a vector of all the items that could be accepted next. */
	168	closure(this_state->items, this_state->nitems);
	169	/* record the reductions allowed out of this state */
	170	save_reductions();
	171	/* find the itemsets of the states that shifts can reach */
	172	new_itemsets();
	173	/* find or create the core structures for those states */
	174	append_states();
	175
	176	/* create the shifts structures for the shifts to those states,
	177	now that the state numbers transitioning to are known */
	178	if (nshifts > 0)
	179	save_shifts();
	180
	181	/* states are queued when they are created; process them all */
	182	this_state = this_state->next;
	183	}
	184
	185	/* discard various storage */
	186	finalize_closure();
	187	free_storage();
	188
	189	/* set up initial and final states as parser wants them */
	190	augment_automaton();
	191	}
	192
	193
	194
	195	/* Find which symbols can be shifted in the current state,
	196	and for each one record which items would be active after that shift.
	197	Uses the contents of itemset.
	198	shift_symbol is set to a vector of the symbols that can be shifted.
	199	For each symbol in the grammar, kernel_base[symbol] points to
	200	a vector of item numbers activated if that symbol is shifted,
	201	and kernel_end[symbol] points after the end of that vector. */
	202	void
d2729d44	203	new_itemsets (void)
40675e7c DM	204	{
	205	register int i;
	206	register int shiftcount;
	207	register short *isp;
	208	register short *ksp;
	209	register int symbol;
	210
	211	#ifdef TRACE
	212	fprintf(stderr, "Entering new_itemsets\n");
	213	#endif
	214
	215	for (i = 0; i < nsyms; i++)
	216	kernel_end[i] = NULL;
	217
	218	shiftcount = 0;
	219
	220	isp = itemset;
	221
	222	while (isp < itemsetend)
	223	{
	224	i = *isp++;
	225	symbol = ritem[i];
	226	if (symbol > 0)
	227	{
	228	ksp = kernel_end[symbol];
	229
	230	if (!ksp)
	231	{
	232	shift_symbol[shiftcount++] = symbol;
	233	ksp = kernel_base[symbol];
	234	}
	235
	236	*ksp++ = i + 1;
	237	kernel_end[symbol] = ksp;
	238	}
	239	}
	240
	241	nshifts = shiftcount;
	242	}
	243
	244
	245
	246	/* Use the information computed by new_itemsets to find the state numbers
	247	reached by each shift transition from the current state.
	248
	249	shiftset is set up as a vector of state numbers of those states. */
	250	void
d2729d44	251	append_states (void)
40675e7c DM	252	{
	253	register int i;
	254	register int j;
	255	register int symbol;
	256
	257	#ifdef TRACE
	258	fprintf(stderr, "Entering append_states\n");
	259	#endif
	260
	261	/* first sort shift_symbol into increasing order */
	262
	263	for (i = 1; i < nshifts; i++)
	264	{
	265	symbol = shift_symbol[i];
	266	j = i;
	267	while (j > 0 && shift_symbol[j - 1] > symbol)
	268	{
	269	shift_symbol[j] = shift_symbol[j - 1];
	270	j--;
	271	}
	272	shift_symbol[j] = symbol;
	273	}
	274
	275	for (i = 0; i < nshifts; i++)
	276	{
	277	symbol = shift_symbol[i];
	278	shiftset[i] = get_state(symbol);
	279	}
	280	}
	281
	282
	283
	284	/* find the state number for the state we would get to
	285	(from the current state) by shifting symbol.
	286	Create a new state if no equivalent one exists already.
	287	Used by append_states */
	288
	289	int
d2729d44	290	get_state (int symbol)
40675e7c DM	291	{
	292	register int key;
	293	register short *isp1;
	294	register short *isp2;
	295	register short *iend;
	296	register core *sp;
	297	register int found;
	298
	299	int n;
	300
	301	#ifdef TRACE
	302	fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
	303	#endif
	304
	305	isp1 = kernel_base[symbol];
	306	iend = kernel_end[symbol];
	307	n = iend - isp1;
	308
	309	/* add up the target state's active item numbers to get a hash key */
	310	key = 0;
	311	while (isp1 < iend)
	312	key += *isp1++;
	313
	314	key = key % STATE_TABLE_SIZE;
	315
	316	sp = state_table[key];
	317
	318	if (sp)
	319	{
	320	found = 0;
	321	while (!found)
	322	{
	323	if (sp->nitems == n)
	324	{
	325	found = 1;
	326	isp1 = kernel_base[symbol];
	327	isp2 = sp->items;
	328
	329	while (found && isp1 < iend)
	330	{
	331	if (isp1++ != isp2++)
	332	found = 0;
	333	}
	334	}
	335
	336	if (!found)
	337	{
	338	if (sp->link)
	339	{
	340	sp = sp->link;
	341	}
	342	else /* bucket exhausted and no match */
	343	{
	344	sp = sp->link = new_state(symbol);
	345	found = 1;
	346	}
	347	}
	348	}
	349	}
	350	else /* bucket is empty */
	351	{
	352	state_table[key] = sp = new_state(symbol);
	353	}
	354
355	return (sp->number);
356	}
357
358
359
360	/* subroutine of get_state. create a new state for those items, if necessary. */
361
362	core *
d2729d44	363	new_state (int symbol)
40675e7c DM	364	{
	365	register int n;
	366	register core *p;
	367	register short *isp1;
	368	register short *isp2;
	369	register short *iend;
	370
	371	#ifdef TRACE
	372	fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
	373	#endif
	374
	375	if (nstates >= MAXSHORT)
	376	toomany("states");
	377
	378	isp1 = kernel_base[symbol];
	379	iend = kernel_end[symbol];
	380	n = iend - isp1;
	381
	382	p = (core ) xmalloc((unsigned) (sizeof(core) + (n - 1) sizeof(short)));
	383	p->accessing_symbol = symbol;
	384	p->number = nstates;
	385	p->nitems = n;
	386
	387	isp2 = p->items;
	388	while (isp1 < iend)
	389	isp2++ = isp1++;
	390
	391	last_state->next = p;
	392	last_state = p;
	393
	394	nstates++;
	395
	396	return (p);
	397	}
	398
	399
	400	void
d2729d44	401	initialize_states (void)
40675e7c DM	402	{
	403	register core *p;
	404	/* register unsigned rp1; JF unused /
	405	/* register unsigned rp2; JF unused /
	406	/* register unsigned rend; JF unused /
	407
	408	p = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
	409	first_state = last_state = this_state = p;
	410	nstates = 1;
	411	}
	412
	413
	414	void
d2729d44	415	save_shifts (void)
40675e7c DM	416	{
	417	register shifts *p;
	418	register short *sp1;
	419	register short *sp2;
	420	register short *send;
	421
	422	p = (shifts *) xmalloc((unsigned) (sizeof(shifts) +
d2729d44	423	(nshifts - 1) * sizeof(short)));
40675e7c DM	424
	425	p->number = this_state->number;
	426	p->nshifts = nshifts;
	427
	428	sp1 = shiftset;
	429	sp2 = p->shifts;
	430	send = shiftset + nshifts;
	431
	432	while (sp1 < send)
	433	sp2++ = sp1++;
	434
	435	if (last_shift)
	436	{
	437	last_shift->next = p;
	438	last_shift = p;
	439	}
	440	else
	441	{
	442	first_shift = p;
	443	last_shift = p;
	444	}
	445	}
	446
	447
	448
	449	/* find which rules can be used for reduction transitions from the current state
	450	and make a reductions structure for the state to record their rule numbers. */
	451	void
d2729d44	452	save_reductions (void)
40675e7c DM	453	{
	454	register short *isp;
	455	register short *rp1;
	456	register short *rp2;
	457	register int item;
	458	register int count;
	459	register reductions *p;
	460
	461	short *rend;
	462
	463	/* find and count the active items that represent ends of rules */
	464
	465	count = 0;
	466	for (isp = itemset; isp < itemsetend; isp++)
	467	{
	468	item = ritem[*isp];
	469	if (item < 0)
	470	{
	471	redset[count++] = -item;
	472	}
	473	}
	474
	475	/* make a reductions structure and copy the data into it. */
	476
	477	if (count)
	478	{
	479	p = (reductions *) xmalloc((unsigned) (sizeof(reductions) +
d2729d44	480	(count - 1) * sizeof(short)));
40675e7c DM	481
	482	p->number = this_state->number;
	483	p->nreds = count;
	484
	485	rp1 = redset;
	486	rp2 = p->rules;
	487	rend = rp1 + count;
	488
	489	while (rp1 < rend)
	490	rp2++ = rp1++;
	491
	492	if (last_reduction)
	493	{
	494	last_reduction->next = p;
	495	last_reduction = p;
	496	}
	497	else
	498	{
	499	first_reduction = p;
	500	last_reduction = p;
	501	}
	502	}
	503	}
	504
	505
	506
	507	/* Make sure that the initial state has a shift that accepts the
	508	grammar's start symbol and goes to the next-to-final state,
	509	which has a shift going to the final state, which has a shift
	510	to the termination state.
	511	Create such states and shifts if they don't happen to exist already. */
	512	void
d2729d44	513	augment_automaton (void)
40675e7c DM	514	{
	515	register int i;
	516	register int k;
	517	/* register int found; JF unused */
	518	register core *statep;
	519	register shifts *sp;
	520	register shifts *sp2;
	521	register shifts *sp1;
	522
	523	sp = first_shift;
	524
	525	if (sp)
	526	{
	527	if (sp->number == 0)
	528	{
	529	k = sp->nshifts;
	530	statep = first_state->next;
	531
	532	/* The states reached by shifts from first_state are numbered 1...K.
	533	Look for one reached by start_symbol. */
	534	while (statep->accessing_symbol < start_symbol
	535	&& statep->number < k)
	536	statep = statep->next;
	537
	538	if (statep->accessing_symbol == start_symbol)
	539	{
	540	/* We already have a next-to-final state.
	541	Make sure it has a shift to what will be the final state. */
	542	k = statep->number;
	543
	544	while (sp && sp->number < k)
	545	{
	546	sp1 = sp;
	547	sp = sp->next;
	548	}
	549
	550	if (sp && sp->number == k)
	551	{
	552	sp2 = (shifts *) xmalloc((unsigned) (sizeof(shifts)
d2729d44	553	+ sp->nshifts * sizeof(short)));
40675e7c DM	554	sp2->number = k;
	555	sp2->nshifts = sp->nshifts + 1;
	556	sp2->shifts[0] = nstates;
	557	for (i = sp->nshifts; i > 0; i--)
	558	sp2->shifts[i] = sp->shifts[i - 1];
	559
	560	/* Patch sp2 into the chain of shifts in place of sp,
	561	following sp1. */
	562	sp2->next = sp->next;
	563	sp1->next = sp2;
	564	if (sp == last_shift)
	565	last_shift = sp2;
	566	FREE(sp);
	567	}
	568	else
	569	{
	570	sp2 = NEW(shifts);
	571	sp2->number = k;
	572	sp2->nshifts = 1;
	573	sp2->shifts[0] = nstates;
	574
	575	/* Patch sp2 into the chain of shifts between sp1 and sp. */
	576	sp2->next = sp;
	577	sp1->next = sp2;
	578	if (sp == 0)
	579	last_shift = sp2;
	580	}
	581	}
	582	else
	583	{
	584	/* There is no next-to-final state as yet. */
	585	/* Add one more shift in first_shift,
	586	going to the next-to-final state (yet to be made). */
	587	sp = first_shift;
	588
	589	sp2 = (shifts *) xmalloc(sizeof(shifts)
	590	+ sp->nshifts * sizeof(short));
	591	sp2->nshifts = sp->nshifts + 1;
	592
	593	/* Stick this shift into the vector at the proper place. */
	594	statep = first_state->next;
	595	for (k = 0, i = 0; i < sp->nshifts; k++, i++)
	596	{
	597	if (statep->accessing_symbol > start_symbol && i == k)
	598	sp2->shifts[k++] = nstates;
	599	sp2->shifts[k] = sp->shifts[i];
	600	statep = statep->next;
	601	}
	602	if (i == k)
	603	sp2->shifts[k++] = nstates;
	604
	605	/* Patch sp2 into the chain of shifts
	606	in place of sp, at the beginning. */
	607	sp2->next = sp->next;
	608	first_shift = sp2;
	609	if (last_shift == sp)
	610	last_shift = sp2;
	611
	612	FREE(sp);
	613
	614	/* Create the next-to-final state, with shift to
	615	what will be the final state. */
	616	insert_start_shift();
	617	}
618	}
619	else
620	{
621	/* The initial state didn't even have any shifts.
622	Give it one shift, to the next-to-final state. */
623	sp = NEW(shifts);
624	sp->nshifts = 1;
625	sp->shifts[0] = nstates;
626
627	/* Patch sp into the chain of shifts at the beginning. */
628	sp->next = first_shift;
629	first_shift = sp;
630
631	/* Create the next-to-final state, with shift to
632	what will be the final state. */
633	insert_start_shift();
634	}
635	}
636	else
637	{
638	/* There are no shifts for any state.
639	Make one shift, from the initial state to the next-to-final state. */
640
641	sp = NEW(shifts);
642	sp->nshifts = 1;
643	sp->shifts[0] = nstates;
644
645	/* Initialize the chain of shifts with sp. */
646	first_shift = sp;
647	last_shift = sp;
648
649	/* Create the next-to-final state, with shift to
650	what will be the final state. */
651	insert_start_shift();
652	}
653
654	/* Make the final state--the one that follows a shift from the
655	next-to-final state.
656	The symbol for that shift is 0 (end-of-file). */
657	statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
658	statep->number = nstates;
659	last_state->next = statep;
660	last_state = statep;
661
662	/* Make the shift from the final state to the termination state. */
663	sp = NEW(shifts);
664	sp->number = nstates++;
665	sp->nshifts = 1;
666	sp->shifts[0] = nstates;
667	last_shift->next = sp;
668	last_shift = sp;
669
670	/* Note that the variable `final_state' refers to what we sometimes call
671	the termination state. */
672	final_state = nstates;
673
674	/* Make the termination state. */
675	statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
676	statep->number = nstates++;
677	last_state->next = statep;
678	last_state = statep;
679	}
680
681
682	/* subroutine of augment_automaton.
683	Create the next-to-final state, to which a shift has already been made in
684	the initial state. */
685	void
d2729d44	686	insert_start_shift (void)
40675e7c DM	687	{
	688	register core *statep;
	689	register shifts *sp;
	690
	691	statep = (core *) xmalloc((unsigned) (sizeof(core) - sizeof(short)));
	692	statep->number = nstates;
	693	statep->accessing_symbol = start_symbol;
	694
	695	last_state->next = statep;
	696	last_state = statep;
	697
	698	/* Make a shift from this state to (what will be) the final state. */
	699	sp = NEW(shifts);
	700	sp->number = nstates++;
	701	sp->nshifts = 1;
	702	sp->shifts[0] = nstates;
	703
	704	last_shift->next = sp;
	705	last_shift = sp;
	706	}