src/LR0.c

/* Generate the nondeterministic finite state machine for bison,
   Copyright 1984, 1986, 1989, 2000, 2001  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 "getargs.h"
#include "reader.h"
#include "gram.h"
#include "state.h"
#include "complain.h"
#include "closure.h"
#include "LR0.h"
#include "lalr.h"
#include "reduce.h"

int nstates;
int final_state;
state_t *first_state = NULL;
shifts *first_shift = NULL;

static state_t *this_state = NULL;
static state_t *last_state = NULL;
static shifts *last_shift = NULL;

static int nshifts;
static short *shift_symbol = NULL;

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

static short **kernel_base = NULL;
static int *kernel_size = NULL;
static short *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)
{
  int i;

  /* 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[ritem[i]]++;
      }

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

  free (symbol_count);
  kernel_size = XCALLOC (int, nsyms);
}


static void
allocate_storage (void)
{
  allocate_itemsets ();

  shiftset = XCALLOC (short, nsyms);
  redset = XCALLOC (short, nrules + 1);
  state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
}


static void
free_storage (void)
{
  free (shift_symbol);
  free (redset);
  free (shiftset);
  free (kernel_base);
  free (kernel_size);
  XFREE (kernel_items);
  free (state_hash);
}


/*----------------------------------------------------------------.
| 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_size[symbol] is their numbers.              |
`----------------------------------------------------------------*/

static void
new_itemsets (void)
{
  int i;

  if (trace_flag)
    fprintf (stderr, "Entering new_itemsets, state = %d\n",
	     this_state->number);

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

  shift_symbol = XCALLOC (short, nsyms);
  nshifts = 0;

  for (i = 0; i < nitemset; ++i)
    {
      int symbol = ritem[itemset[i]];
      if (symbol > 0)
	{
	  if (!kernel_size[symbol])
	    {
	      shift_symbol[nshifts] = symbol;
	      nshifts++;
	    }

	  kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
	  kernel_size[symbol]++;
	}
    }
}


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

static state_t *
new_state (int symbol)
{
  state_t *p;

  if (trace_flag)
    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);

  p = STATE_ALLOC (kernel_size[symbol]);
  p->accessing_symbol = symbol;
  p->number = nstates;
  p->nitems = kernel_size[symbol];

  shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);

  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;
  int i;
  state_t *sp;

  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 < kernel_size[symbol]; ++i)
    key += kernel_base[symbol][i];
  key = key % STATE_HASH_SIZE;
  sp = state_hash[key];

  if (sp)
    {
      int found = 0;
      while (!found)
	{
	  if (sp->nitems == kernel_size[symbol])
	    {
	      found = 1;
	      for (i = 0; i < kernel_size[symbol]; ++i)
		if (kernel_base[symbol][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);
		  found = 1;
		}
	    }
	}
    }
  else				/* bucket is empty */
    {
      state_hash[key] = sp = new_state (symbol);
    }

  if (trace_flag)
    fprintf (stderr, "Exiting get_state => %d\n", sp->number);

  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_flag)
    fprintf (stderr, "Entering append_states, state = %d\n",
	     this_state->number);

  /* 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++)
    shiftset[i] = get_state (shift_symbol[i]);
}


static void
new_states (void)
{
  first_state = last_state = this_state = STATE_ALLOC (0);
  nstates = 1;
}


/*------------------------------------------------------------.
| Save the NSHIFTS of SHIFTSET into the current linked list.  |
`------------------------------------------------------------*/

static void
save_shifts (void)
{
  shifts *p = shifts_new (nshifts);

  p->number = this_state->number;
  shortcpy (p->shifts, shiftset, nshifts);
  this_state->shifts = p;

  if (last_shift)
    last_shift->next = 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.      |
|                                                                   |
| The task of this state consists in shifting (actually, it's a     |
| goto, but shifts and gotos are both stored in SHIFTS) the start   |
| symbols, hence the name.                                          |
`------------------------------------------------------------------*/

static void
insert_start_shifting_state (void)
{
  state_t *statep;
  shifts *sp;

  statep = STATE_ALLOC (0);
  statep->number = nstates;

  /* The distinctive feature of this state from the
     eof_shifting_state, is that it is labeled as post-start-symbol
     shifting.  I fail to understand why this state, and the
     post-start-start can't be merged into one.  But it does fail if
     you try. --akim */
  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 = shifts_new (1);
  statep->shifts = sp;
  sp->number = nstates++;
  sp->shifts[0] = nstates;

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


/*-----------------------------------------------------------------.
| Subroutine of augment_automaton.  Create the final state, which  |
| shifts `0', the end of file.  The initial state shifts the start |
| symbol, and goes to here.                                        |
`-----------------------------------------------------------------*/

static void
insert_eof_shifting_state (void)
{
  state_t *statep;
  shifts *sp;

  /* 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 = STATE_ALLOC (0);
  statep->number = nstates;

  last_state->next = statep;
  last_state = statep;

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

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


/*---------------------------------------------------------------.
| Subroutine of augment_automaton.  Create the accepting state.  |
`---------------------------------------------------------------*/

static void
insert_accepting_state (void)
{
  state_t *statep;

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

  /* Make the termination state.  */
  statep = STATE_ALLOC (0);
  statep->number = nstates++;
  last_state->next = statep;
  last_state = statep;
}


/*------------------------------------------------------------------.
| 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)
{
  if (!first_shift->nshifts)
    {
      /* There are no shifts for any state.  Make one shift, from the
	 initial state to the next-to-final state.  */

      shifts *sp = shifts_new (1);
      first_state->shifts = sp;
      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_shifting_state ();
    }
  else if (first_shift->number == 0)
    {
      state_t *statep = first_state->next;
      shifts *sp = first_shift;
      shifts *sp1 = NULL;
      /* 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;

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

	  if (sp && sp->number == statep->number)
	    {
	      int i;
	      shifts *sp2 = shifts_new (sp->nshifts + 1);
	      sp2->number = statep->number;
	      statep->shifts = sp2;
	      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
	    {
	      shifts *sp2 = shifts_new (1);
	      sp2->number = statep->number;
	      statep->shifts = sp2;
	      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
	{
	  int i, k;
	  shifts *sp2;
	  sp = first_shift;

	  /* 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).  */
	  sp2 = shifts_new (sp->nshifts + 1);
	  first_state->shifts = sp2;
	  /* 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_shifting_state ();
	}
    }
  else
    {
      /* The initial state didn't even have any shifts.
	 Give it one shift, to the next-to-final state.  */
      shifts *sp = shifts_new (1);
      first_state->shifts = sp;
      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_shifting_state ();
    }

  insert_eof_shifting_state ();
  insert_accepting_state ();
}


/*----------------------------------------------------------------.
| 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)
{
  int count;
  int i;

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

  count = 0;
  for (i = 0; i < nitemset; ++i)
    {
      int item = ritem[itemset[i]];
      if (item < 0)
	redset[count++] = -item;
    }

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

  if (count)
    {
      reductions *p = REDUCTIONS_ALLOC (count);
      p->nreds = count;
      shortcpy (p->rules, redset, count);

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