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 "symtab.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"

unsigned int nstates;
/* Initialize the final state to -1, otherwise, it might be set to 0
   by default, and since we don't compute the reductions of the final
   state, we end up not computing the reductions of the initial state,
   which is of course needed.

   FINAL_STATE is properly set by new_state when it recognizes the
   accessing symbol: EOF.  */
int final_state = -1;
static state_t *first_state = NULL;

static state_t *this_state = NULL;
static state_t *last_state = 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; i < nritems; ++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);
  shift_symbol = XCALLOC (short, nsyms);
}


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;

  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, symbols[symbol]->tag);

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

  /* If this is the eoftoken, then this is the final state. */
  if (symbol == 0)
    final_state = p->number;

  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, symbols[symbol]->tag);

  /* 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);
  shortcpy (p->shifts, shiftset, nshifts);
  this_state->shifts = p;
}


/*----------------------------------------------------------------.
| Find which rules can be used for reduction transitions from the |
| current state and make a reductions structure for the state to  |
| record their rule numbers.                                      |
`----------------------------------------------------------------*/

static void
save_reductions (void)
{
  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 (this_state->number == final_state)
    return;

  /* Find and count the active items that represent ends of rules. */
  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.  */
  this_state->reductions = reductions_new (count);
  shortcpy (this_state->reductions->rules, redset, count);
}

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

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

  for (sp = first_state; sp; sp = sp->next)
    {
      /* Pessimization, but simplification of the code: make sure all
	 the states have a shifts, errs, and reductions, even if
	 reduced to 0.  */
      if (!sp->shifts)
	sp->shifts = shifts_new (0);
      if (!sp->errs)
	sp->errs = errs_new (0);
      if (!sp->reductions)
	sp->reductions = reductions_new (0);

      states[sp->number] = sp;
    }
}

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

void
generate_states (void)
{
  allocate_storage ();
  new_closure (nritems);
  new_states ();

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