src/LR0.c

/* Generate the nondeterministic finite state machine for bison,
   Copyright 1984, 1986, 1989, 2000 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, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */


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

#include "system.h"
#include "gram.h"
#include "state.h"
#include "complain.h"
#include "closure.h"
#include "LR0.h"


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

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

static int nshifts;
static short *shift_symbol = NULL;

static short *redset = NULL;
static short *shiftset = NULL;

static short **kernel_base = NULL;
static short **kernel_end = NULL;
static short *kernel_items = NULL;

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

#define	STATE_TABLE_SIZE	1009
static core **state_table = NULL;

\f
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++;
    }

  /* 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 = XCALLOC (short *, nsyms);
  if (count)
    kernel_items = XCALLOC (short, count);

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

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


static void
allocate_storage (void)
{
  allocate_itemsets ();

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


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


/*----------------------------------------------------------------.
| 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.                                                         |
`----------------------------------------------------------------*/

static void
new_itemsets (void)
{
  int i;
  int shiftcount;
  short *isp;
  short *ksp;
  int symbol;

#if 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;
}


/*-----------------------------------------------------------------.
| Subroutine of get_state.  Create a new state for those items, if |
| necessary.                                                       |
`-----------------------------------------------------------------*/

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

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

  if (nstates >= MAXSHORT)
    fatal (_("too many states (max %d)"), MAXSHORT);

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

  p =
    (core *) xcalloc ((unsigned) (sizeof (core) + (n - 1) * sizeof (short)), 1);
  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;
}


/*--------------------------------------------------------------.
| 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.         |
`--------------------------------------------------------------*/

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

  int n;

#if 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;
}

/*------------------------------------------------------------------.
| 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.  |
`------------------------------------------------------------------*/

static void
append_states (void)
{
  int i;
  int j;
  int symbol;

#if 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);
    }
}


static void
new_states (void)
{
  core *p;

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


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

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

  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;
    }
}


/*------------------------------------------------------------------.
| Subroutine of augment_automaton.  Create the next-to-final state, |
| to which a shift has already been made in the initial state.      |
`------------------------------------------------------------------*/

static void
insert_start_shift (void)
{
  core *statep;
  shifts *sp;

  statep = (core *) xcalloc ((unsigned) (sizeof (core) - sizeof (short)), 1);
  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 = XCALLOC (shifts, 1);
  sp->number = nstates++;
  sp->nshifts = 1;
  sp->shifts[0] = nstates;

  last_shift->next = sp;
  last_shift = sp;
}


/*------------------------------------------------------------------.
| 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.                                          |
`------------------------------------------------------------------*/

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->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 *) xcalloc ((unsigned) (sizeof (shifts)
							+
							sp->nshifts *
							sizeof (short)), 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 = XCALLOC (shifts, 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;

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

	      XFREE (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 = XCALLOC (shifts, 1);
	  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 = XCALLOC (shifts, 1);
      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 *) xcalloc ((unsigned) (sizeof (core) - sizeof (short)), 1);
  statep->number = nstates;
  last_state->next = statep;
  last_state = statep;

  /* Make the shift from the final state to the termination state.  */
  sp = XCALLOC (shifts, 1);
  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 *) xcalloc ((unsigned) (sizeof (core) - sizeof (short)), 1);
  statep->number = nstates++;
  last_state->next = statep;
  last_state = statep;
}


/*----------------------------------------------------------------.
| 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.                                      |
`----------------------------------------------------------------*/

static void
save_reductions (void)
{
  short *isp;
  short *rp1;
  short *rp2;
  int item;
  int count;
  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 *) xcalloc ((unsigned) (sizeof (reductions) +
					      (count - 1) * sizeof (short)), 1);

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

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

      for (/* nothing */; rp1 < rend; ++rp1, ++rp2)
	*rp2 = *rp1;

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

\f
/*-------------------------------------------------------------------.
| Compute the nondeterministic finite state machine (see state.h for |
| details) from the grammar.                                         |
`-------------------------------------------------------------------*/

void
generate_states (void)
{
  allocate_storage ();
  new_closure (nitems);
  new_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 */
  free_closure ();
  free_storage ();

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