src/LR0.c

/* Generate the nondeterministic finite state machine for bison,
   Copyright 1984, 1986, 1989, 2000, 2001, 2002  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 "bitset.h"
#include "quotearg.h"
#include "symtab.h"
#include "gram.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"

typedef struct state_list_s
{
  struct state_list_s *next;
  state_t *state;
} state_list_t;

static state_list_t *first_state = NULL;
static state_list_t *last_state = NULL;

static void
state_list_append (state_t *state)
{
  state_list_t *node = XMALLOC (state_list_t, 1);
  node->next = NULL;
  node->state = state;

  if (!first_state)
    first_state = node;
  if (last_state)
    last_state->next = node;
  last_state = node;
}

static int nshifts;
static symbol_number_t *shift_symbol = NULL;

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

static item_number_t **kernel_base = NULL;
static int *kernel_size = NULL;
static item_number_t *kernel_items = NULL;

\f
static void
allocate_itemsets (void)
{
  symbol_number_t i;
  rule_number_t r;
  item_number_t *rhsp;

  /* 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 (r = 1; r < nrules + 1; ++r)
    for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
      {
	count++;
	symbol_count[*rhsp]++;
      }

  /* 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 (item_number_t *, nsyms);
  if (count)
    kernel_items = XCALLOC (item_number_t, 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 (state_number_t, nsyms);
  redset = XCALLOC (short, nrules + 1);
  state_hash_new ();
  shift_symbol = XCALLOC (symbol_number_t, nsyms);
}


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


/*---------------------------------------------------------------.
| Find which symbols can be shifted in 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 (state_t *state)
{
  int i;

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

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

  nshifts = 0;

  for (i = 0; i < nritemset; ++i)
    if (ritem[itemset[i]] >= 0)
      {
	symbol_number_t symbol
	  = item_number_as_symbol_number (ritem[itemset[i]]);
	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 (symbol_number_t symbol, size_t core_size, item_number_t *core)
{
  state_t *res;

  if (trace_flag)
    fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
	     nstates, symbol, symbol_tag_get (symbols[symbol]));

  res = state_new (symbol, core_size, core);
  state_hash_insert (res);

  /* If this is the eoftoken, and this is not the initial state, then
     this is the final state.  */
  if (symbol == 0 && first_state)
    final_state = res;

  state_list_append (res);
  return res;
}


/*--------------------------------------------------------------.
| 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 state_number_t
get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
{
  state_t *sp;

  if (trace_flag)
    fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
	     symbol, symbol_tag_get (symbols[symbol]));

  sp = state_hash_lookup (core_size, core);
  if (!sp)
    sp = new_state (symbol, core_size, core);

  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 STATE.              |
|                                                                   |
| SHIFTSET is set up as a vector of state numbers of those states.  |
`------------------------------------------------------------------*/

static void
append_states (state_t *state)
{
  int i;
  int j;
  symbol_number_t symbol;

  if (trace_flag)
    fprintf (stderr, "Entering append_states, state = %d\n",
	     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++)
    {
      symbol = shift_symbol[i];
      shiftset[i] = get_state (symbol,
			       kernel_size[symbol], kernel_base[symbol]);
    }
}


static void
new_states (void)
{
  /* The 0 at the lhs is the index of the item of this initial rule.  */
  kernel_base[0][0] = 0;
  kernel_size[0] = 1;
  state_list_append (new_state (0, kernel_size[0], kernel_base[0]));
}


/*----------------------------------------------------------------.
| 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 (state_t *state)
{
  int count = 0;
  int i;

  /* If this is the final state, we want it to have no reductions at
     all, although it has one for `START_SYMBOL EOF .'.  */
  if (final_state && state->number == final_state->number)
    return;

  /* Find and count the active items that represent ends of rules. */
  for (i = 0; i < nritemset; ++i)
    {
      int item = ritem[itemset[i]];
      if (item < 0)
	redset[count++] = -item;
    }

  /* Make a reductions structure and copy the data into it.  */
  state_reductions_set (state, count, redset);
}

\f
/*---------------.
| Build STATES.  |
`---------------*/

static void
set_states (void)
{
  states = XCALLOC (state_t *, nstates);

  while (first_state)
    {
      state_list_t *this = first_state;

      /* Pessimization, but simplification of the code: make sure all
	 the states have a shifts, errs, and reductions, even if
	 reduced to 0.  */
      state_t *state = this->state;
      if (!state->shifts)
	state_shifts_set (state, 0, 0);
      if (!state->errs)
	state->errs = errs_new (0);
      if (!state->reductions)
	state_reductions_set (state, 0, 0);

      states[state->number] = state;

      first_state = this->next;
      free (this);
    }
  first_state = NULL;
  last_state = NULL;
}


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

void
generate_states (void)
{
  state_list_t *list = NULL;
  allocate_storage ();
  new_closure (nritems);
  new_states ();
  list = first_state;

  while (list)
    {
      state_t *state = list->state;
      if (trace_flag)
	fprintf (stderr, "Processing state %d (reached by %s)\n",
		 state->number,
		 symbol_tag_get (symbols[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 (state->items, state->nitems);
      /* Record the reductions allowed out of this state.  */
      save_reductions (state);
      /* Find the itemsets of the states that shifts can reach.  */
      new_itemsets (state);
      /* Find or create the core structures for those states.  */
      append_states (state);

      /* Create the shifts structures for the shifts to those states,
	 now that the state numbers transitioning to are known.  */
      state_shifts_set (state, nshifts, shiftset);

      /* States are queued when they are created; process them all.
	 */
      list = list->next;
    }

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

  /* Set up STATES. */
  set_states ();
}
Commit	Line	Data
	1	/* Generate the nondeterministic finite state machine for bison,
	2	Copyright 1984, 1986, 1989, 2000, 2001, 2002 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 "bitset.h"
	27	#include "quotearg.h"
	28	#include "symtab.h"
	29	#include "gram.h"
	30	#include "getargs.h"
	31	#include "reader.h"
	32	#include "gram.h"
	33	#include "state.h"
	34	#include "complain.h"
	35	#include "closure.h"
	36	#include "LR0.h"
	37	#include "lalr.h"
	38	#include "reduce.h"
	39
	40	typedef struct state_list_s
	41	{
	42	struct state_list_s *next;
	43	state_t *state;
	44	} state_list_t;
	45
	46	static state_list_t *first_state = NULL;
	47	static state_list_t *last_state = NULL;
	48
	49	static void
	50	state_list_append (state_t *state)
	51	{
	52	state_list_t *node = XMALLOC (state_list_t, 1);
	53	node->next = NULL;
	54	node->state = state;
	55
	56	if (!first_state)
	57	first_state = node;
	58	if (last_state)
	59	last_state->next = node;
	60	last_state = node;
	61	}
	62
	63	static int nshifts;
	64	static symbol_number_t *shift_symbol = NULL;
	65
	66	static short *redset = NULL;
	67	static state_number_t *shiftset = NULL;
	68
	69	static item_number_t **kernel_base = NULL;
	70	static int *kernel_size = NULL;
	71	static item_number_t *kernel_items = NULL;
	72
	73	\f
	74	static void
	75	allocate_itemsets (void)
	76	{
	77	symbol_number_t i;
	78	rule_number_t r;
	79	item_number_t *rhsp;
	80
	81	/* Count the number of occurrences of all the symbols in RITEMS.
	82	Note that useless productions (hence useless nonterminals) are
	83	browsed too, hence we need to allocate room for _all_ the
	84	symbols. */
	85	int count = 0;
	86	short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
	87
	88	for (r = 1; r < nrules + 1; ++r)
	89	for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
	90	{
	91	count++;
	92	symbol_count[*rhsp]++;
	93	}
	94
	95	/* See comments before new_itemsets. All the vectors of items
	96	live inside KERNEL_ITEMS. The number of active items after
	97	some symbol cannot be more than the number of times that symbol
	98	appears as an item, which is SYMBOL_COUNT[SYMBOL].
	99	We allocate that much space for each symbol. */
	100
	101	kernel_base = XCALLOC (item_number_t *, nsyms);
	102	if (count)
	103	kernel_items = XCALLOC (item_number_t, count);
	104
	105	count = 0;
	106	for (i = 0; i < nsyms; i++)
	107	{
	108	kernel_base[i] = kernel_items + count;
	109	count += symbol_count[i];
	110	}
	111
	112	free (symbol_count);
	113	kernel_size = XCALLOC (int, nsyms);
	114	}
	115
	116
	117	static void
	118	allocate_storage (void)
	119	{
	120	allocate_itemsets ();
	121
	122	shiftset = XCALLOC (state_number_t, nsyms);
	123	redset = XCALLOC (short, nrules + 1);
	124	state_hash_new ();
	125	shift_symbol = XCALLOC (symbol_number_t, nsyms);
	126	}
	127
	128
	129	static void
	130	free_storage (void)
	131	{
	132	free (shift_symbol);
	133	free (redset);
	134	free (shiftset);
	135	free (kernel_base);
	136	free (kernel_size);
	137	XFREE (kernel_items);
	138	state_hash_free ();
	139	}
	140
	141
	142
	143
	144	/*---------------------------------------------------------------.
	145	\| Find which symbols can be shifted in STATE, and for each one \|
	146	\| record which items would be active after that shift. Uses the \|
	147	\| contents of itemset. \|
	148	\| \|
	149	\| shift_symbol is set to a vector of the symbols that can be \|
	150	\| shifted. For each symbol in the grammar, kernel_base[symbol] \|
	151	\| points to a vector of item numbers activated if that symbol is \|
	152	\| shifted, and kernel_size[symbol] is their numbers. \|
	153	`---------------------------------------------------------------*/
	154
	155	static void
	156	new_itemsets (state_t *state)
	157	{
	158	int i;
	159
	160	if (trace_flag)
	161	fprintf (stderr, "Entering new_itemsets, state = %d\n",
	162	state->number);
	163
	164	for (i = 0; i < nsyms; i++)
	165	kernel_size[i] = 0;
	166
	167	nshifts = 0;
	168
	169	for (i = 0; i < nritemset; ++i)
	170	if (ritem[itemset[i]] >= 0)
	171	{
	172	symbol_number_t symbol
	173	= item_number_as_symbol_number (ritem[itemset[i]]);
	174	if (!kernel_size[symbol])
	175	{
	176	shift_symbol[nshifts] = symbol;
	177	nshifts++;
	178	}
	179
	180	kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
	181	kernel_size[symbol]++;
	182	}
	183	}
	184
	185
	186
	187	/*-----------------------------------------------------------------.
	188	\| Subroutine of get_state. Create a new state for those items, if \|
	189	\| necessary. \|
	190	`-----------------------------------------------------------------*/
	191
	192	static state_t *
	193	new_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
	194	{
	195	state_t *res;
	196
	197	if (trace_flag)
	198	fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
	199	nstates, symbol, symbol_tag_get (symbols[symbol]));
	200
	201	res = state_new (symbol, core_size, core);
	202	state_hash_insert (res);
	203
	204	/* If this is the eoftoken, and this is not the initial state, then
	205	this is the final state. */
	206	if (symbol == 0 && first_state)
	207	final_state = res;
	208
	209	state_list_append (res);
	210	return res;
	211	}
	212
	213
	214	/*--------------------------------------------------------------.
	215	\| Find the state number for the state we would get to (from the \|
	216	\| current state) by shifting symbol. Create a new state if no \|
	217	\| equivalent one exists already. Used by append_states. \|
	218	`--------------------------------------------------------------*/
	219
	220	static state_number_t
	221	get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
	222	{
	223	state_t *sp;
	224
	225	if (trace_flag)
	226	fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
	227	symbol, symbol_tag_get (symbols[symbol]));
	228
	229	sp = state_hash_lookup (core_size, core);
	230	if (!sp)
	231	sp = new_state (symbol, core_size, core);
	232
	233	if (trace_flag)
	234	fprintf (stderr, "Exiting get_state => %d\n", sp->number);
	235
	236	return sp->number;
	237	}
	238
	239	/*------------------------------------------------------------------.
	240	\| Use the information computed by new_itemsets to find the state \|
	241	\| numbers reached by each shift transition from STATE. \|
	242	\| \|
	243	\| SHIFTSET is set up as a vector of state numbers of those states. \|
	244	`------------------------------------------------------------------*/
	245
	246	static void
	247	append_states (state_t *state)
	248	{
	249	int i;
	250	int j;
	251	symbol_number_t symbol;
	252
	253	if (trace_flag)
	254	fprintf (stderr, "Entering append_states, state = %d\n",
	255	state->number);
	256
	257	/* first sort shift_symbol into increasing order */
	258
	259	for (i = 1; i < nshifts; i++)
	260	{
	261	symbol = shift_symbol[i];
	262	j = i;
	263	while (j > 0 && shift_symbol[j - 1] > symbol)
	264	{
	265	shift_symbol[j] = shift_symbol[j - 1];
	266	j--;
	267	}
	268	shift_symbol[j] = symbol;
	269	}
	270
	271	for (i = 0; i < nshifts; i++)
	272	{
	273	symbol = shift_symbol[i];
	274	shiftset[i] = get_state (symbol,
	275	kernel_size[symbol], kernel_base[symbol]);
	276	}
	277	}
	278
	279
	280	static void
	281	new_states (void)
	282	{
	283	/* The 0 at the lhs is the index of the item of this initial rule. */
	284	kernel_base[0][0] = 0;
	285	kernel_size[0] = 1;
	286	state_list_append (new_state (0, kernel_size[0], kernel_base[0]));
	287	}
	288
	289
	290
	291	/*----------------------------------------------------------------.
	292	\| Find which rules can be used for reduction transitions from the \|
	293	\| current state and make a reductions structure for the state to \|
	294	\| record their rule numbers. \|
	295	`----------------------------------------------------------------*/
	296
	297	static void
	298	save_reductions (state_t *state)
	299	{
	300	int count = 0;
	301	int i;
	302
	303	/* If this is the final state, we want it to have no reductions at
	304	all, although it has one for `START_SYMBOL EOF .'. */
	305	if (final_state && state->number == final_state->number)
	306	return;
	307
	308	/* Find and count the active items that represent ends of rules. */
	309	for (i = 0; i < nritemset; ++i)
	310	{
	311	int item = ritem[itemset[i]];
	312	if (item < 0)
	313	redset[count++] = -item;
	314	}
	315
	316	/* Make a reductions structure and copy the data into it. */
	317	state_reductions_set (state, count, redset);
	318	}
	319
	320	\f
	321	/*---------------.
	322	\| Build STATES. \|
	323	`---------------*/
	324
	325	static void
	326	set_states (void)
	327	{
	328	states = XCALLOC (state_t *, nstates);
	329
	330	while (first_state)
	331	{
	332	state_list_t *this = first_state;
	333
	334	/* Pessimization, but simplification of the code: make sure all
	335	the states have a shifts, errs, and reductions, even if
	336	reduced to 0. */
	337	state_t *state = this->state;
	338	if (!state->shifts)
	339	state_shifts_set (state, 0, 0);
	340	if (!state->errs)
	341	state->errs = errs_new (0);
	342	if (!state->reductions)
	343	state_reductions_set (state, 0, 0);
	344
	345	states[state->number] = state;
	346
	347	first_state = this->next;
	348	free (this);
	349	}
	350	first_state = NULL;
	351	last_state = NULL;
	352	}
	353
	354
	355	/*-------------------------------------------------------------------.
	356	\| Compute the nondeterministic finite state machine (see state.h for \|
	357	\| details) from the grammar. \|
	358	`-------------------------------------------------------------------*/
	359
	360	void
	361	generate_states (void)
	362	{
	363	state_list_t *list = NULL;
	364	allocate_storage ();
	365	new_closure (nritems);
	366	new_states ();
	367	list = first_state;
	368
	369	while (list)
	370	{
	371	state_t *state = list->state;
	372	if (trace_flag)
	373	fprintf (stderr, "Processing state %d (reached by %s)\n",
	374	state->number,
	375	symbol_tag_get (symbols[state->accessing_symbol]));
	376	/* Set up ruleset and itemset for the transitions out of this
	377	state. ruleset gets a 1 bit for each rule that could reduce
	378	now. itemset gets a vector of all the items that could be
	379	accepted next. */
	380	closure (state->items, state->nitems);
	381	/* Record the reductions allowed out of this state. */
	382	save_reductions (state);
	383	/* Find the itemsets of the states that shifts can reach. */
	384	new_itemsets (state);
	385	/* Find or create the core structures for those states. */
	386	append_states (state);
	387
	388	/* Create the shifts structures for the shifts to those states,
	389	now that the state numbers transitioning to are known. */
	390	state_shifts_set (state, nshifts, shiftset);
	391
	392	/* States are queued when they are created; process them all.
	393	*/
	394	list = list->next;
	395	}
	396
	397	/* discard various storage */
	398	free_closure ();
	399	free_storage ();
	400
	401	/* Set up STATES. */
	402	set_states ();
	403	}