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

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